二叉树遍历实验报告.doc

《二叉树遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.1．实验题目二叉树的建立与遍历[问题描述]　　建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。2．需求分析（1）输入的形式和输入值的范围：以字符形式按先序遍历输入（2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出(3)程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。(4)测试数据：ABCффDEфGффFффф（其中ф表示空格字符）　　则输出结果为先序：ABCDEGF　　中序：CBEGDFA　　后序：CGBFDBA3

2、．概要设计（1）structbtnode{chardata;数据structbtnode*Lchild;左子数指针structbtnode*Rchild;右子数指针};structbtnode*createbt(structbtnode*bt)初始条件：空二叉树存在操作结果：先序建立二叉树voidpreOrder(structbtnode*bt)初始条件：二叉树存在递归先序遍历二叉树voidpreOrder1(structbtnode*bt)初始条件：二叉树存在操作结果：非递归先序遍历voidmidOrder(st

3、ructbtnode*bt)初始条件：二叉树存在操作结果：递归中序遍历voidmidOrder1(structbtnode*bt)初始条件：二叉树存在操作结果：非递归中序遍历voidpostOrder(structbtnode*bt)初始条件：二叉树存在操作结果：递归后序遍历voidpostOrder1(structbtnode*bt)初始条件：二叉树存在操作结果：非递归后序遍历voidmain()主函数（2）voidmain()主函数..{*createbtpreOrderpreOrder1midOrdermid

4、Order1postOrderpostOrder1}4．详细设计structbtnode{chardata;structbtnode*Lchild;structbtnode*Rchild;};structbtnode*createbt(structbtnode*bt){输入结点数据c检查存储空间将c赋给结点参数p递归建立左子树递归建立右子树}voidpreOrder(structbtnode*bt){判断树是否为空输出根结点数data递归遍历左子树递归遍历右子树}voidpreOrder1(structbtnode

5、*bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){输出根结点数data将根结点压栈遍历左子树}提取栈顶元素值栈顶元素出栈访问右子树}voidmidOrder(structbtnode*bt){判断树是否为空递归遍历左子树..输出根结点数data递归遍历右子树}voidmidOrder1(structbtnode*bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){将根结点压栈遍历左子树}提取栈顶元素值输出根结点数data栈顶元素出栈访问右子树}

6、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(ro

7、ot);preOrder(root);midOrder(root);postOrder(root);preOrder1(root);midOrder1(root)；postOrder1(root);}5.调试分析（1）先序建立二叉树时，虽用到递归建左右子树，但没有把他们赋值给根节点的左右指针，造成二叉树脱节。（2）非递归后序遍历时，未考虑到所有条件，只考虑节点的左右结点是否为空，而未考虑结点是否是前一个遍历结点的根节点且不为空。（3）用栈实现非递归遍历。..6.用户使用说明运行环境为vc6.0程序执行后在命令窗口中

8、输入测试数据然后enter7.测试结果8、附录#include#include#include#include#includeusingnamespacestd;structbtnode{chardata;structbtnode*Lchild;structbtnod