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

1、实验报告课程名称数据结构实验项目实验三一创建一个二叉树并输出三种遍历结果系 别=一计算机学院_ _专 _班级/学号_学生姓名实验日期_成绩指导教师实验题目：实验三创建一个二叉树并输出三种遍历结果一、实验目的掌握二叉树存储结构；掌握并实现二叉树遍历的递归算法和非递归算法理解树及森林对二叉树的转换；理解二叉树的应用哈夫曼编码及 WPL 计算。二、实验内容以广义表或遍历序列形式创建一个二叉树，存储结构自选；输出先序、中序、后序遍历序列；二选一应用题：1)树和森林向二叉树转换；2)哈夫曼编码的应用问题。(应用型题目可替换上述前两项实验内容)三、设计与编码程序结构基本设计框架本实验用到的理论知识 遍历二

2、叉树，递归和非递归的方法(提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并 阐述自己的理解和想法)具体算法设计首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype，定义一棵二叉树，只需定义其根指针。然后以递归的先序遍历方法创建二叉树，函数为CreateTree(),在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应当输入一个特殊的字符(本算法为“#”)，表示左孩子或者右孩子为空。下一步，创建利用递归方法先序遍历二叉树的函数，函数为PreOrderTree()，创建非递归方法中序遍历二叉树的函数，函

3、数为InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数，函数为LaOrderTree()。(提示：该部分主要是利用C、C+等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用 流程图等描述)4) 编码#include#include#includetypedef char DataType;#define MaxSize 100typedef struct

4、 NodeDataType data; struct Node *lchild; struct Node *rchild; *BiTree,BitNode;void InitBitTree(BiTree *T);/*树的初始化*/void CreateBitTree(BiTree *T);/*按照先序输入字符序列递归创建二叉树*/void PreOrderTraverse(BiTree T); /*二叉树的先序遍历的 递归函数声明*/void InOrderTraverse(BiTree T); /*二叉树的中序遍历的 递归函数声明*/void PostOrderTraverse(BiTree

5、 T); /*二叉树的后序遍历的 递归函数声明*/void PreOrderTraverse2(BiTree T); /*二叉树的先序遍历的 非递归函数声明*/void InOrderTraverse2(BiTree T); /*二叉树的中序遍历的 非递归函数声明*/void PostOrderTraverse2(BiTree T); /*二叉树的后序遍历的 非递归函数声明*/void main()BiTree T,root; InitBitTree(&T);printf (根据输入二叉树的先序序列创建二叉树(#表示结 束)：n);CreateBitTree(&T);printf(二叉树的先序

6、序列：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(

7、T); printf(n);void InitBitTree(BiTree *T)*T=NULL;void CreateBitTree(BiTree *T) /*递归创建二叉树*/DataType ch; 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)

8、;子树*/void PreOrderTraverse(BiTree T)/*先序遍历二叉树的递归实现*/树*/树*/if(T)/*如果二叉树不为空*/ 树*/树*/if(T)/*如果二叉树不为空*/ printf(%2c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);/*访问根结点*/*先序遍历左子/*先序遍历右子void InOrderTraverse(BiTree T)/*中序遍历二叉树的递归实现*/if(T)/*如果二叉树不为空*/if(T)树*/树*/*中序遍历左子树*/树*/*中序遍历左子/*访问根结点*/

9、*中序遍历右子printf(%2c,T-data);InOrderTraverse(T-rchild);void PostOrderTraverse(BiTree T)/*后序遍历二叉树的递归实现*/if(T) /*如果二叉树不为空*/PostOrderTraverse(T-lchild);/*后序遍历左子树*/PostOrderTraverse(T-rchild);/*后序遍历右子树*/printf(%2c,T-data);/*访问根结点*/*定义一个栈，用于/*定义栈顶指针*/ /*定义一个结点的指针*/*初始化栈*/void PreOrderTraverse2(BiTree T) /*定

10、义一个栈，用于/*定义栈顶指针*/ /*定义一个结点的指针*/*初始化栈*/BiTree stackMaxSize; 存放结点的指针*/ int top;BitNode *p; top=0; p=T;while(p!=NULL|top0) /*如果p不空，访问根结/*如果p不空，访问根结/*访问根结点*/*将 p入栈*/*遍历左子树*/*如果栈不空*/*栈顶元素出栈*/*遍历右子树*/ printf(%2c,p-data); stacktop+=p; p=p-lchild; if(top0) p=stack-top; p=p-rchild;/*定义一个栈，用于/*定义栈顶指针*/ /*定义一个

11、结点的指针*/*初始化栈*/void InOrderTraverse2(BiTree T) /*定义一个栈，用于/*定义栈顶指针*/ /*定义一个结点的指针*/*初始化栈*/BiTree stackMaxSize; 存放结点的指针*/ int top;BitNode *p; top=0; p=T;while(p!=NULL|top0)/*如果p不空，访问根结/*将/*如果p不空，访问根结/*将p入栈*/*遍历左子树*/*如果栈不空*/*栈顶元素出栈*/*访问根结点*/*遍历右子树*/BiTree stackMaxSize;存放结点的指针*/int top;BitNode *p,*q;top=0

12、;p=T,q=NULL;while(p!=NULL|top0) while(p!=NULL) 根结点，遍历左子树*/stacktop+=p; p=p-lchild;if(top0)p=stacktop-1;/*定义一个栈，用于/*定义栈顶指针*/ /*定义结点的指针*/*初始化栈*/*初始化结点的指针*/*如果p不空，访问/*将p入栈*/*遍历左子树*/*如果栈不空*/*取栈顶元素*/while(p!=NULL)点，遍历左子树*/stacktop+=p; p=p-lchild;if(top0)p=stack-top;printf(%2c,p-data); p=p-rchild;void Pos

13、tOrderTraverse2(BiTree T) /*后序遍历二叉树的非递归实现*/ if(p-rchild=NULL|p-rchild=q)/*如果 p 没有右孩子结点，或右孩子结点已经访问过*/printf(%2c,p-data);/*访问根结点printf(%2c,p-data);/*访问根结点*/q=p;p=NULL;top-;elsep=p-rchild;(提示：该部分主要是将算法转化为C、C+程序，设计主函数完成 对各成员函数的调用；设计人机界面，每一步需要用户操作的提示 以及每一次用户操作产生的预期结果)四、运行与测试在调试程序的过程中遇到什么问题，是如何解决的 在调试程序的过程中，遇到最大的问题就是中序和后序不能正确表示 答案，最后发现是因为两个函数的错误导致。设计了哪些测试数据测试结果是什么abd#e#c#测试结果：前序：abdec中序：dbeac后序：debca3) 测试结果：前序：abdec中序：dbeac后序：debca3) 程序运行结果如何Habdec abdec帥 *C: YDDcuient s and Sett ings&dAinist ratorDebugXCpp 1. exe醍据输卜二处的先序斥列创逹二翼槟叶舂六结車； Exw的尢序疗