《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源06 树》由会员分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源06 树（90页珍藏版）》请在金锄头文库上搜索。
1、,数据结构与算法,第6章 树,唐懿芳,前面讨论了线性结构的表示及其应用实例。然而,线性结构在许多实际应用中不能明确、方便地表示数据元素之间的复杂关系。树型结构是一种应用十分广泛的非线性结构，其中以二叉树最为常用，它是以分支关系定义的层次结构。树型结构在客观世界中广泛存在，如家族的家谱、各种社会组织机构一般都可以用树来形象地表示。在计算机领域中，编译系统中源程序的语法结构、数据库系统中信息的组织形式也用到树形结构。 本章重点讨论二叉树的存储结构、各种操作及其应用实例,树的定义和基本术语,二叉树,遍历二叉树,线索二叉树,二叉树、树和森林,哈夫曼树及其应用,遍历算法的简单应用案例,PART,1,树的
2、定义和基本术语,树的定义,树是由 n (n 0) 个结点组成的有限集合T。 如果 n = 0，称为空树； 如果 n 0，则满足 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为 m (m 0) 个 互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树(subTree)。 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,第一节 树的定义和基本术语,数据结构与算法,第 5 页,由11个结点组成的树T,树的其他表示方法,第一节 树的定义和基本术语,数据结构与算法,第 6 页,(a)集合包含关系文氏图法
3、,(A(B(E,F,G(K),C(H),D(I,J) (b) 广义表法,树的 基本术语,第一节 树的定义和基本术语,数据结构与算法,第 7 页,结点(node) 包含一个数据元素及若干个指向其子树的分支 结点的度(degree) 结点的子树的个数 树的度(degree) 树中结点度的最大值 叶子(leaf)结点 度为零的结点 分支(branch)结点 度不为零的结点 孩子 (child)结点 某结点的各子树的根 双亲(parent)结点 该结点的直接前驱结点 兄弟(sibling) 结点 具有相同双亲的结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(leve
4、l) 根的层次值为1，其余结点的层次值为双亲结点层次值加1 树的高度(depth) 树中结点的最大层次值 有序树和无序树 森林,PART,2,二叉树(Binary Tree),第二节 二叉树 Binary Tree,数据结构与算法,第 9 页,二叉树的定义,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,五种基本形态不同的二叉树,第二节 二叉树 Binary Tree,数据结构与算法,第 10 页,二叉树的重要性质,性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i -1个结点。(i 1) 用数学归纳
5、法证明 根结点在第1 层上，这层结点数最多为1 个，即20 个；第2 层上最多有2 个结点，即21 个；. 假设第i-1 层的结点最多有2i-2 个，且每个结点最多有两个孩子,那么第i 层上结点最多有2*2 i-2 =2 i-1 个。 性质2 深度为 k 的二叉树最多有 2k-1个结点。(k 1) 证明用求等比级数前k项和的公式 根据性质1，显然深度为k的二叉树的结点总数至多为：,第二节 二叉树 Binary Tree,数据结构与算法,第 11 页,二叉树的重要性质,性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有 n0n21 证明：若设度为1的结点
6、有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 ， e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = (n0 + n1 + n2) - 1 n2 = n0 - 1 n0 = n2 + 1,第二节 二叉树 Binary Tree,数据结构与算法,第 12 页,二叉树的重要性质,定义1 满二叉树(Full Binary Tree) 一棵深度为k 并且含有2 k-1个结点的二叉树. 特点:每层上的结点数都达到最大结点个数 定义2 完全二叉树(Complete Binary Tree) 一棵深度为k 的二叉树，除第k 层外，
7、其它各层 (1 k-1) 的结点数都达到最大个数，第k 层从右向左连续缺若干结点，这就是完全二叉树,第二节 二叉树 Binary Tree,数据结构与算法,第 13 页,二叉树的重要性质,定义1 满二叉树(Full Binary Tree) 一棵深度为k 并且含有2 k-1个结点的二叉树. 特点:每层上的结点数都达到最大结点个数 定义2 完全二叉树(Complete Binary Tree) 一棵深度为k 的二叉树，除第k 层外，其它各层 (1 k-1) 的结点数都达到最大个数，第k 层从右向左连续缺若干结点，这就是完全二叉树 说明 若对深度为k 的满二叉树的结点从根结点开始自上向下，自左至右
8、顺序编号，如图（a）中每个结点斜上角的数字。 若对深度为k ，含有n 个结点的完全二叉树按同样方法编号，则每个结点的编号与相应满二叉树结点的编号从1 到n 一一相应，如图(b)所示。 而图(c)则不是完全二叉树,第二节 二叉树 Binary Tree,数据结构与算法,第 14 页,二叉树的重要性质,性质4 具有 n 个结点的完全二叉树的深度为 log2(n) +1 (其中 x 表示不大于x的最大整数) 证明：设完全二叉树的高度为h，则有 2h-1 - 1 n 2h - 1 或 2h-1 n 2h 取对数 h-1 log2(n) h 是整数 h-1 log2(n) h,第二节 二叉树 Binar
9、y Tree,数据结构与算法,第 15 页,二叉树的重要性质,性质5 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1, 2, , n，那么，对于编号为i (1 i n) 的结点,则有以下关系： 若i = 1,则该结点为根，无双亲结点 若i 1,则该结点的双亲结点编号为i /2 若2i n,则有编号为2i 的左孩子，否则没有左孩子 若2i+1 n,则有编号为2i+1的右孩子，否则没有右孩子 若 i 为奇数,且i != 1,则其左兄弟编号为i-1 若 i 为偶数,且i != n,则其右兄弟编号为i+1,第二节 二叉树 Binary Tree,数据结构与算法,第 16 页
10、,二叉树的顺序存储结构,用一组连续的的存储单元存放二叉树中的元素，即按满二叉树的形式存放在一维数组中 结点的编号恰好与数组元素的下标相对应 根据二叉树性质5，结点在一维数组中的相对位置隐含着结点之间的关系 适用于满二叉树和完全二叉树,根据二叉树性质5，在数组中可以方便地由某结点的 下标找到它们的双亲结点，或左、右孩子结点,存储示例,(a)完全二叉树的数组表示,(b)一般二叉树的数组表示,第二节 二叉树 Binary Tree,数据结构与算法,第 17 页,二叉树的顺序存储结构,由于在顺序存储结构中是以结点在数组中的相对位置表示结点之间的关系，因此，一般二叉树也必须以完全二叉树的形式来存储，可能
11、会造成存储空间的浪费。 单支树就是一个极端情况。例如，深度为k 的单支二叉树，它只有k个结点却需要2k-1个存储单元。,第二节 二叉树 Binary Tree,数据结构与算法,第 18 页,二叉树的链式存储结构,最常用的是二叉链表和三叉链表 二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指向右孩子。 结点结构描述为： typedef struct btnode ElemType data; /* 数据域*/ struct btnode *lchild; /* 左孩子指针域*/ struct btnode *rchild; /* 右孩子指针域*/ BTNode;,第二节
12、二叉树 Binary Tree,数据结构与算法,第 19 页,二叉树的链式存储结构,三叉链表的结点比二叉链表结点多一个指向双亲的指针域。 结点结构描述为： typedef struct btnode_p ElemType data; struct btnode *lchild; /* 左孩子指针域*/ struct btnode *rchild; /* 右孩子指针域*/ struct btnode *parent; /* 双亲指针域*/ BTNode_p;,第二节 二叉树 Binary Tree,数据结构与算法,第 20 页,二叉树的链式存储结构,bt 是一个 *BTNode 类型的变量，指向
13、根结点，对于二叉链表的操作都是从它开始的,存储示例,第二节 二叉树 Binary Tree,数据结构与算法,第 21 页,建立二叉树的二叉链表,建立二叉链表的方法不止一种。这里介绍的方法的原理是利用二叉树的性质5。 对于一棵任意的二叉树，先按满二叉树对其结点进行编号，如下图所示。虽然此二叉树并非满二又树，结点的编号并不连续，但结点编号之间的关系是满足二叉树的性质5的。,第二节 二叉树 Binary Tree,数据结构与算法,第 22 页,算法实现,设置一个辅助指针数组p ,pi 中存放编号为i的结点的指针 根据二叉树，按结点编号i 和数据 ch 建立数据表，按此表一一输入数对,每输入一对数（i
14、，ch），便产生一个新的结点s ，同时将该结点的指针保存在 pi 中； 当i=1 时，所产生的结点为根结点 当i1 时，由性质5可知：其双亲结点的编号 j=i/2 若 i 为偶数，它是双亲的左孩子，则 pj-lchild=pi 若 i 为奇数，它是双亲的右孩子，则 pj-rchild=pi 这样就将每个结点与其双亲结点相连，从而建立起了二叉链表,第二节 二叉树 Binary Tree,数据结构与算法,第 23 页,算法实现,/*算法5.1 建立二叉链表 */ #define MAXNUM 20 /*最大结点数*/ BtNode *pMAXUNM+1; /* 辅助指针数组*/ BtNode *
15、Creat_Bt( ) printf(“n enter i,ch:“); scanf(“%d%c“, ,PART,3,遍历二叉树 (Binary Tree Traversal),第 25 页,相关 定义,第三节遍历二叉树 (Binary Tree Traversal),数据结构与算法,遍历二叉树 以某种次序访问二叉树中的每个结点，且每个结点仅被访问一次 访问 如查询结点数据域的内容、输出结点的数据、修改结点的数据或是执行对结点的其他操作 设 访问根结点 记作 T 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有: TLR,TRL,LTR, RTL,LRT,RLT 取三种遍历次序 TLR 先根遍历 LTR 中根遍历 LRT 后根遍历,第 26 页,遍历 方法,第三节遍历二叉树 (Binary Tree Traversal),数据结构与算法,为了便于理解遍历思想，暂时为右图示的二叉树中每个没有子树的结点均补充上相应的空子树，用表示。 设想有一条搜索路线(用虚线表示)，它从根结点的左支开始，自上而下自左至右搜索，最后由根结点右支向上出去。恰好搜索线途经每个有效结点都是三次。 第一次经过时访问的结点是：A、B、D、C 先根遍历 第二次经过才访问的结点是：B、D、A、C 中根遍历 第三次经过才访问的结点是：D、B、C、A 后根遍历,第 27 页,先根 遍
