数据结构第6章树和二叉树.ppt

《数据结构第6章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第6章树和二叉树.ppt（42页珍藏版）》请在三一办公上搜索。

1、1,第六章 树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义和实现,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.5 Huffman树与Huffman编码,2,对比树型结构和线性结构的结构特点,第一个数据元素(无前驱)最后一个数据元素(无后继)其它数据元素(一个前驱、一个后继),根结点(无前驱)多个叶子结点(无后继)其它数据元素(一个前驱、多个后继),3,6.1 树的类型定义,树 是 n(n 0)个结点的有限集 D，当n 1 时：1）有一个特定的结点 root 被称为根(结点);2）除根以外的结点被分成 m(m 0)个不相交的有限集T1,T2,Tm，其中每个集合又是一棵树，称

2、为根的子树。,4,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,树的基本术语,(从根到结点的)路径：,由从根到该结点所经分支和结点构成,5,孩子结点：结点的子树的根称为该结点的孩子双亲结点：B 结点是A 结点的孩子，则A结点是B结点的双亲兄弟结点：同一双亲的孩子之间互称兄弟堂兄弟结点：其双亲在同一层的结点互称堂兄弟祖先结点：从根到该结点所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙,6,孩子结点双亲结点兄弟结点堂兄弟结点祖先结点子孙结点,结点的层次:,树的深度

