实验六 二叉树1(1)

《实验六 二叉树1(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验六　二叉树【实验目的】1、掌握二叉树的定义和各种基本存储结构，特别是链式实现；2、掌握二叉树的建立以及各种遍历算法；3、理解二叉树的性质；【实验要求】给出以及后序遍历，请大家完成算法：要求建立基于二叉链表的二叉树，建立二叉树的二叉链表存储并遍历，包括：1、先序遍历；2、中序遍历；3、后序遍历；4、层次遍历；5、求叶子结点数。#include#include#include#defineINFEASIBLE-1#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintStatu

2、s;typedefcharTElemType;//二叉树二叉链表储存结构typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//二叉树输入StatusCreateBiTree(BiTree&T){charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->r

3、child);}returnOK;}//CreateBiTreeStatusVisit(TElemTypee){printf("%c",e);returnOK;}//先序排列StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse//

4、中序遍历StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//InOrderTraverse//后序遍历StatusHouOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(HouOrderTravers

5、e(T->lchild,Visit))if(HouOrderTraverse(T->rchild,Visit))if(Visit(T->data))returnOK;returnERROR;}elsereturnOK;}//HouOrderTraverseintLeafCount_BiTree(BiTreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeafCount_BiTree(T->lchild)+LeafCount_BiTree(T->rchil

6、d);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTreemain(){BiTreeT;intxz=3,xz1=4;do{printf("............二叉树..............");printf(".....1.按先序遍历输入二叉树.....");printf(".....2.输出二叉树...............");printf(".....3.退出.....................");printf("................................");scanf("%d",&xz);if(xz==

7、1)CreateBiTree(T);if(xz==2){printf("..........输出二叉树.............");printf("..........1.先序遍历输出.........");printf("..........2.中序遍历输出.........");printf("..........3.后序遍历输出.........");printf("...