《数据结构——使用c语言树和二叉树》由会员分享，可在线阅读，更多相关《数据结构——使用c语言树和二叉树（102页珍藏版）》请在金锄头文库上搜索。
1、数据结构使用C语言树和二叉树,树 二叉树 二叉树设计 二叉树遍历 线索二叉树 哈夫曼树 等价问题 树与二叉树的转换 树的遍历,主要知识点,1 树,1.树的定义,树是由n(n0)个结点组成的有限集合T。n=0的树称为空树；对n0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n1时，除根结点外其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。,注：树的定义具有递归性，即“树中还有树”。,若干术语,结点：由数据元素和构造数据元素之 间关系的指针组成,结点的度：结点所拥有的子树的个数,叶结点：度为0的结点，也称作
2、终端结点,分支结点：度不为0的结点,孩子结点：树中一个结点的子树的根结点,双亲结点：若树中某结点有孩子结点，则这个结点就 称作它的孩子结点的双亲结点,兄弟结点：具有相同的双亲结点的结点,树的度：树中所有结点的度的最大值,结点的层次：从根结点到树中某结点所经路径上的分支数,树的深度：树中所有结点的层次的最大值,无序树：树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树,有序树：树中任意一个结点的各孩子结点有严格排列 次序的树,森林：m（m0）棵树的集合,2.树的表示方法,(1)直观表示法,(2)形式化表示法,(3)凹入表示法,T=（D，R） DF = D1D2Dm （1i,jm, DiDj
3、=） R=, i=1,2,n-1,A,B,C,D,E,F,G,H,I,J,K,L,3.树的抽象数据类型,数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）双亲结点Parent(T, curr) （4）左孩子结点LeftChild(T, curr) （5）右兄弟结点RightSibling(T, curr) （6）遍历树Traverse(T, Visit(),4.树的存储结构,树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主
4、要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。 指针有常规指针和仿真指针,(1)双亲表示法,(a)一棵树,（b)仿真指针的双亲表示法存储结构,树及其使用仿真指针的双亲表示法,(2)孩子表示法,双亲孩子表示法存储结构,(3)双亲孩子表示法,(4)孩子兄弟表示法,常规指针的孩子兄弟表示法,2 二叉树,一、二叉树：是n(n0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒。所以下
5、面是两棵不同的树,1.二叉树的定义,二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。 三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示,(a)满二叉树,(b)完全二叉树,问题:一个高度为h的完全二叉树最多有多少个结点?最少有多少个结点?,数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）
6、左插入结点InsertLeftNode(curr, x) （4）右插入结点InsertRightNode(curr, x) （5）左删除子树DeleteLeftTree(curr) （6）右删除子树DeleteRightTree(curr) （7）遍历二叉树Traverse(T, Visit(),2.二叉树抽象数据类型,3.二叉树的性质,性质1 在一棵非空二叉树的第i层上至多有2i个结点（i0）。,性质2 深度为k的二叉树至多有2k+1-1个结点。 说明：深度k=-1，表示没有一个结点；深度k=0，表示只有一个根结点。,性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，
7、则有 n0= n2+1。 证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点个数，则有： n = n0 + n1 + n2 另外，在二叉树中，除根结点外的所有结点都有一个惟一的进入分支，设M为二叉树中所有结点的进入分支数，则有： M = n - 1 从二叉树的结构可知，二叉树的所有进入分支是由度为1的结点和度为2的结点发出的，每个度为1的结点发出一个分支，每个度为2的结点发出两个分支，所以又有： M = n1 + 2 n2 因此有： n - 1 = n1 + 2 n2 再把 n=n0+n1+n2 代入，则可以得到 n0 = n2 + 1。,性质4 具有n个结点的完全二叉树的深度k为大于或
8、等于lb(n+1)-1的最小整数。 证明：由性质2和完全二叉树的定义可知，对于有n个结点的深度为k的完全二叉树有：2k-1 n 2k+1-1 移项有：2k n+1 2k+1 对不等式求对数，有：k lb(n+1) k+1 因为lb(n+1)介于k和k+1之间且大于k，而二叉树的深度又只能是整数，所以必有k为大于或等于lb(n+1)-1的最小整数。 可简写为k=lb(n+1)-1。例如，2.0=2，2.1=3。 若结点个数n=0，则有深度k=-1，满足k=lb(0+1)-1=-1； 若结点个数n=1，则有深度k=0，满足k=lb(1+1)-1=0； 若结点个数n=2，则有深度k=1，满足k=lb
9、(2+1)-1 =0.xx =1； 若结点个数n=3，则有深度k=1，满足k=lb(3+1)-1=1。,性质5 对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0i 0，则其双亲是结点(i-1)/2(“/”表示整除） ；如果i=0，则结点i是根结点，无双亲。 (2)如果2i+1n ，其左孩子是结点2i+1；如果2i+1n，则结点i无左孩子。 (3)如果2i2n，其右孩子是结点2i2；如果2i2n，则结点i无右孩子。,3.1二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。 1. 二叉树的顺序
10、存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：,3二叉树的设计和实现,对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。,(a)一般二叉树,(b)完全二叉树形态,(c) 在数组中的存储形式,2. 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域dat
11、a、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为：,二叉链存储结构的二叉树也有不带头结点和带头结点两种。带头结点的二叉链存储结构的二叉树见下图(b)，不带头结点的二叉链存储结构的二叉树如下图(a)所示。,图8-10 二叉链存储结构的二叉树,(a)不带头结点的二叉树,(b)带头结点的二叉树,3.二叉树的仿真指针 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。,二叉树的仿真二叉链存储结构,3.2二叉链结构的二叉树设计,typedef struct
12、 Node DataType data; struct Node *leftChild; struct Node *rightChild; BiTreeNode; /*初始化*/ void Initiate(BiTreeNode *root) *root = (BiTreeNode *)malloc(sizeof(BiTreeNode); (*root)-leftChild = NULL; (*root)-rightChild = NULL; ,/*左子树插入结点*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) BiTree
13、Node *s, *t; if(curr = NULL) return NULL; t = curr-leftChild; s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-leftChild = t; s-rightChild = NULL; curr-leftChild = s; return curr-leftChild; ,/*删除左子树*/ BiTreeNode *DeleteLeftTree(BiTreeNode *curr) if(curr = NULL | curr-leftChild = NULL) retu
14、rn NULL; Destroy( ,例8-1 编写一个建立如图8-10（b）所示的带头结点的二叉链存储结构二叉树的程序。 #include #include typedef char DataType; #include “Bitree.h“ Void main(void) BiTreeNode *root, *p, *pp; Initiate( ,4 二叉树遍历,1.二叉树遍历的基本方法,从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D,L,R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，根据遍历算法对访问根结点处理的位置，称下面三种遍历
15、算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。,4.1 二叉树遍历,前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 对于图8-7（b）所示的二叉树，前序遍历访问结点的次序为： A B D G C E F,中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 对于图8-7（b）所示的二叉树，中序遍历访问结点的次序为： D G B A E C F,后序遍历（LRD）递归算法为： 若二
16、叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 对于图8-7（b）所示的二叉树，后序遍历访问结点的次序为： G D B E F C A,此外，二叉树还有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。 它的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。,二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得一个结点指针，访问该结点； （3.b）若该结点的左子树非空，则将该结点的左子树指 针入队列； （3.c）若该结点的右子树非空，则将该结点的右子树指 针入队列； （4）结束。,
