第6章 树和二叉树.ppt

《第6章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第6章 树和二叉树.ppt（99页珍藏版）》请在优知文库上搜索。

1、第第6章章 树和二树和二叉树叉树本章主要内容本章主要内容树结构广泛存在树结构广泛存在6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 赫夫曼树及其应用赫夫曼树及其应用6.1 树的定义和基本术语树的定义和基本术语一、树的定义一、树的定义P118 树树(Tree)是是n(n=0)个结点的有限集，在任意一棵非空树中个结点的有限集，在任意一棵非空树中(1)有有且仅有一个特定的称为根（且仅有一个特定的称为根（Root）的结点；（）的结点；（2）当）当n1时，其时，其余结点棵分为余结点棵分为m(m0)个互不相

2、交的有限集个互不相交的有限集T1,T2,Tm,其中每其中每一个集合本身又是一棵树，并且称为根的子树（一个集合本身又是一棵树，并且称为根的子树（SubTree）。）。基本术语基本术语P120二、树的表示法二、树的表示法P120三、树的逻辑结构：非线性结构三、树的逻辑结构：非线性结构-层次结构层次结构四、树的基本操作：初始化、建树、清空、求树的深度、找双亲、四、树的基本操作：初始化、建树、清空、求树的深度、找双亲、找孩子、插入、删除、遍历等找孩子、插入、删除、遍历等五、五、ADT示示张张1311张张1312张张2221张张2221张张2221张张111张张131张张132张张221张张222张张2

3、23张张331张张341张张11张张12张张13张张21张张22张张31张张32张张33张张34张张1张张2张张3张源张源族普族普-家族家族树树称为称为子树子树T1子树子树T2子树子树T3结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素数据元素+若干指向子树的分支若干指向子树的分支分支的个数分支的个数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点DHIJM(从根到结点的)路径路径：孩子孩子结点结点、双亲双亲结点结点、兄弟兄弟结点结点、堂兄弟堂兄弟祖先祖先结点结点、子孙子孙结点结点结点的层次结点的层次:树

4、的深度：树的深度：由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组 Tree=（root，F）其中：其中：root 被称为根结点，F 被称为子树森林森林：森林：是 m（m0）棵互不相交的树的集合ArootBEFKLCGDHIJMF (1)有确定的根有确定的根 (2)树根和子树根之间为有向关系树根和子树根之间为有向关系有向树有向树：有序树：有序树：子树之间存在确定的次序关系子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。子树之间不存在确定的次序关

