《创建一个二叉树并输出三种遍历结果》由会员分享，可在线阅读，更多相关《创建一个二叉树并输出三种遍历结果（10页珍藏版）》请在金锄头文库上搜索。
1、.实验报告课程名称数据结构实验项目实验三 - 创建一个二叉树并输出三种遍历结果系别 _计算机学院_ _专业 _班级 / 学号 _学生姓名_实验日期_成绩 _.专业 .专注.指导教师实验题目 ：实验三 -创建一个二叉树并输出三种遍历结果一、实验目的1) 掌握二叉树存储结构 ；2) 掌握并实现二叉树遍历的递归算法和非递归算法；3) 理解树及森林对二叉树的转换 ；4) 理解二叉树的应用 哈夫曼编码及 WPL 计算 。二 、实验内容1) 以广义表或遍历序列形式创建一个二叉树，存储结构自选 ；2) 输出先序 、中序 、后序遍历序列 ；3)二选一应用题： 1）树和森林向二叉树转换； 2 ）哈夫曼编码的应用
2、问题。（ 应用型题目可替换上述前两项实验内容）三、设计与编码1) 程序结构基本设计框架.专业 .专注.（提示 ：请根据所选定题目 ，描述程序的基本框架 ，可以用流程图 、界面描述图 、框图等来表示 ）2)本实验用到的理论知识遍历二叉树 ，递归和非递归的方法（提示 ：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法）3) 具体算法设计（ 1）首先，定义二叉树的存储结构为二叉链表存储 ，每个元素的数据类型 Elemtype ，定义一棵二叉树 ，只需定义其根指针 。（ 2）然后以递归的先序遍历方法创建二叉树，函数为Cre
3、ateTree()，在输入字符时要注意 ，当节点的左孩子或者右孩子为空的时候 ，应当输入一个特殊的字符（本算法为 “#”），表示左孩子或者右孩子为空 。（ 3）下一步，创建利用递归方法先序遍历二叉树的函数，函数为PreOrderTree() ，创建非递归方法中序遍历二叉树的函数，函数为InOrderTree() ，中序遍历过程是 ：从二叉树的根节点开始 ，沿左子.专业 .专注.树向下搜索 ，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推 ，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数 ，函数为 LaOrderTr
4、ee() 。（提示 ：该部分主要是利用C、 C+ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述）4)编码#include#include#includetypedef char DataType;#define MaxSize 100typedef struct NodeDataType data;struct Node *lchild;struct Node *rchild;*BiTree,BitNode;void InitBitTree(BiTree *T);/* 树的初始化 */void CreateBitTree(BiTree *T
5、);/* 按照先序输入字符序列递归创建二叉树*/void PreOrderTraverse(BiTree T);/* 二叉树的先序遍历的递归函数声明*/void InOrderTraverse(BiTree T);/* 二叉树的中序遍历的递归函数声明*/void PostOrderTraverse(BiTree T); /*二叉树的后序遍历的递归函数声明*/void PreOrderTraverse2(BiTree T); /*二叉树的先序遍历的非递归函数声明*/void InOrderTraverse2(BiTree T);/* 二叉树的中序遍历的非递归函数声明*/void PostOrde
6、rTraverse2(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);InOrderTrav
7、erse(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.专业
8、.专注.*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);/* 先序遍历左子树*/PreOrder
9、Traverse(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);/*
10、后序遍历左子树*/PostOrderTraverse(T-rchild);/* 后序遍历右子树*/printf(%2c,T-data);/* 访问根结点 */.专业 .专注.void PreOrderTraverse2(BiTree T)/* 先序遍历二叉树的非递归实现*/BiTree stackMaxSize;/* 定义一个栈 ，用于存放结点的指针*/int top;/* 定义栈顶指针 */BitNode *p;/* 定义一个结点的指针*/top=0;/* 初始化栈 */p=T;while(p!=NULL|top0)while(p!=NULL)/* 如果p不空，访问根结点 ，遍历左子树*/printf(%2c,p-data);/* 访问根结点 */stacktop+=p;/* 将 p 入栈 */p=p-lchild;/* 遍历左子树 */if(top0)/* 如果栈不空 */p=stack-top;/* 栈顶元素出栈 */p=p-rchild;/* 遍历右子树 */void InOrderTraverse2(BiTree T)/* 中序遍历二叉树的非递归实现*/BiTree stackMaxSize;/* 定义一个栈 ，用于存放结点的指针*/int top;/* 定义栈顶指针 */BitNode *p;/* 定义一个结点的指针*/top=0;/* 初始化栈 */p=T;wh
