《信息与通信树》ppt课件

《《信息与通信树》ppt课件》由会员分享，可在线阅读，更多相关《《信息与通信树》ppt课件（91页珍藏版）》请在金锄头文库上搜索。

1、第6章 树,6.1 树的应用实例 6.2 树的基本概念和术语 6.3 二叉树 6.4 遍历二叉树 6.5 线索二叉树 6.6 二叉树、树和森林 6.7 树的应用 6.8 实习: 二叉树的建立和遍历 习题6,6.1 树的应用实例,例6.1 如图6.1为某校计算机系领导结构图。 例6.2 家族树,图6.1 某校计算机系领导结构图,图6.2 家族树,6.2 树的基本概念和术语,6.2.1 树的定义 树(Tree)是由一个或多个结点组成的有限集合T。其中： (1) 有一个特定的结点称为该树的根(Root)结点； (2) 除根结点之外的其余结点可分为m(m0)个互不相交的有限集合T1，T2，Tm，且其中

2、每一个集合本身又是一棵树，称之为根的子树(Subtree)。 这是一个递归的定义，即在定义中又用到了树这个术语。它道出了树的固有特性。仅有一个根结点的树是最小树，树中结点较多时，每个结点都是某一棵子树的根。,图6.3是一棵由9个结点组成的树T。其中A是根结点，其余结点分为三个互不相交的子集：T1=B,H,I，T2=C，T3=D,E,F,G。T1、T2、T3都是树根A的子树，这三棵子树的根结点分别是B、C、D。每棵子树本身也是一棵树，可继续划分。例如子树T3以D为根结点，它的其余结点又可分为两个互不相交的子集：T31=E，T32=F，G，而其中T31可以认为是仅有一个根结点的子树。,图6.3 树

3、T,6.2.2 树的表示 （1）树形图表示 树形图表示是树结构的主要表示方法。 树的树形图表示中：结点用圆圈表示，结点的名字写在圆圈旁边（有时亦可写在圆圈内）。 （2）树的其他表示法 嵌套集合表示法 是用集合的包含关系来描述树结构。 上图(a)树的嵌套集合表示法如图(b) 凹入表表示法 类似于书的目录，上图(a)树的凹入表示法如图(c) 广义表表示法 用广义表的形式表示的。上图(a)树的广义表表示法如图(d) （A（B（E，F（I，J），C，D（G，H）,6.2.3 树的常用术语 1. 结点的度和树的度 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree

4、)。而树的度是指树中结点的度的最大值。如图6.3中，B结点有2个子树，则它的度为2。在树T中，A结点的度最大，值为3，也就是说，树T的度为3。,2. 分支结点和叶子结点 称度不为0的结点为分支结点，也叫非终端结点。称度为0的结点为叶子(Leaf)或终端结点。如图6.3中，分支结点分别为A、B、D、F，而叶子结点分别为H、I、C、E、G。,3. 孩子、双亲、兄弟、子孙、祖先 结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。如图6.3中，B、C、D分别是根结点A的子树的根，三个都是A的孩子，相应地，A是它们

5、的双亲，其中，B、C、D三者是兄弟。一棵树上除根结点以外的其它结点称为根结点的子孙。对于树中某结点，从根结点开始到该结点的双亲是该结点的祖先。,4. 结点的层次和树的高度 结点的层次(Level)从根结点开始定义，根为第一层，根结点的孩子为第二层，依次类推，其余结点的层次值为双亲结点层次值加1。树中结点的最大层次值称为树的高度或深度(Depth)。如图6.3所示的树T高度为4。,5. 无序树、有序树、森林 若树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林(Forest)是m(m0

6、)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。,6.3 二 叉 树,6.3.1 二叉树的定义 二叉树(Binary Tree)是n(n0)个结点的有限集合。它或为空树(n0)，或为非空树；对于非空树有： (1) 有一个特定的称之为根的结点； (2) 根结点以外的其余结点分别由两棵互不相交的称之为左子树和右子树的二叉树组成。,这个递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成的。由于左、右子树也是二叉树，则由二叉树的定义，它们也可以为空。由此，二叉树可以有五种基本形态，如图6.5所示。,图6.5 二叉树的五种基本形态 (a) 空

7、二叉树; (b) 只有一个根结点; (c) 有根结点和左子树; (d) 有根结点和右子树; (e) 有根结点和左、右子树,有两种特殊形态的二叉树，它们是满二叉树和完全二叉树。 满二叉树：深度为k且含有2k1个结点的二叉树为满二叉树，这种树的特点是每层上的结点数都是最大结点数，如图6.6(a)所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，图6.6(a)中每个结点边的数字即是该结点的编号。 完全二叉树：深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序号从1到n相对应时，则称此二叉树为完全二叉树，如图6.6(b)所示。而图6.6(c)则不是完全二叉树。

8、,图6.6 满二叉树和完全二叉树 (a) 满二叉树；(b) 完全二叉树；(c) 非完全二叉树,6.3.2 二叉树的重要性质 性质1 二叉树第i(i1)层上至多有2i-1个结点。 根据二叉树和结点层次的定义可知，根结点在第一层上，这层结点数至多为1个，即20个；显然第二层上至多有2个结点，即21个 假设第i1层的结点至多有2i-2个，且每个结点最多有两个孩子，那么第i层上结点至多有22i-2=2i-1个。,性质2 深度为k(k1)的二叉树至多有2k1个结点。 由性质1可知，各层结点最多数目之和为20+21+22+2k-1；由二进制换算关系可知：20+21+22+2k-1=2k1，因此二叉树中结点