5、系。对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素(开始结点开始结点)(无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(终端结点终端结点)(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个直接前驱、一个直接前驱、一个直接后继一个直接后继)其它数据元素其它数据元素(一个直接前驱、一个直接前驱、多个直接后继多个直接后继)树的表示法树的表示法1、树型图表示法树型图表示法：2、嵌套集合表示法：、嵌套集合表示法：3、凹入表表示法：、凹入表表示法：4、广义表表示

6、法广义表表示法：(A(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根广义表表示法广义表表示法数据对象数据对象 D：D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合。若若D为空集，则称为空树；为空集，则称为空树；否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互 不相交的有限集不相交的有限集T1,T2,Tm,其中每一其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系 R：基本操

7、作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类 Root(T)/求树的根结点求树的根结点 查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历InitTree

8、(&T)/初始化置空树初始化置空树 插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空 删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树6.2 二叉树本节主要内容本节主要内容6.2.1 二叉树的定义二叉树的定义6.2.

9、2 二叉树的性质二叉树的性质6.2.3 二叉树的存储结构二叉树的存储结构6.2.1 二叉树的定义一、二叉树的定义一、二叉树的定义P121二、二叉树的基本形态二、二叉树的基本形态P123三、二叉树的逻辑结构：非线性结构三、二叉树的逻辑结构：非线性结构-层层次结构次结构四、二叉树的基本操作：四、二叉树的基本操作：初始化、建树、清空、初始化、建树、清空、求树的深度、找双亲、找孩子、插入、删除、遍求树的深度、找双亲、找孩子、插入、删除、遍历等历等五、五、ADTP121122 二叉树或为空树空树；或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCD

10、EFGHK根结点左子树右子树EF由二叉树的定义知由二叉树的定义知:二叉树只有五种基本形态二叉树只有五种基本形态N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树6.2.2 二叉树的性质二叉树的性质性质性质1、在二叉树的第、在二叉树的第i层上至多有层上至多有2i-1个结点（个结点（i1）。）。性质性质2、深度为、深度为k的二叉树至多有的二叉树至多有2k-1个结点（个结点（k1）。）。性质性质3、对任何一棵二叉树、对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0，度为度为2的结点数的结点数为为n2，则：，则

11、：n0=n2+1分析分析 例例满二叉树满二叉树：一棵深度为：一棵深度为k且有且有2k-1个结点的二叉树称为满个结点的二叉树称为满二叉树。二叉树。P124完全二叉树完全二叉树：若一棵二叉树至多只有最下面的两：若一棵二叉树至多只有最下面的两层上结点的度数可以小于层上结点的度数可以小于2，并且，最下一层上，并且，最下一层上的结点都集中在该层最左边的若干位置上，则的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。此二叉树称为完全二叉树。例例 注注性质性质4、具有具有n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为：log2n +1分析分析：令二叉树的深度为：令二叉树的深度为k，从

12、而，从而，2k-1-1n 2k-1深度为深度为k-1的满二叉的满二叉树的结点数树的结点数深度为深度为k的的满二叉树满二叉树的结点数的结点数 2k-1 n 2k k-1 log2n1，则其双亲，则其双亲PARENT(i)是结点是结点 i/2。(2)如果如果2in，则结点，则结点i无左孩子（结点无左孩子（结点i为叶子为叶子结点）；否则其左孩子结点）；否则其左孩子LCHILD(i)是结点是结点2i。(3)若若2i+1n，则结点，则结点i无右孩子；否则其右孩无右孩子；否则其右孩子子RCHILD(i)是结点是结点2i+1。注：可以用数学归纳法证明之，学生自己证明，我们用其结论。注：可以用数学归纳法证明之

13、，学生自己证明，我们用其结论。完全二叉树完全二叉树T123456789101112 对有对有n个结点的完全二叉树个结点的完全二叉树T从上到下从上到下且每层从左至右进行且每层从左至右进行1至至n的连续编号的连续编号 观察编号为观察编号为i的结点的双亲、左孩子、右的结点的双亲、左孩子、右孩子的编号情况孩子的编号情况注：注：由完全二叉树的定义有以下结论：由完全二叉树的定义有以下结论：（1）叶子结点只可能在层次最大的两层上出现）叶子结点只可能在层次最大的两层上出现（最下两层）；（最下两层）；（2）满二叉树一定是完全二叉树，反之不然；）满二叉树一定是完全二叉树，反之不然；（3）完全二叉树中，若某结点无左

14、孩子，则该结）完全二叉树中，若某结点无左孩子，则该结点一定无右孩子；点一定无右孩子；（4）对任一结点，若其右分支下的子孙的最大层）对任一结点，若其右分支下的子孙的最大层次为次为k，则其左分支下的子孙的最大层次必为，则其左分支下的子孙的最大层次必为k或或k+1。例、判定以下树中，哪些是满二叉树，哪些例、判定以下树中，哪些是满二叉树，哪些是完全二叉树是完全二叉树。456789101112321131415是：完全二叉树，且是满二叉树是：完全二叉树，且是满二叉树456789321101112不是完全二叉树不是完全二叉树456789101112321456321不是完全二叉树不是完全二叉树是完全二叉树

15、是完全二叉树例1、设高度为设高度为h的二叉树的二叉树T无度为无度为1的结点，则的结点，则二叉树二叉树T至少有多少个结点？至多有多少个结点？至少有多少个结点？至多有多少个结点？若二叉树若二叉树T的叶子总数为的叶子总数为m，则二叉树，则二叉树T的结点的结点总数为多少？总数为多少？分析：分析：（1）由于二叉树）由于二叉树T无无1度结点，从而当从第二层至第度结点，从而当从第二层至第h层每层只有两个结点时，层每层只有两个结点时，T的总结点数最少，而第一的总结点数最少，而第一层只有树根，从而，层只有树根，从而，T至少有：至少有：2(h-1)+1=2h-1个结点；个结点；（2）由二叉树的性质）由二叉树的性质

16、2知，知，T至多有至多有2h-1个结点；个结点；（3）设）设n0、n1、n2、n分别为分别为T的叶子结点数、的叶子结点数、1度结度结点数、点数、2度结点数、结点总数，则有：度结点数、结点总数，则有：n0=m，n1=0 由二叉树的性质由二叉树的性质3有：有：n0=n2+1，有，有n2=n0-1 从而，从而，n=n0+n1+n2=n0+0+n0-1=2n0-1=2m-1 12n1i1)(Li其中：其中：Li为第为第i个结点所在的层次数个结点所在的层次数（假设根为第一层结点）。（假设根为第一层结点）。例例2、假设有、假设有n个叶子结点的二叉树个叶子结点的二叉树T中中所有非叶子结点都有左、右子树，则：所有非叶子结点都有左、右子树，则：T共有多少个结点？共有多少个结点？证明：证明：分析：分析：分别用分别用n0、n1、n2表示二叉树表示二叉树T中的中的度为度为0、1、2的结点数，依题意知的结点数，依题意知n0=n，又二叉树又二叉树T中中所有非叶子结点都有左、右所有非叶子结点都有左、右子树，从而子树，从而T中中无度为无度为1的结点，即的结点，即n1=0，由性质由性质3有有n2=n0-1=n-1，从而