数据结构树和二叉树

《数据结构树和二叉树》由会员分享，可在线阅读，更多相关《数据结构树和二叉树（131页珍藏版）》请在金锄头文库上搜索。

1、 第6章 树和二叉树 树型结构是一类重要的非线性结构。树型结 构是结点之间有分支，并且具有层次关系的结 构，它非常类似于自然界中的树。树结构在客 观世界中是大量存在的，例如家谱、行政组织 机构都可用树形象地表示。树在计算机领域中 也有着广泛的应用，例如在编译程序中，用树 来表示源程序的语法结构；在数据库系统中， 可用树来组织信息；在分析算法的行为时，可 用树来描述其执行过程。等等。 6.1 树的类型定义树的定义及基本概念树(Tree)是n(n=0)个结点的有限集T，T为 空时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m=0)个

2、互不相交的子 集T1,T2,T3Tm，其中每个子集又是一棵树，并 称其为子树(Subtree)。ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根例如:AEBCDFHIGTEBDFHIT1CGT2E DF HIT12T11T13树的递归定义树的表示AEBCDFHIGTa*b+(c-d/e)*f+-*abc/fde树形表示法Cusert2.docT1.txtWin.inisystem32windowsAutoexec.batsjlib文件目录结构CGAFDIHB E集合图凹入表A B D E HI F C GA（B（D，E（H，I

3、），F），C（G） ）广义表数据对象 D： D是具有相同特性的数据元素的集合。若D为空集，则称为空树 。否则:(1) 在D中存在唯一的称为根的数据元素root；(2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系 R：基本操作：查 找 类插 入 类删 除 类Root(T) / 求树的根结点 查找类：Value(T, cur_e) / 求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子 RightS

4、ibling(T, cur_e) / 求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树 TreeDepth(T) / 求树的深度TraverseTree( T, Visit() ) / 遍历InitTree( SqBiTree bt;二叉树的顺序存储表示A B C D EFG H IJK L1 2 3 4 5 6 7 8 9 10 11 12完全二叉树ABCDEFGHIJKLABCDEFG 表示该处没有元素 存在仅仅为了好理解ABCDEFG一般二叉树 从树根起，自上层至下层，每层自左 至右的给所有结点编号缺点是有可能对存 储空间造成极大的浪费，在最坏的情况下 ，一个深度为H且只

5、有H个结点的右单支树 确需要2H-1个结点存储空间。而且，若经 常需要插入与删除树中结点时，顺序存储 方式不是很好！二、二叉树的链式存储表示 设计不同的结点结构可构成不同 形式的链式存储结构。DATAPARENTLCHILDRCHILDADEBCFrootlchild data rchild结点结构:1. 二叉链表typedef struct BiTNode / 结点结构TElemType data;struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构:C 语言的类型描述如下: 有时也

6、可用数组的下标来模拟指针, 即开辟三个一维数组 Data ,lchild,rchild 分别存储结点的元素及 其左,右指针域;ADEBCFroot2三叉链表parent lchild data rchild结点结构:typedef struct TriTNode / 结点结构TElemType data;struct TriTNode *lchild, *rchild; / 左右孩子指针struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结构:C 语言的类型描述如下:二叉树链表表示的示例二叉树

7、链表表示的示例 AAABBBCCCDDDFFFEEErootrootroot二叉树 二叉链表 三叉链表 在不同的存储结构中，实现二叉 树的操作方法也不同，如找结点X的双亲 ，在三叉表中很容易实现，但在二叉表 中则需从根指针出发巡查。由此，在具 体应用中采用什么存储结构，除根据二 叉树的形态之外还应考虑需进行的何种 操作。6.4二叉树的遍历在二叉树的一些应用中，常常要求在树中查找具 有某种特征的结点，或者对树中全部结点逐一进行 某种处理。这就引入了遍历二叉树的问题， 即如 何顺着某一条搜索路径巡访二叉树中的结点，使得 每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，

8、如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。 假如以L、D、R分别表示遍历左子树、遍历根结 点和遍历右子树，遍历整个二叉树则有DLR、LDR、 LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右 ，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。 二叉树是由3个基本单元组成：根结点、左 子树、右子树。因此若能依次遍历这三个部分， 便是遍历了整个二叉树。二、先左后

9、右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：例如图（1）所示的二叉树表达式 (a+b*(c-d)-e/f) 若先序遍历此二叉树,按访问结点的先后次序将结点排列起 来,其先序序列为: (波兰式) -+a*b-cd/ef按中序遍

10、历,其中序序列为： a+b*c-d-e/f (中缀式)按后序遍历,其后序序列为： abcd-*+ef/- (逆波兰式) 人喜欢中缀形式的算术 表达式,对于计算机,使 用后缀易于求值 图 （1） *a/b-dcfe遍历算法的应用举例1、统计二叉树中叶子结点的个数(先序遍历)2、求二叉树的深度(后序遍历)1、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数 ”的参数，并将算法中“访问结点”的 操作改为：若是叶子，则计数器增1。void CountLeaf (BiTree T, int / 对叶子结点计数C

11、ountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf2、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1 。由此，需先分别求得左、右子树的深 度，算法中“访问结点”的操作为：求 得左、右子树深度的最大值，然后加 1 。首先分析二叉树的深度和它的左、右子树深度之间的关系。int Depth (BiTree T ) / 返回二叉树的深度if ( !T ) depthval = 0;else depthLeft = Depth( T-lchild

12、);depthRight= Depth( T-rchild );depthval = 1 + (depthLeft depthRight ?depthLeft : depthRight); return depthval; 按给定的表达式建相应二叉树 由先缀表示式建树例如：已知表达式的先缀表示式-+ a b c / d e 由原表达式建树 例如：已知表达式 (a+b)c d/e对应先缀表达式 -+ a b c / d e的二叉树abcde-+/特点：操作数为叶子结点运算符为分支结点scanf( if ( In(ch, 字母集 ) 建叶子结点; else 建根结点;递归建左子树;递归建右子树;

13、由先缀表示式建树的算法的基本操作：a+b(a+b)c d/ea+bc 分析表达式和二叉树的关系:ab+a bc+abc +(a+b)cabcde- +/6.5 线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如: 先序序列:A B C D E F G H K 中序序列:B D C A H G K F E后序序列:D C B H K G F E A指向该线性序列中的“前驱”和“后继” 的指针，称作“线索”与其相应的二叉树， 称作 “线索二叉树”包含 “线索” 的存储结 构，称作 “线索链表”A

14、 B C D E F G H K D C B E 对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定： lchildltagDatartagrchild其中: 0 lchild 域指示结点的左孩子 ltag= 1 lchild 域指示结点的前驱 rtag= 0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后驱 对二叉树以某种次序遍历使其变 为线索二叉树的过程叫线索化。typedef struct BiThrNod TElemType data;struct BiThrNode *lchild, *rchild; / 左右指针PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;线索链表的类型描述：typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索二、线索链表的遍历算法:由于在线索链表中添加了遍历中得到 的“前驱”和“后继”的信息，从而简化了遍历的算法。在线索树上进行遍历，只要先找到序 列中的第一个结点，然后依次找结点后 继直至其后继为空时为止。从遍历的第一个结点来看： 先序序列中第一个结点必为根结点 中、后序序列中第一个结点的左孩子定为空 从遍历的最后一个结点来看： 先、中序序列中最后一个结点的右孩子