实验报告课程名称数据结构实验项目实验三--创建一个二叉树并输出三种遍历结果系别■计算机学院 _________________专业_______________班级/学号_____________学生姓名___________实验日期—成绩______________________________ 指导教师实验题目：实验三创建一个二叉树并输出三种遍历结果实验目的1）掌握二叉树存储结构；2）掌握并实现二叉树遍历的递归算法和非递归算法;3）理解树及森林对二叉树的转换;4）理解二叉树的应用一哈夫曼编码及WPL计算。

实验内容1）以广义表或遍历序列形式创建一个二叉树，存储结构自选；2）输出先序、中序、后序遍历序列；3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。

题目可替换上述前两项实验内容）设计与编码1）程序结构基本设计框架（提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示）2）本实验用到的理论知识遍历二叉树，递归和非递归的方法（应用型(提示：总结本实验用到的理论知识，实现理论与实践相结合。

总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法)3) 具体算法设计1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype,定义一棵二叉树，只需定义其根指针。

2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。

3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推，指导整棵二叉树全部访问完毕。

创建递归方法后序遍历二叉树的函数，函数为LaOrderTree()。

(提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述)4) 编码#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef char DataType;#define MaxSize 100typedef struct Node{DataType data;struct Node *lchild;struct Node *rchild;}*BiTree,BitNode;实验题目：实验三 创建一个二叉树并输出三种遍历结果/* 树的初始化 *//* 按照先序输入字符序列递归创建二叉树 */ /* 二叉树的先序遍历的递归函数声明 */ /* 二叉树的中序遍历的递归函数声明 */ /* 二叉树的后序遍历的递归函数声明 *//* 二叉树的先序遍历的非递归函数声明 */ /*二叉树的中序遍历的非递归函数声明 */ /* 二叉树的后序遍历的非递归函数声明 */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 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 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));}}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 stack[MaxSize];int top;BitNode *p;top=0;p=T;while(p!=NULL||top>0){while(p!=NULL)*/{printf("%2c",p->data);stack[top++]=p;p=p->lchild;}if(top>0){p=stack[--top];p=p->rchild;}}}void InOrderTraverse2(BiTree T)/* 中序遍历二叉树的非递归实现*/{BiTree stack[MaxSize];int top;BitNode *p; /* 后序遍历左子树*//* 后序遍历右子树*//* 访问根结点*//* 定义一个栈，用于存放结点的指针*/ /*定义栈顶指针*//* 定义一个结点的指针*//* 初始化栈*//*如果p 不空，访问根结点，遍历左子树/* 访问根结点*//*将p 入栈*//* 遍历左子树*//* 如果栈不空*//* 栈顶元素出栈*/ /*遍历右子树*//* 定义一个栈，用于存放结点的指针*//* 定义栈顶指针*//* 定义一个结点的指针*/top=0;p=T;while(p!=NULL||top>0){while(p!=NULL)*/{stack[top++]=p;p=p->lchild;}if(top>0){p=stack[--top];printf("%2c",p->data);p=p->rchild;}}}/* 初始化栈*//*如果p 不空，访问根结点，遍历左子树/*将p 入栈*//* 遍历左子树*//* 如果栈不空*//* 栈顶元素出栈*//* 访问根结点*//* 遍历右子树*/void PostOrderTraverse2(BiTree T) /* 后序遍历二叉树的非递归实现*/{BiTree stack[MaxSize]; int top;BitNode *p,*q;top=0; p=T,q=NULL;while(p!=NULL||top>0) { while(p!=NULL) 子树*/{ stack[top++]=p;p=p->lchild;} if(top>0){/* 定义一个栈，用于存放结点的指针*/ /*定义栈顶指针*//* 定义结点的指针*//* 初始化栈*//* 初始化结点的指针*//* 如果p 不空，访问根结点，遍历左/*将p 入栈*//* 遍历左子树*//* 如果栈不空*/p=stack[top-1]; /* 取栈顶元素*/if(p->rchild==NULL||p->rchild==q) /* 如果p 没有右孩子结点，或右孩子结点已经访问过*/{ printf("%2c",p->data); /* 访问根结点*/ q=p;p=NULL; top--;}else p=p->rchild;}}}(提示：该部分主要是将算法转化为C、C++ 程序，设计主函数完成对各成员函数的调用；设计人机界面，每一步需要用户操作的提示以及每一次用户操作产生的预期结果)四、运行与测试1) 在调试程序的过程中遇到什么问题，是如何解决的？在调试程序的过程中，遇到最大的问题就是中序和后序不能正确表示答案，最后发现是因为两个函数的错误导致。