二叉树的操作.doc

1、二叉树操作实验日志实验题目 ：二叉树操作实验目的 ：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构， 完成二叉树的建立， 先序、 中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序程序的功能是采用二叉树链表存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作。如输入二叉树 ABD#CE#F#，链表示意图如下：ABCDEF2、添加中序和后序遍历算法/=LNR中序遍历 =void Inord er(BinTree T)if(T)Inorder(T-lchild);printf(%c,T-data);Inor

2、der(T-rchild);/=LRN后序遍历 =void Postorder(BinTree T)if(T)Postorder(T-lchild);Postorder(T-rchild);printf(%c,T-data);3、调试程序，设计一棵二叉树， 输入完全二叉树的先序序列， 用#代表虚结点（空指针），如 ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。四、源程序代码#includestdio.h#includestring.h#includestdlib.h#define Max 20/ 结点的最大个数typed ef struct no

3、d echar data;struct node *l chil d,*rchil d;BinTNode;/ 自定义二叉树的结点类型typed ef BinTNode *BinTree;/ 定义二叉树的指针int NodeNum,l eaf;/NodeNum为结点数， leaf 为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点#以示空指针的位置=BinTree CreatBinTree(void)BinTree T;char ch;if(ch=getchar()=#)return(NULL);/ 读入 #，返回空指针elseT=(BinTNode *)malloc(

4、sizeof(BinTNode);/ 生成结点T-data=ch;T-lchil d=CreatBinTree();/ 构造左子树T-rchil d=CreatBinTree();/ 构造右子树return(T);/=NLR先序遍历=void Preorder(BinTree T)if(T) printf(%c,T-data);/ 访问结点Preorder(T-lchil d);Preorder(T-rchild);/ 先序遍历左子树/ 先序遍历右子树/=LNR中序遍历 =void Inorder(BinTree T)if(T)Inorder(T-lchil d);printf(%c,T-da

5、ta);Inorder(T-rchild);/=LRN后序遍历 =void Postorder(BinTree T)if(T)Postorder(T-lchil d);Postorder(T-rchild);printf(%c,T-data);/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T)int hl,hr,max;if(T)hl=TreeDepth(T-lchil d);/ 求左深度hr=TreeDepth(T-rchild);/ 求右深度max=hlhr? hl:hr;/ 取左右深度的最大值NodeNum=NodeNum+1;/

6、求结点数if(hl=0&hr=0) leaf=leaf+1;/ 若左右深度为0 ，即为叶子。return(max+1);else return(0);/=利用 先进先出 （FIFO）队列，按层次遍历二叉树=void Level order(BinTree T)int front=0,rear=1;BinTNode *cqMax,*p;cq1=T;/ 定义结点的指针数组/ 根入队cqwhil e(front!=rear)front=(front+1)%NodeNum;p=cqfront;printf(%c,p-data);if(p-l chil d!=NULL)rear=(rear+1)%Nod

7、eNum;cqrear=p-lchil d;/ 出队/ 出队，输出结点的值/ 左子树入队if(p-rchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p-rchild;/ 右子树入队/=主函数=void main()BinTree root;int i,depth;printf(n);printf(Creat Bin_Tree；Input preorder:); /输入完全二叉树的先序序列，root=CreatBinTree();/用# 代表虚结点，如ABD#CE#F#/ 创建二叉树，返回根结点do / 从菜单中选择遍历方式，输入序号。printf(t* sel

8、ect *n);printf(t1: Preorder Traversaln);printf(t2: Iorder Traversaln);printf(t3: Postorder traversaln);printf(t4: PostTreeDepth,Node number,Leaf numbern);printf(t5: Level Depthn); /按层次遍历之前，先选择4，求出该树的结点数。printf(t0: Exitn);printf(t*n);scanf(%d,&i);/ 输入菜单序号（0-5 ）switch (i)case 1: printf(Print Bin_tree

9、Preorder: );Preorder(root);/ 先序遍历break;case 2: printf(Print Bin_Tree Inorder: );Inorder(root);/ 中序遍历break;case 3: printf(Print Bin_Tree Postorder: );Postorder(root);/ 后序遍历break;case 4: depth=TreeDepth(root);/ 求树的深度及叶子数printf(BinTree Depth=%dBinTree Nodenumber=%d,depth,NodeNum);printf(BinTree Leaf number=%d,leaf);break;case 5: printf(LevePrint Bin_Tree: );Level order(root);/ 按层次遍历break;default: exit(1);printf(n); whil e(i!=0);实验结果：（ 1）输入完全二叉树的先序序列ABD#CE#F#，程序运行结果如下：(2)先序序列 :(3)中序序列 :(4)后序序列 :(5)所有叶子及结点总数 :(6)按层次遍历序列 :心得体会：通过本次上机实验，我对编程又有了进一步的理解与认识。树型结