3、：,假设根结点的层次为1，第L层结点的子树的根结点层次为L+1,树中叶子结点所在的最大层次,7,有序树：子树之间存在确定的次序关系。最左边子树的根称为第一个孩子；最右边子树的根称为最后一个孩子。,森林：,是m（m0）棵互不相交的树的集合。,无序树：,不考虑子树的顺序。,8,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林,森林和树之间的联系：,一棵树去掉根后，其子树构成一个森林；一个森林增加一个根结点成为树。,9,(A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,树根,广义表,树的表示方法：层次结构；1）嵌套集合

4、；2）广义表；3）凹入表示法,10,ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若 D 为空集，则称为空树；若 D 中仅含一个数据元素，则关系R为空集；否则 R=H，(1)在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；(2)当n1时，其余数据元素可分为 m(m0)个互不相交的(非空)有限集 T1,T2,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 H,i=1,2,m。,树的抽象数据类型定义如下：,11,基本操作：,结构初始化InitTree(初始条件：树 T 存在。

5、操作结果：销毁树 T。,12,引用型操作TreeEmpty(T);初始条件：树 T 存在。操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。TreeDepth(T);初始条件：树 T 存在。操作结果：返回T的深度。Root(T);初始条件：树 T 存在。操作结果：返回 T 的根。,13,Value(T,cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：返回 cur_e 的值。Parent(T,cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 cur_e 是T的非根结点，则返回它的 双亲，否则返回“空”。LeftCh

6、ild(T,cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 cur_e 是T的非叶子结点，则返回它的最左孩子，否则返回空,14,RightSibling(T,cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回“空”。TraverseTree(T,visit();初始条件：树T存在，visit 是对结点操作的应用函数 操作结果：按某种次序对 T 的每个结点调用函数visit()一次且至多一次。一旦 visit()失败，则操 作失败。加工型操作Assign(初始条件：树T存在，cur

7、_e 是 T 中某个结点。操作结果：结点 cur_e 赋值为 value。,15,ClearTree(初始条件：树 T 存在，p 指向 T 中某个结点，1ip 指结点的度。操作结果：删除 T 中 p 所指结点的第 i 棵子树。,ADT Tree,16,定义 或为空树，或是由一个根结点和两棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。特性二叉树中每个结点最多有两棵子树；二叉树每个结点的度小于等于2子树有左右之分，不能颠倒有序树二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念,6.2 二叉树的类型定义和实现,17,二叉树与度为2的树相同吗？为什么？,答案：二叉树与度为2的树不

8、相同；1.度为2的树不能为空树，二叉树可以为空树。2.度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。,18,a、b两棵二叉树相同吗？为什么？,(a),(b),答案：不相同。因为，二叉树是有序树，而a和b两棵二叉树的左右子树不同。,19,二叉树的五种基本形态：,空树,只含根结点,右子树为空树,左子树为空树,左右子树均不为空树,20,二叉树的抽象数据类型定义如下：,ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。数据关系：若D为空集，则称为空树。

9、否则:(1)在D中存在唯一的称为根的数据元素 root；(2)当n 1时，其余结点可分为2个互不相交的有限集T1、T2，其中每一棵子集本身又是一棵符合本定义的二叉树，T1称为根 root 的左子树，T2称为根 root 的右子树。,21,基本操作：,初始化操作,InitBiTree(&T)操作结果：构造空二叉树 T。,DestroyBiTree(初始条件：二叉树 T 存在。操作结果：销毁二叉树 T。,结构销毁操作,CreateBiTree(&T,definition)初始条件：definition 给出二叉树 T 的定义。操作结果：按 definition 构造二叉树 T。,22,引用型操作,

10、Root(T)初始条件：二叉树 T 存在。操作结果：返回二叉树T的根结点。,Parent(T,e)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。,Value(T,e)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回e的值。,23,引用型操作（续）,LeftChild(T,e)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的左孩子。若 e 无左孩子，则返回空。,RightChild(T,e)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的右孩子。若 e 无右孩

11、子，则返回空。,24,引用型操作（续）,RightSibling(T,e)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的右兄弟。若 e 是其双亲的 右孩子或无右兄弟，则返回空。,LeftSibling(T,e)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的左兄弟。若 e 是其双亲的 左孩子或无左兄弟，则返回“空”。,25,引用型操作（续）,BiTreeEmpty(T);初始条件：二叉树 T 存在。操作结果：若T为空二叉树，则返回 TRUE，否则返回 FALSE。,BiTreeDepth(T)初始条件：二叉树 T 存在。操作结果：返回 T

12、的深度。,26,引用型操作（续）,PreOrderTraverse(T,Visit()根左右初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败，则操作失败。,InOrderTraverse(T,Visit()左根右初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit()失败，则操作失败。,27,引用型操作（续）,PostOrderTraverse(T,Visit()左右根初始条件：二叉树 T

13、 存在，visit 是对结点操作的应用函数。操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败，则操作失败。,LevelOrderTraverse(T,Visit()初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败，则操作失败。,28,加工型操作,InsertChild(&T,p,LR,c)初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。操作结果：根据 LR 为 0 或

14、1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成为 c 的右子树。,29,加工型操作,DeleteChild(初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。,30,加工型操作（续）,ClearBiTree(&T)初始条件：二叉树 T 存在。操作结果：将二叉树 T 清为空树。,ADT BinaryTree,Assign(&T,&e,value)初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：结点 e 赋值为 value。,31,性质 1 在二叉

15、树的第 i 层上至多有2i-1 个结点。(i1),证明：用归纳法证明,当i=1时，只有根结点1个结点，2i-1=20=1，结论成立；假设，当i=j时，命题成立；即第j层最多有2j-1个结点；当i=j+1时，即第j+1层 第j+1层的结点是由第j层的孩子组成；又 二叉树上每个结点最多有两个孩子；第j+1 层最多有 2j-12=2j=2(j+1)-1 个结点。结论成立；,二叉树的重要特性,32,性质 2 深度为 k 的二叉树上至多含 2k-1 个结点(k1)。,证明：,由性质1，第i层至多有2i-1个结点 深度为k的二叉树，最多共有 20+21+2k-1个结点 而 20+21+2k-1=2k-1。

16、公式：(1-x)(1+x1+x2+xn-1)=1-xn,33,性质 3 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。,证明：,设二叉树上总结点数为 n，度为1的结点数为n1；则 n=n0+n1+n2 设B为二叉树中分支总数，除根结点外，每个结点都有一个分支进入，则 B=n-1 二叉树中所有分支是由度为1的结点和度为2的结点射出的，度为1的结点射出一条边，度为2的结点射出2条 B=n1+2n2 由、可得：n0=n2+1。,34,满二叉树：深度为 k，且有 2k-1 个结点的二叉树；特点：每一层上的结点数都是最大数目。结点层序编号方法：从根

17、结点起自上而下逐层（层内自左至右）对二叉树的结点进行连续编号。,两类特殊的二叉树：,35,完全二叉树：一棵深度为 k 有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。特点：叶子结点只可能在层次数最大的两层上出现。只有最下一层的结点数可能未达到最大值。对任一结点，如果其右子树的最大层次为 L，则其左子树的最大层次为 L或 L1。完全二叉树结点数2k-1-1n2k-1满二叉树一定是完全二叉树，反之不成立。,36,是完全二叉树吗？,37,Q1：满二叉树和完全二叉树有什么区别？答案：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-

18、1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。,Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？答案：因为只有这两种形式可以实现顺序存储！,38,性质 4 具有 n 个结点的完全二叉树的深度为 log2n+1,证明：,设完全二叉树的深度为 k，根据第二条性质，对深度为k的满二叉树共有2k-1个结点，深度为k-1的满二叉树共有2k-1-1个结点。n个结点的完全二叉树（深度为k）2k-1-1 n 2k-1，即 2k-1 n 2k k-1log2n k又k为深度，只能是整数，k=log2n+1。说明：x 取下界，即取不超过x的最大整数,39,Q3:一棵深度

19、为6的满二叉树有 个分支结点和 个个叶子。答案：满二叉树没有度为1的结点，所有分支结点都是二度结点。前5层结点都为分支结点，共25-1=31个，或利用公式n0=n2+1，n1+n2=0+n2=n0-1=31叶子结点都在第6层，共26-1=32。一棵具有257个结点的完全二叉树，它的深度为。答案：利用公式k=log2n+1=log2257+1=9一棵含有n（n1）个结点的k叉树，可能达到的最大深度为，最小深度为。答案：当k=1(单叉树)时应该最深，深度n（层）；当k=n-1（n-1叉树）时应该最浅，深度2（层）；,31,32,9,2,n,40,Q4:设一棵完全二叉树具有1000个结点，则它有 个

20、叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。,489,1,0,答案：易求出总层数和末层叶子数。总层数k=log2n1=10;/（210）=1024且前9层总结点数为29-1=511(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。,41,请注意：叶子结点总数末层叶子数！还应加上第k-1层（靠右边）的0度结点个数。分析：末层的489个叶子只占据了上层的245个结点（489/2)，上层(k=9)右边的0度结点数还有 29-1-245=11个！,第i层上的满结点数为2i-1,所以，全部叶子数489(末层)11(k-1层)=500个。度为2的结点叶子总数1=499个。（n0=n2+1),42,另一法：可先求2度结点数,再由此得到叶子总数。首先，前k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度2，（共有489/2244个）。所以全部2度结点数为255(k-2层)244(k-1层)=499个；总叶子数2度结点数1=500个。,