9、的最大数目为2k1。,性质3 在任意二叉树中，若叶子结点(即度为零的结点)个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，那么n0=n2+1。 证明：设n代表二叉树结点总数，那么 n=n0+n1+n2 (1) 由于有n个结点的二叉树总分支数为n1条，于是得 n1=0n0+1n1+2n2 (2) 将式(1)代入式(2)得 n0=n2+1,性质4 具有n个结点的完全二叉树深度为 log2n+1(其中x表示不大于x的最大整数)。,性质5 若对有n(1in)个结点的完全二叉树进行顺序编号，那么，对于编号为i(i1)的结点： 当i=1时，该结点为根，它无双亲结点； 当i1时，该结点的双亲结点

10、编号为i/2 ； 若2in，则有编号为2i的左孩子，否则没有左孩子； 若2i+1n，则有编号为2i+1的右孩子，否则没有右孩子。,6.3.3 二叉树的存储结构 二叉树常用的存储结构有两种，即顺序存储结构和链式存储结构。 (1) 顺序存储结构(向量)可以作为二叉树的存储结构。这种存储结构适用于完全二叉树和满二叉树。假设用一维数组a存放图6.6(a)所示的满二叉树。可以发现图6.6(a)中结点的编号恰好与数组元素的下标相对应，见图6.7。根据二叉树性质5，在a数组中可以方便地由某结点ai的下标i找到它们的双亲结点ai/2或左、右孩子结点a2i、a2i+1。在哈夫曼树构造算法中也用到顺序存储结构。一

11、般二叉树较少采用顺序存储结构。,图6.7 二叉树的顺序存储结构,(2) 链表存储结构通常用于二叉树存储。常见的有二叉链表和三叉链表。二叉链表的每个结点都有一个数据域和两个指针域，一个指针指向左孩子，另一个指针指向右孩子。 typedef struct node datatype data； /*数据域*/ struct node *lch，*rch； /*左、右指针域*/ BinTNode ; typedef BinTNode *BinTree；/BinTree为指向BinTNode类型结点的指针类型,三叉链表的结点比二叉链表多了一个指向双亲的指针域。结点结构如图6.8(b)所示，可以描述为：

12、 typedef struct datatype data； /*数据域*/ struct BTlink3 *lch，*parent，*rch；/*parent是双亲指针域*/ Bnode3;,(a),(b),图6.8 二叉树链表存储结构中的结点结构 (a) 二叉链表中的结点结构；(b) 三叉链表中的结点结构,图6.9 二叉树的链表存储结构,6.4 遍历二叉树,在二叉树的应用中，常常需要在树中搜索具有某种特征的结点，或对树中全部的结点逐一进行处理。这就涉及到一个遍历二叉树的问题。遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。所谓访问结点，就是指对结点进行各种操作。

13、例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。对于线性结构来说，遍历很容易实现，顺序扫描结构中的每个数据元素即可。但二叉树是非线性结构，遍历时是先访问根结点还是先访问子树，是先访问左子树还是先访问右子树必须有所规定，这就是遍历规则。采用不同的遍历规则会产生不同的遍历结果，因此必须人为设定遍历规则。,由于一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成的，遍历二叉树时只要按顺序依次遍历这三部分即可。假定我们以D、L、R分别表示访问根结点、遍历左子树和遍历右子树，则可以有六种遍历形式：DLR、LDR

14、、LRD、DRL、RDL、RLD，若依习惯规定先左后右，则上述六种形式可归并为三种形式，即： DLR 先序遍历 LDR 中序遍历 LRD 后序遍历,6.4.1 先序遍历 先序遍历可以递归地描述如下： 如果二叉树为空，则空操作，否则： 访问根结点； 按先序次序遍历左子树； 按先序次序遍历右子树。 先序遍历的递归算法如下:,/*算法描述6.2 先序遍历的递归算法*/ void preorder(BTlink * p) if(p!=NULL) printf(“%cn“，p-data)； /*访问根结点*/ preorder(p-lch)； /*按先根次序遍历左子树*/ preorder(p-rch)

15、； /*按先根次序遍历右子树*/ /*preorder*/,图6.11 遍历序列示例,6.4.2 中序遍历 中序遍历可以递归地描述如下： 如果二叉树为空，则空操作，否则： 按中序次序遍历左子树， 访问根结点， 按中序次序遍历右子树。 中序遍历递归算法如下:,/*算法描述6.3 中序遍历的递归算法*/ void inorder(BTlink *p) if (p!=NULL) inorder(p-lch)； /*中序遍历左子树*/ printf(“%cn“，p-data)； /*访问根结点*/ inorder(p-rch)； /*中序遍历右子树*/ /*inorder*/ 例如，图6.11(a)所示二叉树的中根遍历序列为BAC, 图6.11(b)所示二叉树的中根遍历序列为BCAEDF。,6.4.3 后根遍历 后根遍历可以递归地描述如下： 如果二叉树为空，则空操作，否则： 后序遍历左子树； 后序遍历右子树； 访问根结点。 后根遍历递归算法如下：,/*算法描述6.4 后序遍历的递归算法*/ void postorder (BTlink* p ) if ( p!= NULL ) postorder ( p-lch); /*后序遍历左子树*/ postorder ( p-rch ); /*后根遍历右子树*/ printf (“ %cn