ﻩCreateＢｉtTｒeｅ(&T);
ｐrｉntf（"二叉树的先序序列：\n")；
prｉntf("递归：\t")；
PreOrderTｒaｖeｒse(T);
ﻩprｉｎtf(＂\n")；
pｒｉntf(＂非递归:");
ﻩPreOrｄerＴravｅrse2(T);
ﻩpｒｉntf("\n＂）；
ﻩｐrintf("二叉树的中序序列:\n")；
ｖoiｄＩnOrｄerTraveｒse２(ＢiTree T）;ﻩ/＊二叉树的中序遍历的非递归函数声明*/
ｖoidPostOrｄerTraｖeｒｓe2(ＢiTｒｅeＴ）;/*二叉树的后序遍历的非递归函数声明＊/
vｏid mａin()
{
BiTｒeｅT,root；
IniｔBitTｒee(&T);
ﻩprintｆ("根据输入二叉叉树并输出三种遍历结果
———————————————————————————————— 作者:
———————————————————————————————— 日期:
ﻩ
实验报告
课程名称数据结构
实验项目实验三-－创建一个二叉树并输出三种遍历结果
系 别＿__ ＿计算机学院 ＿ ______
专 业_＿_ _＿_
班级/学号___＿＿__＿___
学生姓名 _＿__＿__＿_
实验日期＿
成 绩___＿＿___＿_____＿__＿__＿__
指导教师
实验题目:实验三－--－-－创建一个二叉树并输出三种遍历结果
一、实验目的
1)掌握二叉树存储结构;
2)掌握并实现二叉树遍历的递归算法和非递归算法；
3)理解树及森林对二叉树的转换;
ﻩpｒinｔf（"\n");
ﻩｐｒinｔf（"非递归：");
ﻩPosｔOrdeｒTｒavｅｒsｅ２（T);
ﻩｐrintf(＂\ｎ");
｝
vｏid InitＢitＴree(ＢiTｒeｅ*Ｔ)
{
*T=NUＬL；
}
void CreatｅBitＴｒｅe(ＢiTree *T)
/*递归创建二叉树＊/
｛
DataTypｅch；
ｐrintf("递归:\t");
IｎOrdeｒTraverse(Ｔ）;
ﻩｐrｉntf（＂\ｎ");
prｉntf("非递归：")；
ﻩInOｒdeｒTravｅrse2(T）；
ﻩｐrintf（"\n");
ﻩpriｎｔｆ(＂二叉树的后序序列:\n");
ﻩprｉntf("递归:\t"）;
PoｓｔＯｒderTraverse(T);
（2）然后以递归的先序遍历方法创建二叉树，函数为CreatｅTrｅｅ(），在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应当输入一个特殊的字符（本算法为“#”),表示左孩子或者右孩子为空。
（3）下一步,创建利用递归方法先序遍历二叉树的函数，函数为PreＯrderTree(),创建非递归方法中序遍历二叉树的函数,函数为IｎOｒderＴree（)，中序遍历过程是:从二叉树的根节点开始，沿左子树向下搜索,在搜索过程将所遇到的节点进栈；左子树遍历完毕后,从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推,指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数,函数为LaOrdｅrＴｒee(）。
(提示:该部分主要是利用C、Ｃ＋＋等完成数据结构定义、设计算法实现各种操作,可以用列表分步形式的自然语言描述，也可以利用流程图等描述)
4)编码
#include<ｓtdiｏ.ｈ>
#inｃlude＜malloc.ｈ>
＃incluｄe<stdliｂ.h＞
tyｐｅｄef cｈar DataＴype；
＃ｄefineＭaxSiｚe１０0
2)本实验用到的理论知识
遍历二叉树,递归和非递归的方法
（提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关,要求结合自己的题目并阐述自己的理解和想法)
3)具体算法设计
（1）首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtyｐｅ,定义一棵二叉树,只需定义其根指针。
4)理解二叉树的应用—哈夫曼编码及ＷPＬ计算。
二、实验内容
1)以广义表或遍历序列形式创建一个二叉树，存储结构自选；
2)输出先序、中序、后序遍历序列；
3)二选一应用题:1）树和森林向二叉树转换；2)哈夫曼编码的应用问题。（应用型题目可替换上述前两项实验内容）
三、设计与编码
1)程序结构基本设计框架
（提示：请根据所选定题目，描述程序的基本框架,可以用流程图、界面描述图、框图等来表示）
CreateBitTｒee(&((*T)->rcｈild)）; ﻩﻩ/*构造右子树*/
}
}
voｉdPｒeOrderTrａveｒse(BiTree T)
/＊先序遍历二叉树的递归实现＊/
{
ｉf(T)ﻩﻩﻩﻩ/*如果二叉树不为空*/
{
ｐｒiｎtf("%2c＂,T->dａta）;ﻩ/＊访问根结点*/
PrｅOrderＴraverse(T-＞lcｈilｄ）;ﻩ/*先序遍历左子树＊/
ｖoｉｄＰｒeOｒｄeｒTravｅrｓｅ(BiTree T）；/*二叉树的先序遍历的递归函数声明*/
ｖoidＩｎOrderＴｒavｅrse（BiTreｅＴ）;/＊二叉树的中序遍历的递归函数声明*／
ｖoid PosｔOrdeｒＴrａverse（BｉTrｅeＴ）;/＊二叉树的后序遍历的递归函数声明＊/
ｖoidPrｅOrdｅrTraverse2(ＢｉＴreｅT);/＊二叉树的先序遍历的非递归函数声明＊/
tｙpeｄef structNode
｛
DaｔａTypeｄata;
ﻩstrｕctＮoｄe*lｃhilｄ;
structNoｄｅ*rｃhild;
｝
*ＢiTｒeｅ,BitＮode;
ｖoiｄIniｔBｉtTrｅe(BiＴｒeｅ*Ｔ); /*树的初始化*/
ｖoｉd CrｅaｔｅBitTreｅ(BｉTrｅe*Ｔ);/*按照先序输入字符序列递归创建二叉树*/
sｃanf（＂%ｃ"，&ｃh);
iｆ(ｃh=='#')
*T=ＮULＬ；
elｓe
{
*Ｔ＝(BｉＴｒｅe)ｍalloc(ｓizeof(BｉtNoｄe））;ﻩ/*生成根结点＊／
if(!(*Ｔ))
eｘiｔ(-１);
(*T)－>data=ch；
CreateBitＴree（&(（＊T)－>lｃｈild))；ﻩ/＊构造左子树*／