实验三：二叉树遍历算法的设计

1、学校代码：10128学 号：201220905048 数据结构实验报告（题 目：二叉树遍历算法的设计学生姓名：孙跃学 院：理学院系 别：数学系专 业：信息与计算科学班 级：信计12-2任课教师：杜雅娟二一四年十一月2一、实验目的通过理解二叉树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。二、程序分析本演示程序用Visual C+ 6.0编写，完成二叉树的遍历算法。1.按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树t；2.对二叉树t作先序、中序、后序遍历的递归算法，输出结果；3.计算二叉树t的深度，输出结果；4.计算二叉树t的叶子结点个数。三、程序设计在开头定义了

2、二叉树的链式存储结构，此处采用了每个结点中设置三个域， 即值域，左指针域和右指针域。1、 二叉树的建立链式存储结构，首先typedef struct BiTNode：定义二叉树的链式存储结构，此处采用了每个结点中设置三个域，data：即值域，*lchild：左指针域和rchild：右指针域；2、 二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树；3、 二叉树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树；4、 二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点；5、 求二叉树的深度

3、：首先判断二叉树是否为空，若为空则此二叉树的深度为0。否则，就先别求出左右子树的深度并进行比较，取较大的+1就为二叉树的深度；6、 二叉树的求叶子结点的个数计算；先分别求得左右子树中各叶子结点个数，再计算出两者之和即为二叉树的叶子结点数；7、 主函数：主函数中分别调用各函数。四、 实验程序#include<stdio.h>#include<malloc.h>#define M 20typedef struct nodechar data;struct node *lchild,*rchild;BTnode;BTnode * create()BTnode *t;char

4、ch;scanf("%c",&ch);if(ch='#')t=NULL;elset=(BTnode*)malloc(sizeof(BTnode);t->data=ch;t->lchild=create();t->rchild=create();return t;void Inordertraverse(BTnode *t)int i=0;BTnode *p,*sM;p=t;dowhile(p!=NULL)si+=p;p=p->lchild;if(i>0)p=s-i;printf("%ct",p->

5、;data);p=p->rchild;while(i>0|p!=NULL);void Preordertraverse(BTnode *t)int i=0;BTnode *p,*sM;p=t;dowhile(p!=NULL)printf("%ct",p->data);if(p->rchild!=NULL)si+=p->rchild;p=p->lchild;if(i>0)p=s-i;while(i>0|p!=NULL);void Postordertraverse(BTnode *t)int slM;int i=0;BTnode

6、 *p,*sM;p=t;dowhile(p!=NULL)si=p;sli+=0;p=p->lchild;while(i>0&&sli-1=1)p=s-i;printf("%ct",p->data);free(p);if(i>0)sli-1=1;p=si-1;p=p->rchild;while(i>0);printf("n");int high(BTnode *t)int h,lh,rh;if(!t)return 0;lh=high(t->lchild);rh=high(t->rchild);

7、h=lh?lh+1:rh+1;return h;int leafcount(BTnode *t,int &n)BTnode *p=t;if(p)if(p->lchild=NULL&&p->rchild=NULL)n+;n=leafcount(p->lchild,n);n=leafcount(p->rchild,n);return n;void main()BTnode *t;int n=0;printf("input data: ");t=create();printf("n Preordertraverse: &q

8、uot;);Preordertraverse(t);printf("n Inordertraverse: ");Inordertraverse(t);printf("n the left's number: ");n=leafcount(t,n);printf("%d",n);printf("n the high of the bintree: ");n=high(t);printf("%d",n);printf("n Postordertraverse: ");Po