文档介绍：数据结构实验
数据结构实验
数据结构实验
实验六二叉树遍历算法的设计与实现
实验人：杨嘉雯　学号:　Xb1０680２30 　　　　　时间：。2７
实验目的
掌握二叉树的建立与存储
掌握二叉树的遍历方法
实验内容
编写程序实现根据用户输入二叉树的先序序列建立一棵二叉树，并实现对此二叉树的先序、中序、和后序遍历。用非递归方法实现中序遍历。(选做)
实验步骤：
。
2．对建立好的二叉树实现先序、中序、和后序遍历，将遍历后的序列输出。
算法说明
对于三种遍历的过程,要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三种遍历，中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子，直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。
采用非递归中序遍历算法,先逐步扫描二叉树的左子树，并压入堆栈,如果栈不为空,左子树为空,则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树,直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。
数据结构实验
数据结构实验
数据结构实验
测试结果
中序线索化二叉树：
分析与探讨
实验中经常会出现前后字符不一致的情况，主要原因是自己比较马虎,平时编程比较少,遇到比较长的程序,就容易出错。
附录：源代码
#incｌude 〈>
#iｎclｕｄｅ　〈〉
ｔｙpedef struct　BｉTNoｄe ／*定义二叉链表结点结构*/
　{ 　　
　 char dａtａ；　
　　　 sｔruｃt BiTNode　*ｌchild,*rcｈild；
数据结构实验
数据结构实验
数据结构实验
　 }BiTNode,*BiTｒｅe;
void CreateBiTree(ＢｉTree　*T）/＊输入二叉树的先序遍历序列，创建二叉链表 */　
｛　
char　ｃh；
ﻩch＝getｃｈａr(）; 　
if （ch==＇＃’）＊T＝NUＬL;
else
｛
ﻩ　　＊T=（BiTＮode*）mallｏｃ（sizｅof(BiTNode））；　
ﻩ(*T)-〉data=ｃh; 　
//prｉｎtf("当前根结点:％c\n”，（*T）－＞dａta); 　
ﻩ CｒeａｔｅＢｉTree（&（＊T）-＞ｌchiｌd）; /* 建左子树＊／　　　
CｒeａtｅＢiTｒee(&（＊Ｔ)-〉rchilｄ）；／* 建右子树 */ 　
　　}
}
voｉd PreOrｄerTraｖerse（BiTree T）／*　对二叉树进行先序遍历 *／　
｛　
if(T==NULL）
　rｅturn；　
prinｔf(＂％c＂,T－>dａｔａ）; 　
　 PｒeOrdeｒTraｖｅrsｅ(T—〉lchild）；ﻩﻩ
ﻩＰｒeOrderTｒavｅrse(T—>rchil