资源描述：
《二叉树的建立及遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、实验内容要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。二、实验环境操作系统和C语言系统三、源程序及注释：#include"stdio.h"#include"stdlib.h"typedefstructtree{chardata;structtree*lchild;structtree*rchild;}*Ptree;PtreecreateTree()//树的建立{charch;Ptreet;ch=
2、getchar();//输入二叉树数据if(ch=='')//判断二叉树是否为空t=NULL;else{t=(Ptree)malloc(sizeof(Ptree));//二叉树的生成t->data=ch;t->lchild=createTree();t->rchild=createTree();}returnt;}voidpreOrder(Ptreet)//先序遍历{if(t){printf("%c",t->data);preOrder(t->lchild);5preOrder(t->rchild);}}voidint
3、Order(Ptreet)//中序遍历{if(t){intOrder(t->lchild);printf("%c",t->data);intOrder(t->rchild);}}voidpostOrder(Ptreet)//后序遍历{if(t){postOrder(t->lchild);postOrder(t->rchild);printf("%c",t->data);}}intgetleaf(Ptreet)//求叶子数{inta,b;if(t==NULL)//判断是否为空return0;else{if(t->lchi
4、ld==NULL&&t->rchild==NULL)//只有一个根节点return1;else{a=getleaf(t->lchild);b=getleaf(t->rchild);returna+b;//返回叶子结点数}}}voidgetlevel(Ptreet,intl,intnum[])//求二叉树每层节点的个数{5if(t){num[l]++;getlevel(t->lchild,l+1,num);getlevel(t->rchild,l+1,num);}}intgetheight(Ptreet){inth1,h
5、2;if(t==NULL)//判断是否为空return0;else{h1=getheight(t->lchild);h2=getheight(t->rchild);//比较左右子树，得树的深度if(h1>h2)returnh1+1;elsereturnh2+1;}}voidmain(){intnum[10]={0};intheight;inti,a=0;Ptreet;printf("先序创建二叉树,用空格代表虚结点：");t=createTree();printf("前序遍历：");preOrder(t);prin
6、tf("");printf("中序遍历：");intOrder(t);printf("");printf("后序遍历：");postOrder(t);printf("");height=getheight(t);getlevel(t,1,num);for(i=1;i<=height;i++)5a=a+num[i];printf("结点个数：%d",a);printf("叶子总数：%d",getleaf(t));}四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：1、实验中经常会出现前
7、后字符不一致的情况，主要原因是自己比较马虎，平时编程比较少，遇到比较长的程序，就容易出错。解决方法：应多加练习编程，要仔细认真。2、用给的参考方法建立二叉树时；总是在编译和链接时无错，但无法运行。解决方法：参照课本，改用递归建立，程序就可正常运行。3、输入时出错，不会输入。解决办法：当结点左右孩子不全时，缺几个就要打几个空格。4、在计算结点数时，由于递归的知识学的不是很好，不会计算。解决方法：改为先计算每层结点数，然会再相加即可。六、思考题用非递归的方法也可建立二叉树：Ptree*CreateTree(){inti,j
8、,x;Ptree*q,*t,*s[30];printf("i,x");scanf("%d,%d",&i,&x);while((i!=0)&&(x!=0))5{q=(Ptree*)malloc(sizeof(Ptree));q->data=x;q->lchild=NULL;q->rchild=NULL;s[i]=q;//将指向结
