创建一个二叉树并输出三种遍历结果

实验报告课程名称数据结构实验项目实验三--创建一个二叉树并输出三种遍历结果系别____计算机学院_______专业______班级/学号___________学生姓名_________实验日期_成绩_______________________指导教师实验题目：实验三------创建一个二叉树并输出三种遍历结果一、实验目的1)掌握二叉树存储结构；2)掌握并实现二叉树遍历的递归算法和非递归算法；3)理解树及森林对二叉树的转换；4)理解二叉树的应用—哈夫曼编码及WPL计算。二、实验内容1)以广义表或遍历序列形式创建一个二叉树，存储结构自选；2)输出先序、中序、后序遍历序列；3)二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。（应用型题目可替换上述前两项实验内容）三、设计与编码1)程序结构基本设计框架（提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示）2)本实验用到的理论知识遍历二叉树，递归和非递归的方法（提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法）3)具体算法设计（1）首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype，定义一棵二叉树，只需定义其根指针。（2）然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应当输入一个特殊的字符（本算法为“#”），表示左孩子或者右孩子为空。（3）下一步，创建利用递归方法先序遍历二叉树的函数，函数为PreOrderTree()，创建非递归方法中序遍历二叉树的函数，函数为InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数，函数为LaOrderTree()。（提示：该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述）4)编码#includestdio.h#includemalloc.h#includestdlib.htypedefcharDataType;#defineMaxSize100typedefstructNode{DataTypedata;structNode*lchild;structNode*rchild;}*BiTree,BitNode;voidInitBitTree(BiTree*T);/*树的初始化*/voidCreateBitTree(BiTree*T);/*按照先序输入字符序列递归创建二叉树*/voidPreOrderTraverse(BiTreeT);/*二叉树的先序遍历的递归函数声明*/voidInOrderTraverse(BiTreeT);/*二叉树的中序遍历的递归函数声明*/voidPostOrderTraverse(BiTreeT);/*二叉树的后序遍历的递归函数声明*/voidPreOrderTraverse2(BiTreeT);/*二叉树的先序遍历的非递归函数声明*/voidInOrderTraverse2(BiTreeT);/*二叉树的中序遍历的非递归函数声明*/voidPostOrderTraverse2(BiTreeT);/*二叉树的后序遍历的非递归函数声明*/voidmain(){BiTreeT,root;InitBitTree(&T);printf(根据输入二叉树的先序序列创建二叉树('#'表示结束)：\n);CreateBitTree(&T);printf(二叉树的先序序列：\n);printf(递归：\t);PreOrderTraverse(T);printf(\n);printf(非递归：);PreOrderTraverse2(T);printf(\n);printf(二叉树的中序序列：\n);printf(递归：\t);InOrderTraverse(T);printf(\n);printf(非递归：);InOrderTraverse2(T);printf(\n);printf(二叉树的后序序列：\n);printf(递归：\t);PostOrderTraverse(T);printf(\n);printf(非递归：);PostOrderTraverse2(T);printf(\n);}voidInitBitTree(BiTree*T){*T=NULL;}voidCreateBitTree(BiTree*T)/*递归创建二叉树*/{DataTypech;scanf(%c,&ch);if(ch=='#')*T=NULL;else{*T=(BiTree)malloc(sizeof(BitNode));/*生成根结点*/if(!(*T))exit(-1);(*T)-data=ch;CreateBitTree(&((*T)-lchild));/*构造左子树*/CreateBitTree(&((*T)-rchild));/*构造右子树*/}}voidPreOrderTraverse(BiTreeT)/*先序遍历二叉树的递归实现*/{if(T)/*如果二叉树不为空*/{printf(%2c,T-data);/*访问根结点*/PreOrderTraverse(T-lchild);/*先序遍历左子树*/PreOrderTraverse(T-rchild);/*先序遍历右子树*/}}voidInOrderTraverse(BiTreeT)/*中序遍历二叉树的递归实现*/{if(T)/*如果二叉树不为空*/{InOrderTraverse(T-lchild);/*中序遍历左子树*/printf(%2c,T-data);/*访问根结点*/InOrderTraverse(T-rchild);/*中序遍历右子树*/}}voidPostOrderTraverse(BiTreeT)/*后序遍历二叉树的递归实现*/{if(T)/*如果二叉树不为空*/{PostOrderTraverse(T-lchild);/*后序遍历左子树*/PostOrderTraverse(T-rchild);/*后序遍历右子树*/printf(%2c,T-data);/*访问根结点*/}}voidPreOrderTraverse2(BiTreeT)/*先序遍历二叉树的非递归实现*/{BiTreestack[MaxSize];/*定义一个栈，用于存放结点的指针*/inttop;/*定义栈顶指针*/BitNode*p;/*定义一个结点的指针*/top=0;/*初始化栈*/p=T;while(p!=NULL||top0){while(p!=NULL)/*如果p不空，访问根结点，遍历左子树*/{printf(%2c,p-data);/*访问根结点*/stack[top++]=p;/*将p入栈*/p=p-lchild;/*遍历左子树*/}if(top0)/*如果栈不空*/{p=stack[--top];/*栈顶元素出栈*/p=p-rchild;/*遍历右子树*/}}}voidInOrderTraverse2(BiTreeT)/*中序遍历二叉树的非递归实现*/{BiTreestack[MaxSize];/*定义一个栈，用于存放结点的指针*/inttop;/*定义栈顶指针*/BitNode*p;/*定义一个结点的指针*/top=0;/*初始化栈*/p=T;while(p!=NULL||top0){while(p!=NULL)/*如果p不空，访问根结点，遍历左子树*/{stack[top++]=p;/*将p入栈*/p=p-lchild;/*遍历左子树*/}if(top0)/*如果栈不空*/{p=stack[--top];/*栈顶元素出栈*/printf(%2c,p-data);/*访问根结点*/p=p-rchild;/*遍历右子树*/}}}voidPostOrderTraverse2(BiTreeT)/*后序遍历二叉树的非递归实现*/{BiTreestack[MaxSize];/*定义一个栈，用于存放结点的指针*/inttop;/*定义栈顶指针*/BitNode*p,*q;/*定义结点的指针*/top=0;/*初始化栈*/p=T,q=NULL;/*初始化结点的指针*/while(p!=NULL||top0){while(p!=NULL)/*如果p不空，访问根结点，遍历左子树*/{stack[top++]=p;/*将p入栈*/p=p-lchild;/*遍历左子树*/}if(top0)/*如果栈不空*/{p=stack[top-1];/*取栈顶元素*/if(p-rchild==NULL||p-rchild==q)/*如果p没有右孩子结点，或右孩子结点已经访问过*/{printf(%2c,p-data);/*访问根结点*/q=p;p=NULL;top--;}elsep=p-rchild;}}}（提示：该部分主要是将算法转化为C、C++程序，设计主函数完成对各成员函数的调用；设计人机界面，每一步需要用户操作的提示以及每一次用户操作产生的预期结果）四、运行与测试1)在调试程序的过程中遇到什么问题，是如何解决的？在调试程序的过程中，遇到最大的问题就是中序和后序不能正确表示答案，最后发现是因为两个函数的错误导致。2)设计了哪些测试数据？测试结果是什么？abd##e##c##测试结果：前序：abdec中序：dbeac后序：debca3)程序运行结果如何？五、总结与心得理解了二叉树的逻辑特点和二叉树的性质；掌握了二叉树的二叉链表存储结构，以及二叉树的遍历算法的递归与非递归实现。虽完成了实验，但也需日后多多练习。实验完成后的总结与思考，或者谈收获。（注意此部分要结合自己的题目来阐述说明）