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

实验目的 编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。 实验内容 编程序并上机调试运行。 编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。 编写程序 /***********二叉树的遍历**************/ #includestdio.h #includestdlib.h typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; /*************************************************/ //按先序次序构建的二叉树链表 void CreatBiTree(BiTree *T) { char ch; if((ch=getchar())== ) *T=NULL; else { *T=(BiTNode*)malloc(sizeof(BiTNode)); 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); InOrderTraverse(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(\n\n); printf(中序遍历为:\n); InOrderTraverse(T); printf(\n\n); printf(后序遍历为:\n); PostOrderTraverse(T); printf(\n\n); getchar(); } 运行程序： 结果分析： 按先序输入的二叉树为ABC^^DE^G^^F^^^（^为空格） 该二叉树画成树形为： 其先序遍历为：ABCDEGF 其中序遍历为：CBEGDFA 其后序遍历为：CGEFDBA 可以看出运行结果是正确的。 程序解析： 1.首先是将程序的开头写好，因为后面要用到malloc，所以要有stdlib.h的声明。然后建立指针表struct BiTNode，定义其数据类型为char型，指针指向lchild,rchild，下一个指针为BiTNode. 按先序次序构建二叉树链表T。 函数CreatBiTree为构建二叉树链表的函数，T为指针，定义ch为字符型，如果输入为空格的话，指针就为空。否则，就新开辟一个单元，如果开辟失败，则强制错误退出，如果开辟成功，就让ch指向新单元的数据，然后再指向左孩子，再指向右孩子。 遇到的问题：一开始写的是以下程序： 没有指针形式，调试的时候没有错误，也可以执行，但是执行的时候就发生以下错误： 所以在T的前面加一个指针符号，因为要用指针指向新的结点，所以将后面的T都加上一个*，结果还是错误： 最后实在不知道错在哪，就上网百度了一下，发现是在指向左孩子和右孩子的时候要加一个地址符，因为函数CreatBi