二叉树的建立及遍历.doc

1、 实验内容要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。二、实验环境操作系统和C语言系统3、 源程序及注释：#include stdio.h #include stdlib.h typedef struct tree char data; struct tree *lchild; struct tree *rchild; *Ptree; Ptree createTree() /树的建立 char ch; Ptree t; ch=getchar(); /输入二叉树数据 if(ch= ) /判断二叉树是否为空 t=NULL; else t=(Ptree)malloc(sizeof(Ptree); /二叉树的生成 t-data=ch; t-lchild=createTree(); t-rchild=createTree(); return t; void preOrder(Ptree t) /先序遍历 if(t) printf(%c,t-data); preOrder(t-lchild); preOrder(t-rchild); void intOrder(Ptree t) /中序遍历 if(t) intOrder(t-lchild); printf(%c,t-data); intOrder(t-rchild); void postOrder(Ptree t) /后序遍历 if(t) postOrder(t-lchild); postOrder(t-rchild); printf(%c,t-data); int getleaf(Ptree t) /求叶子数 int a,b; if(t=NULL) /判断是否为空 return 0; else if(t-lchild=NULL&t-rchild=NULL) /只有一个根节点 return 1; else a=getleaf(t-lchild); b=getleaf(t-rchild); return a+b; /返回叶子结点数 void getlevel(Ptree t,int l,int num) /求二叉树每层节点的个数 if(t) numl+; getlevel(t-lchild,l+1,num); getlevel(t-rchild,l+1,num); int getheight(Ptree t) int h1,h2; if(t=NULL) /判断是否为空 return 0; else h1=getheight(t-lchild); h2=getheight(t-rchild); /比较左右子树，得树的深度 if(h1h2)returnh1+1; elsereturnh2+1; void main() int num10=0; int height; int i,a=0; Ptree t; printf(先序创建二叉树,用空格代表虚结点：n); t=createTree(); printf(前序遍历：); preOrder(t) ; printf(n); printf(中序遍历：); intOrder(t); printf(n); printf(后序遍历：); postOrder(t); printf(n); height=getheight( t) ; getlevel(t,1,num); for(i=1;idata=x;q- lchild=NULL; q- rchild=NULL; si=q; /将指向结点的指针存入si if (i=1)t=q;else/t指向根结点 j=i/2; /j为双亲结点编号 if(i%2)=0 ) sj-lchild=si; else sj-rchild=si; printf(i,x n);scanf(%d%d,&i,&x); return(t); /返回根结点7、 实验总结： 通过这次实验使我发现我是编程能力较差，而且对于二叉树的知识学的也不是很好。使得在编程时，发现有很多地方不是很懂，