二叉树遍历实验报告

1．实验题目二叉树的建立与遍历[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。2．需求分析（1）输入的形式和输入值的范围：以字符形式按先序遍历输入（2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出(3)程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。(4)测试数据：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA3．概要设计（1）structbtnode{chardata;数据structbtnode*Lchild;左子数指针structbtnode*Rchild;右子数指针};structbtnode*createbt(structbtnode*bt)初始条件：空二叉树存在操作结果：先序建立二叉树voidpreOrder(structbtnode*bt)初始条件：二叉树存在递归先序遍历二叉树voidpreOrder1(structbtnode*bt)初始条件：二叉树存在操作结果：非递归先序遍历voidmidOrder(structbtnode*bt)初始条件：二叉树存在操作结果：递归中序遍历voidmidOrder1(structbtnode*bt)初始条件：二叉树存在操作结果：非递归中序遍历voidpostOrder(structbtnode*bt)初始条件：二叉树存在操作结果：递归后序遍历voidpostOrder1(structbtnode*bt)初始条件：二叉树存在操作结果：非递归后序遍历voidmain()主函数（2）voidmain()主函数{*createbtpreOrderpreOrder1midOrdermidOrder1postOrderpostOrder1}4．详细设计structbtnode{chardata;structbtnode*Lchild;structbtnode*Rchild;};structbtnode*createbt(structbtnode*bt){输入结点数据c检查存储空间将c赋给结点参数p递归建立左子树递归建立右子树}voidpreOrder(structbtnode*bt){判断树是否为空输出根结点数data递归遍历左子树递归遍历右子树}voidpreOrder1(structbtnode*bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){输出根结点数data将根结点压栈遍历左子树}提取栈顶元素值栈顶元素出栈访问右子树}voidmidOrder(structbtnode*bt){判断树是否为空递归遍历左子树输出根结点数data递归遍历右子树}voidmidOrder1(structbtnode*bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){将根结点压栈遍历左子树}提取栈顶元素值输出根结点数data栈顶元素出栈访问右子树}voidpostOrder(structbtnode*bt){判断树是否为空递归遍历左子树递归遍历右子树输出根结点数data}voidpostOrder1(structbtnode*bt){定义栈，结点参数p,prebt入栈While(栈或p是否为空){提取栈顶元素值if判断p是否为空或是pre的根结点输出根结点数data栈顶元素出栈栈顶元素p赋给pre记录elseif右结点非空将右结点压栈if左结点将左结点压栈}}voidmain(){structbtnode*root=NULL;root=createbt(root);preOrder(root);midOrder(root);postOrder(root);preOrder1(root);midOrder1(root)；postOrder1(root);}5.调试分析（1）先序建立二叉树时，虽用到递归建左右子树，但没有把他们赋值给根节点的左右指针，造成二叉树脱节。（2）非递归后序遍历时，未考虑到所有条件，只考虑节点的左右结点是否为空，而未考虑结点是否是前一个遍历结点的根节点且不为空。（3）用栈实现非递归遍历。6.用户使用说明运行环境为vc6.0程序执行后在命令窗口中输入测试数据然后enter7.测试结果8、附录#includestdio.h#includestdlib.h#includeiostream#includestring.h#includestackusingnamespacestd;structbtnode{chardata;structbtnode*Lchild;structbtnode*Rchild;};structbtnode*createbt(structbtnode*bt)//先序建立二叉树{charc;c=getchar();if(c=='')//如果输入为空，则子树为空{bt=NULL;}else{if(!(bt=(structbtnode*)malloc(sizeof(structbtnode))))//检验bt空间分配是否成功printf(error!);bt-data=c;bt-Lchild=createbt(bt-Lchild);//递归建立左子树bt-Rchild=createbt(bt-Rchild);//递归建立右子树}return(bt);}voidpreOrder(structbtnode*bt)//递归先序遍历{if(bt!=NULL){printf(%c,bt-data);preOrder(bt-Lchild);preOrder(bt-Rchild);}}voidpreOrder1(structbtnode*bt)//非递归先序遍历{inti=0;structbtnode*p;stackstructbtnode*s;定义栈p=bt;while(p!=NULL||!s.empty()){while(p!=NULL){printf(%c,p-data);s.push(p);//将根结点压栈p=p-Lchild;//遍历左子树}if(!s.empty()){p=s.top();//提取栈顶元素值s.pop();//栈顶元素出栈p=p-Rchild;//访问右子树}}}voidmidOrder(structbtnode*bt)//递归中序遍历{if(bt!=NULL){midOrder(bt-Lchild);printf(%c,bt-data);midOrder(bt-Rchild);}}voidmidOrder1(structbtnode*bt)//非递归中序遍历{inti=0;structbtnode*p;stackstructbtnode*s;p=bt;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-Lchild;}if(!s.empty()){p=s.top();printf(%c,p-data);s.pop();p=p-Rchild;}}}voidpostOrder(structbtnode*bt)//递归后序遍历{if(bt!=NULL){postOrder(bt-Lchild);postOrder(bt-Rchild);printf(%c,bt-data);}}voidpostOrder1(structbtnode*bt)//非递归后序遍历{structbtnode*p,*pre=NULL;stackstructbtnode*s;s.push(bt);while(!s.empty()){p=s.top();if((p-Lchild==NULL&&p-Rchild==NULL)||(pre!=NULL&&(pre==p-Lchild||pre==p-Rchild)))//判断p是否为空或是pre的根结点{printf(%c,p-data);s.pop();pre=p;}else{if(p-Rchild!=NULL)s.push(p-Rchild);//先将右结点压栈if(p-Lchild!=NULL)s.push(p-Lchild);//后将左结点压栈，因为先入后出}}}voidmain()//主函数{structbtnode*root=NULL;root=createbt(root);printf(先序递归遍历结果：);preOrder(root);printf(中序递归遍历结果：);midOrder(root);printf(后序递归遍历结果：);postOrder(root);printf(先序非递归遍历结果：);preOrder1(root);printf(中序非递归遍历结果：);midOrder1(root);printf(后序非递归遍历结果：);postOrder1(root);}