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

.实验报告课程名称数据构造 实验工程实验三-创立一个二叉树并输出三种遍历结果系 别_ _计算机学院 _ _专 业_ _班级/*_学生 _实验日期 _成 绩 _指导教师实验题目：实验三-创立一个二叉树并输出三种遍历结果一、 实验目的1) 掌握二叉树存储构造；2) 掌握并实现二叉树遍历的递归算法和非递归算法；3) 理解树及森林对二叉树的转换；4) 理解二叉树的应用哈夫曼编码及WPL计算。二、 实验容1) 以广义表或遍历序列形式创立一个二叉树，存储构造自选；2) 输出先序、中序、后序遍历序列；3) 二选一应用题：1树和森林向二叉树转换；2哈夫曼编码的应用问题。应用型题目可替换上述前两项实验容三、 设计与编码1) 程序构造根本设计框架提示：请根据所选定题目，描述程序的根本框架，可以用流程图、界面描述图、框图等来表示2) 本实验用到的理论知识遍历二叉树，递归和非递归的方法提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法3) 具体算法设计（1） 首先，定义二叉树的存储构造为二叉链表存储，每个元素的数据类型Elemtype，定义一棵二叉树，只需定义其根指针。（2） 然后以递归的先序遍历方法创立二叉树，函数为CreateTree()，在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应当输入一个特殊的字符本算法为"#，表示左孩子或者右孩子为空。（3） 下一步，创立利用递归方法先序遍历二叉树的函数，函数为PreOrderTree()，创立非递归方法中序遍历二叉树的函数，函数为InOrderTree()，中序遍历过程是：从二叉树的根节点开场，沿左子树向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并；然后再用上述过程遍历右子树，依次类推，指导整棵二叉树全部完毕。创立递归方法后序遍历二叉树的函数，函数为LaOrderTree()。提示：该局部主要是利用C、C+等完成数据构造定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述4) 编码#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef char DataType;#define Ma*Size 100typedef struct 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 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("二叉树的先序序列：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");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) e*it(-1); (*T)->data=ch; CreateBitTree(&(*T)->lchild); /*构造左子树*/ CreateBitTree(&(*T)->rchild); /*构造右子树*/ void PreOrderTraverse(BiTree T)/*先序遍历二叉树的递归实现*/ if(T)/*如果二叉树不为空*/ printf("%2c",T->data); /*根结点*/ PreOrderTraverse(T->lchild);/*先序遍历左子树*/ PreOrderTraverse(T->rchild); /*先序遍历右子树*/ void InOrderTraverse(BiTree T)/*中序遍历二叉树的递归实现*/ if(T)/*如果二叉树不为空*/InOrderTraverse(T->lchild);/*中序遍历左子树*/ 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)/*先序遍历二叉树的非递归实现*/BiTree stackMa*Size; /*定义一个栈，用于存放结点的指针*/int top; /*定义栈顶指针*/BitNode *p; /*定义一个结点的指针*/top=0;/*初始化栈*/p=T;while(p!=NULL|top>0)while(p!=NULL) /*如果p不空，根结点，遍历左子树*/printf("%2c",p->data); /*根结点*/stacktop+=p; /*将p入栈*/p=p->lchild; /*遍历左子树*/if(top>0) /*如果栈不空*/p=stack-top; /*栈顶元素出栈*/p=p->rchild;/*遍历右子树*/void InOrderTraverse2(BiTree T)/*中序遍历二叉树的非递归实现*/BiTree stackMa*Size; /*定义一个栈，用于存放结点的指针*/int top; /*定义栈顶指针*/BitNode *p; /*定义一个结点的指针*/top=0;/*初始化栈*/p=T;while(p!=NULL|top>0)while(p!=NULL) /*如果p不空，根结点，遍历左子树*/stacktop+=p; /*将p入栈*/p=p->lchild; /*遍历左子树*/if(top>0) /*如果栈不空*/p=stack-top; /*栈顶元素出栈*/printf("%2c",p->data); /*根结点*/p=p->rchild;/*遍历右子树*/void PostOrderTraverse2(BiTree T)/*后序遍历二叉树的非递归实现*/BiTree stackMa*Size; /*定义一个栈，用于存放结点的指针*/int top; /*定义栈顶指针*/BitNode *p,*q; /*定义结点的指针*/top=0;/*初始化栈*/p=T,q=NULL; /*初始化结点的指针*/while(p!=NULL|top>0)while(p!=NULL) /*如果p不空，根结点，遍历左子树*/stacktop+=p; /*将p入栈*/p=p->lchild; /*遍历左子树*/if(top>0) /*如果栈不空*/p=stacktop-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) 程序运行结果如何？五、 总结与心得理解了二叉树的逻辑特点和二叉树的性质；掌握了二叉树的二叉链表存储构造，以及二叉树的遍历算法的递归与非递归实现。虽完成了实验，但也需日后多多练习。实验完成后的总结与思考，或者谈收获。注意此局部要结合自己的题目来阐述说明. >