二叉树的遍历(先序遍历、中序遍历、后序遍历全)实验报告

1、实验目的编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。实验内容编程序并上机调试运行。编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历 编写程序/*二叉树的遍历*/#include#includetypedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/按先序次序构建的二叉树链表void CreatBiTree(BiTree *T)char ch; if(ch=getchar()= ) *T=NULL;else *T=(BiTNode*)malloc(sizeof(BiTNode

2、); if(!(*T) exit(1);(*T)-data=ch; CreatBiTree(&(*T)-lchild); CreatBiTree(&(*T)-rchild);/先序遍历-递归算法void PreOrderTraverse(BiTree T) if(T) printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild);/中序遍历-递归算法void InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild); printf(%c,T-data);I

3、nOrderTraverse(T-rchild);/后序遍历-递归算法void PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild); printf(%c,T-data);/main 函数 void main() BiTree T;printf(请按先序次序输入二叉树中结点的值，空格字符表示空树:n”);CreatBiTree (&T);printf(n);printf(”先序遍历为:n);PreOrderTraverse(T);printf(nn);printf(中序遍历

4、为:n);InOrderTraverse(T);printf(nn);printf(”后序遍历为:n);PostOrderTraverse(T);printf(nn);getchar();运行程序:请按先序次序输入二叉树中结点的值，空格字符表示空树:ABC DE G F请按先序次序输入二叉树中结点的値，空格字符表示空树:OBC DE G F先序遍历为=ABCDEGF中序遍历为；GBEGDFfi后序遍历为:CGEFDBfiPpess any 1吕屮 to continue结果分析：按先序输入的二叉树为ABCAADEAGAAFAAA （人为空格） 该二叉树画成树形为：其先序遍历为：ABCDEGF

5、其中序遍历为：CBEGDFA 其后序遍历为：CGEFDBA 可以看出运行结果是正确的。程序解析：1.首先是将程序的开头写好，因为后面要用到malloc，所以要有stdlib.h的 声明。然后建立指针表struct BiTNode，定义其数据类型为char型，指针指向 lchild,rchild，下一个指针为 BiTNode./*2_5!寸的盖豪盖序芳序芳序芳序芳序芳1* /itinclu(leitinclu(letypedeF struct BiTNodechar data;struct BiTHode *lchild 9*rcliild ;BiTHode,*BiTree;2按先序次序构建二叉

6、树链表To/ *穽穽養 *芈拦琴芈穽壬*養軒養琴提軒穽費来强*費餐餐釜餐穽餐穽餐蚤餐豊蚤关at/按先序次昂构建的二翼树链表uoid CreatBiTree(BiTree *T)char ch;if (ch = getctiar()=)*T=HULL;elsedata=ch;CreatBiTrpp(E；(*T)-lctiild);CreatBiTr&(&(*T)-rctiild);函数CreatBiTree为构建二叉树链表的函数，T为指针，定义ch为字符型，如果 输入为空格的话，指针就为空。否则，就新开辟一个单元，如果开辟失败，则强 制错误退出，如果开辟成功，就让ch指向新单元的数据，然后再指向

7、左孩子， 再指向右孩子。遇到的问题：一开始写的是以下程序：void CreatBiTree(BiTree T)char ch;iF(Cch=getchar()=)T=NULL;elsedata=ch;CreatBiTreeCT-Mchild); CreatBiTree(T-rchild);没有指针形式，调试的时候没有错误，也可以执行，但是执行的时候就发生以下错误:匸口空格字符表示空树:洗序遍历为:匸口空格字符表示空树:洗序遍历为:i| y.exe已停止工作凸现了一问题导錢程序亭止正常工惟.请关诩该程 序4关闭程序所以在T的前面加一个指针符号，因为要用指针指向新的结点，所以将后面的T都加上一 个

8、*，结果还是错误：P青按先序次序输入二叉树中结点的值，空格字符表示空树:HBC DE G F叵2| y-exe已停止工作口现了一r问题r导毀程序停止正帛工作.请关闭谚程 序4lchild);CreatBiTree(fe(*T)-rchild):这样结果就对了。3建立先序遍历函数。先序遍历一递归算法uoid PreOrderTrauersetBiTree T)data);PreOrderTrauersefT-lchild):PreOrderTrauer5e(T-rchild):用递归算法建立先序遍历的函数PreOrderTraverse,如果T不为0,则先输出其根，再 输出左孩子，在输出右孩子。

9、这种方法为递归算法，以下的中序，后序均与此类似。4建立中序遍历函数。/卑卑里卑舉卑关罢黑黑*罢罢黑里共*莫案穽弹莫黑器*器*弹*器*芈琴崔琴峯琴芈琴鉴芈聲芈聲誓弹豊餐共/ 中序遍历一递归算袪.void InOrderTrauerse(BiTree T)ifT)lchild);printf ,T-data);InOrderTraverse(T-rchild);用递归算法建立中序遍历函数InOrderTraverse，其函数的写法与先序的类似，先输出其 左孩子，再输出根节点，再输出其右孩子。书上的中序遍历用的是非递归算法，非递归算法 用的是栈，所以还要建栈，入栈，出栈等函数，相较于递归算法麻烦很多

10、。5建立后序遍历函数。/聲鑒擊睾事鑒睾案舉关舉舉舉卑里关里关舉关罢黑里罢罢里黑黑里罢穽穽琴穽穽藝穽穽穽穽*琴关#关*#/ 后序遍历一递归算袪.uoid PostOrderTraverse(BiTree T)if(T)lchild);PostOrderTrauerse(T-rchild); printf(c,T-data);用递归算法建立后序遍历函数PostOrderTraverse,先输出其左孩子，再输出其右孩子，再输 出其根节点。以C的格式输出。6建立main函数。/*#*#*#*#*#*#*#*/m日in函数void main()BiTree T;Printff请按先序次序输入二叉树中结点的值，空格字符表示空W：n-);CreatBiTree(&T); printFCXn);PintFC先序遍历为An);PreOrderTrauerseCT);printf (,nn,)jPrintf(中序遍历