二叉树遍历实验报告.doc

1实验题目二叉树的建立与遍历问题描述建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。2需求分析（1）输入的形式和输入值的范围：以字符形式按先序遍历输入（2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出(3) 程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。(4) 测试数据：ABCDEGF（其中表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA3概要设计（1）struct btnodechar data; 数据struct btnode *Lchild;左子数指针struct btnode *Rchild; 右子数指针;struct btnode *createbt(struct btnode *bt ) 初始条件：空二叉树存在操作结果：先序建立二叉树void preOrder(struct btnode *bt)初始条件：二叉树存在递归先序遍历二叉树void preOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归先序遍历void midOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归中序遍历void midOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归中序遍历void postOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归后序遍历void postOrder1 (struct btnode *bt)初始条件：二叉树存在操作结果：非递归后序遍历void main() 主函数（2）void main() 主函数*createbtpreOrderpreOrder1midOrdermidOrder1postOrderpostOrder14详细设计struct btnodechar data;struct btnode *Lchild;struct btnode *Rchild;struct btnode *createbt(struct btnode *bt )输入结点数据c检查存储空间将c赋给结点参数p递归建立左子树递归建立右子树void preOrder(struct btnode *bt)判断树是否为空输出根结点数data递归遍历左子树递归遍历右子树void preOrder1(struct btnode *bt)定义栈，结点参数pWhile(栈或p是否为空)While(p!=null)输出根结点数data将根结点压栈遍历左子树提取栈顶元素值栈顶元素出栈访问右子树void midOrder(struct btnode *bt)判断树是否为空递归遍历左子树输出根结点数data递归遍历右子树void midOrder1(struct btnode *bt)定义栈，结点参数pWhile(栈或p是否为空)While(p!=null)将根结点压栈遍历左子树提取栈顶元素值输出根结点数data栈顶元素出栈访问右子树void postOrder(struct btnode *bt)判断树是否为空递归遍历左子树递归遍历右子树输出根结点数datavoid postOrder1 (struct btnode *bt)定义栈，结点参数p,prebt入栈While(栈或p是否为空)提取栈顶元素值if判断p是否为空或是pre的根结点输出根结点数data栈顶元素出栈栈顶元素p赋给pre记录else if右结点非空将右结点压栈 if左结点将左结点压栈void main() struct btnode *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、附录#include #include#include #include#includeusing namespace std;struct btnodechar data;struct btnode *Lchild;struct btnode *Rchild;struct btnode *createbt(struct btnode *bt )/先序建立二叉树char c;c=getchar();if(c= )/如果输入为空，则子树为空bt=NULL;elseif(!(bt=(struct btnode *)malloc(sizeof(struct btnode)/检验bt空间分配是否成功printf(error!);bt-data=c;bt-Lchild=createbt(bt-Lchild);/递归建立左子树bt-Rchild=createbt(bt-Rchild); /递归建立右子树return(bt);void preOrder(struct btnode *bt)/递归先序遍历if(bt!=NULL)printf(%c,bt-data); preOrder(bt-Lchild); preOrder(bt-Rchild);void preOrder1(struct btnode *bt)/非递归先序遍历int i=0;struct btnode *p;stack 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;/访问右子树void midOrder(struct btnode *bt)/递归中序遍历if(bt!=NULL)midOrder(bt-Lchild); printf(%c,bt-data); midOrder(bt-Rchild);void midOrder1(struct btnode *bt)/非递归中序遍历int i=0;struct btnode *p;stack 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;void postOrder(struct btnode *bt)/递归后序遍历if(bt!=NULL) postOrder(bt-Lchild); postOrder(bt-Rchild); printf(%c,bt-data); void postOrder1 (struct btnode *bt)/非递归后序遍历struct btnode *p,*pre=NULL; stack 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;elseif(p-Rchild!=NULL) s.push(p-Rchild);/先将右结点压栈if(p-Lchild!=NULL)s.push(p-Lchild);/后将左结点压栈，因为先入后出void main() /主函数struct btnode *root=NULL;root=createbt(root);printf(先序递归遍历结果：); preOrder(root); printf(中序递归遍历结果：); midOrder(root);printf(后序递归