资源描述：
《二叉树的建立与遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途实践考核题第二题设计报告书学生姓名 XXX学生学号0９XXX所在地区XXX提交日期(年/月）２014/6实践题目实现二叉树的建立与遍历 需求分析 （1）以二叉链表作为存储结构,定义二叉树类型Ｂitｒee 定义二叉链表的存储结构,可以更好地对二叉表的操作，在二叉链表中,datａ域用于存储二叉树节点中的数据信息；lchiｌｄ是指向左孩子的指针(左指针）。类似的，rchild是指向右孩子的指针（右指针）。此外，每个二叉链表还必须有一个指向根节点的指针，该指针称为根指针。与链表头指针类似,根指针具有标识二叉链表
2、的作用，对二叉链表的访问只能从根指针开始。若果某个节点的右孩子或者左孩子不存在时,则相应指针数据域为空(#)。由此可知叶节点的左右指针必为空（#）。(２)实现二叉树的以下运算<1＞建立vｏid CreateBiＴree（BiTreｅ＊T） 输入二叉树的结点元素,建立二叉链表 建立voｉｄ ＣreateBｉTree(BiTrｅe ＊Ｔ)函数可以往二叉链表中输入数据和向左右指针的指向是否为#,只有建立了二叉链表才能通过调用先序遍历、中序遍历和后序遍历的函数遍历出二叉树中的数据。<２>选择一种遍历方式（先序、中序、后序)遍历这
3、棵二叉树通过选择遍历方式，遍历同一颗二叉树，遍历的次序是不同的，遍历的方法也是不一样的，通过不同的遍历方式的得到二叉树的顺序是不一样,但是都是为了得到二叉树最后的排序。通过先序遍历，先访问的是根节点，然后是左子树,最后是右子树。中序遍历，先遍历左子树，在访问根节点，最后遍历右子树。后序遍历,先遍历左子树,在遍历右子树,左后访问根节点。通过不同的排序方式可以确定一棵唯一的二叉树。概要设计个人收集整理勿做商业用途（1）建立二叉链表: voidCreateBiTreｅ(BｉTree *T) 首先，定义一个结构体,存储每个节点的信息
4、，并给这个结构体定义别名为Bittree;这个结构体中的数据元素有，保存数据的类型,还有指向左右孩子的指针它的类型和结构体的类型一样。（2）实现二叉树的以下运算选择一种遍历方式（先序、中序、后序)遍历这棵二叉树 先序遍历:void PrｅＯrder（BiTree T)若被遍历的二叉树为空,执行空操作；否则，依次执行下列操作: 访问根节点； 先序遍历左子树; 先序遍历右子树。中序遍历：ｖoid InOrdeｒ（BiTｒｅｅT若被遍历的二叉树为空，执行空操作;否则，依次执行下列操作：中序遍历左子树;访问根节点；中序
5、遍历右子树。后序遍历:ｖoｉｄ PｏstOｒｄer(BiTｒeeT)若被遍历的二叉树为空,执行空操作;否则,依次执行下列操作:后序遍历左子树；后序遍历右子树;访问根节点。上面给出的先序遍历、中序遍历和后序遍历的定义都是递归的，因而根据定义很容易得到相应遍历的递归算法。详细设计个人收集整理勿做商业用途 #include#include＃inclｕdｅ<ｍａｌloc.h>typedefcharTElｅｍTｙpｅ;typedef sｔruct ＳＢiＴNｏde{ TEleｍTypｅdａｔａ;ｓ
6、ｔructSBiTＮode*lchilｄ,＊rchild;}BiTNodｅ,*ＢiTree;//采用左序遍历创建二叉树，用到的是递归算法，参数指针T有点晦涩难懂。ｖoidCreａteBｉTree(ＢｉTreｅ*Ｔ）{ ＴElｅｍＴypeｃｈ; scanｆ(＂%c＂,&ch);if(cｈ＝＝'＃'） *T=ＮULL; else{ *T=(BiTree)ｍalloc（siｚeoｆ(BｉTNoｄe) )； if(！*T) exit(-1); （*T）->datａ＝cｈ; CreａteBiＴreｅ(＆(
7、＊T)-＞lchild);个人收集整理勿做商业用途 CreateBiTｒeｅ(&(*T)->rｃｈｉｌd）; ｝}//输出函数voidVｉｓit(BｉTree T)｛ﻩif（T－>ｄａｔa!='＃'){ﻩprintｆ("％ｃ",Ｔ->ｄata)；ﻩ}}//先序遍历ｖｏidＰrｅOrｄer(BiTreeT){if(T！=NULL）{ﻩ／/访问根节点ﻩVｉsiｔ（Ｔ);ﻩ／／访问左子结点ﻩPreOrdｅr(T->lchild);ﻩ／／访问右子结点PreOｒｄｅr(T->ｒcｈild);}}//中序遍历vｏiｄInOrder（Ｂi
8、TreeT){个人收集整理勿做商业用途 ／/判断是否为空ｉf(T!=NULＬ) ｛//中序访问左子树InOrdeｒ(Ｔ->lchiｌd); /／访问根节点 Ｖisit(T); //中序访问右子树 InOrder(T-＞ｒｃhiｌd); ｝}/／后序遍历voidP
