课件：第二章 树、二叉树

1、NO：1第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树 树型结构是一类很重要的树型结构是一类很重要的非线性非线性数据结数据结构，在这类结构中，元素结点之间存在明显构，在这类结构中，元素结点之间存在明显的的分支分支和和层次层次关系。关系。 树型结构在客观世界中广泛应用，例如树型结构在客观世界中广泛应用，例如家族关系中的家谱、各种社会组织机构、一家族关系中的家谱、各种社会组织机构、一本书中的章节划分、操作系统中的多级目录本书中的章节划分、操作系统中的多级目录结构等。结构等。 本节主要讨论树及二叉树的定义及其存本节主要讨论树及二叉树的定义及其存储结构，重点

2、讨论二叉树的特性以及应用。储结构，重点讨论二叉树的特性以及应用。线性结构的特点是前驱和后继的数目都线性结构的特点是前驱和后继的数目都不超过不超过1非线性就是可能存在非线性就是可能存在多个多个前驱和后继前驱和后继可能存在多个后继，但可能存在多个后继，但前驱数不超过前驱数不超过1的非线性的非线性结构称为树结构称为树NO：2第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树一、树的定义及其存储结构一、树的定义及其存储结构1.1. 树的定义和术语树的定义和术语 树的定义树的定义1 1）定义：定义：树是由树是由n(nn(n 0)0)个结点组成的有限集个结点组成的有

3、限集合合T T，其中其中有且仅有有且仅有一个结点没有前驱称为一个结点没有前驱称为根根( (rootroot) )。n1n1时，除根外，其余结点可以分为时，除根外，其余结点可以分为m(mm(m0)0)个互不相交的有限集合个互不相交的有限集合T T1 1、T T2 2、T Tm m，其中每一个集合其中每一个集合T Ti i本身又是一棵树，称为根结本身又是一棵树，称为根结点点rootroot的的子树子树。2 2）树是一种树是一种递归递归结构结构, ,如图。树的定义也是递如图。树的定义也是递归的。归的。ABDKEFLMJIHGCT1T2T3rootNO：3第二章第二章 常用数据结构及其运算常用数据结构

4、及其运算2.5 2.5 树与二叉树树与二叉树 常用术语常用术语1 1）结点：结点：表示树中的元素。如表示树中的元素。如A A、B B、K K等等2 2）度：度：结点拥有的子树数。如结点拥有的子树数。如A A的度为的度为3 3，C C的的度为度为1 1。一棵树中最大的结点度数为这棵树的。一棵树中最大的结点度数为这棵树的度。上图中树的度为度。上图中树的度为3 3。3 3）叶结点：叶结点：没有后继结点没有后继结点( (度为度为0 0) )的结点的结点4 4）孩子：孩子：结点的子树的根。结点的子树的根。5 5）双亲：双亲：相应地，该结点称为孩子的双亲相应地，该结点称为孩子的双亲ABDKEFLMJIHG

5、CT1T2T3root1234NO：4第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树6 6）子孙：子孙：以某结点为根的子树中的任一结点称为以某结点为根的子树中的任一结点称为该结点的子孙。该结点的子孙。7 7）祖先：祖先：从根到该结点所经分支上的所有结点。从根到该结点所经分支上的所有结点。8 8）兄弟：兄弟：同一双亲的孩子。同一双亲的孩子。9 9）结点的层次：结点的层次：从根结点开始算起，根为第一层，从根结点开始算起，根为第一层，根的直接后继结点为第二层，以此类推。根的直接后继结点为第二层，以此类推。1010）深度：深度：树中结点的最大层次数。树中结点

6、的最大层次数。ABDKEFLMJIHGCT1T2T3root1234NO：5第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树1111）森林：森林：是是m(m0)m(m0)棵互不相交的树的集合棵互不相交的树的集合1212）有序树：有序树：树中结点在同层中按从左到右有树中结点在同层中按从左到右有序排列、不能互换的称为有序树；反之称为无序排列、不能互换的称为有序树；反之称为无序树。序树。BDKEFLMJIHGCT1T2T31234ANO：6第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树 树的存储结构树的存储结构1

7、1）树是多分支非线性表，因此需要采用）树是多分支非线性表，因此需要采用多重多重链表链表结构，即每个结点设有结构，即每个结点设有多个指针域多个指针域，其中，其中每一个指针指向一棵子树的根结点。每一个指针指向一棵子树的根结点。由于树的结点度各不相同，导致链表结点所需的由于树的结点度各不相同，导致链表结点所需的存储单元的长度也各不相同，这就导致对树的处存储单元的长度也各不相同，这就导致对树的处理算法变得非常复杂。理算法变得非常复杂。需要用需要用后继数目后继数目相对相对固定固定的树结构来表示普通树的树结构来表示普通树的结构的结构NO：7第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.

8、5 树与二叉树树与二叉树 二叉树的定义及其存储结构二叉树的定义及其存储结构1 1）二叉树是）二叉树是n(nn(n0)0)个结点的有限集合个结点的有限集合，它或它或为空树为空树( (n=0)n=0)，或由一个根结点和两棵分别称或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。为左子树和右子树的互不相交的二叉树构成。这也是一个递归定义。这也是一个递归定义。2 2）二叉树采用二叉链表进行存储。每个结点）二叉树采用二叉链表进行存储。每个结点由由数据域数据域( (datadata) )、左指针域左指针域( (lchildlchild) )、右指针右指针域域( (rchildrchild)

9、 )组成。组成。3 3）二叉树及其结构如上图所示。）二叉树及其结构如上图所示。BADFEC A B F E D C NO：8第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树 二叉树的基本性质二叉树的基本性质1 1）二叉树的第）二叉树的第i i层上至多有层上至多有2 2i-1i-1(i1)(i1)个结点个结点 第第1 1层只有根结点，第层只有根结点，第2 2层最多层最多2 2个结点个结点( (分别是根的左右分别是根的左右儿子儿子) )，第，第3 3层最多层最多4 4个结点，。个结点，。 第第i-1i-1层最多有层最多有n ni-1i-122i-2i-2个

10、结点，那么第个结点，那么第i i层就最多有层就最多有2 2* *2 2i-2i-2个结点个结点( (每个结点最多有每个结点最多有2 2个儿子个儿子).). 2 2）高度为）高度为k k的二叉树中至多含有的二叉树中至多含有2 2k k-1-1个结点。个结点。 将将k k层结点数加起来，并代入性质层结点数加起来，并代入性质1 1 n n1 1+n+n2 2+n+n3 3+ + +n nk k 1+2+4+8+2k-1 等比数列求和公式可得等比数列求和公式可得126574312111098NO：9第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二叉树树与二叉树3）在任意二叉

11、树中，若有）在任意二叉树中，若有n0个叶子结点，个叶子结点，n2个个度为度为2的结点，则必有：的结点，则必有：n0=n2+1。证明：设证明：设n1为度为为度为1的结点，则结点总数为的结点，则结点总数为 n=n0+n1+n2； 二叉树中的结点除了根结点外，都是度为二叉树中的结点除了根结点外，都是度为1或者度为或者度为2的结点的后继，度为的结点的后继，度为1的结点有一个的结点有一个后继，度为后继，度为2的结点有的结点有2个后继，因此个后继，因此 n-1=n1+2n2联立上二式，得：联立上二式，得： n0=n2+1NO：10第二章第二章 常用数据结构及其运算常用数据结构及其运算2.5 2.5 树与二

12、叉树树与二叉树4) n个结点的二叉树的高个结点的二叉树的高h至少是至少是log2n+1，即，即 hlog2n+1 表示取整表示取整 根据性质根据性质2，有：，有：n2h-1 所以所以 n log2n h是整数，是整数， log2n是实数，既然是实数，既然h log2n，当然就大于，当然就大于h log2n的整数部分，即的整数部分，即 h log2n一个整数大于另一个整数，至少比这个整数大一个整数大于另一个整数，至少比这个整数大1，即，即 hlog2n+1 NO：112.5 2.5 树与二叉树树与二叉树126574315141312111098第二章第二章 常用数据结构及其运算常用数据结构及其运

13、算 几种特殊形式的二叉树几种特殊形式的二叉树1 1）满二叉树：满二叉树：深度为深度为h h且含有且含有2 2h h-1-1个结点的二个结点的二叉树。如图所示深度为叉树。如图所示深度为4 4的满二叉树，结点编的满二叉树，结点编号是自上至下、自左至右。号是自上至下、自左至右。2 2）完全二叉树：完全二叉树：如果一棵有如果一棵有n n个结点的二叉树个结点的二叉树按与满二叉树相同的编号方式对结点进行编号，按与满二叉树相同的编号方式对结点进行编号，若树中若树中n n个结点和满二叉树个结点和满二叉树1 1n n编号完全一致，编号完全一致，则称该二叉树为完全二叉树。如图所示：则称该二叉树为完全二叉树。如图所

14、示：126574312111098126574312111098而上面的这个树就不是完全二叉树。而上面的这个树就不是完全二叉树。NO：122.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算完全二叉树只能从完全二叉树只能从满二叉树满二叉树中中依次依次删去删去编号最大编号最大的若的若干个结点干个结点(也可以一个结点也不删也可以一个结点也不删)，所以它的叶结点，所以它的叶结点编号一定是连续的编号一定是连续的完全二叉树是满二叉树的一部分，而满二叉树是完全完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例二叉树的特例NO：132.5 2.5 树与二叉树树与

15、二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算完全二叉树的二个重要性质：完全二叉树的二个重要性质： 一棵具有一棵具有n个结点的完全二叉树的高度为个结点的完全二叉树的高度为log2n+1由完全二叉树的定义可得：由完全二叉树的定义可得： 2k-1-1 n 2k-1 (大于大于k-1层结点个数，小于等于二叉树结点最大值）层结点个数，小于等于二叉树结点最大值）考察考察 2k-1-1 n 2k-1 n (n为整数，因此至少大为整数，因此至少大1)同理同理, n 2k-1 n 2k所以所以, 2k-1 n 2k取对数取对数 k-1 log2n log2n NO：142.5 2.5 树与二叉树

16、树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 编号为编号为i (1in)的结点的父亲和左右儿子的编号满的结点的父亲和左右儿子的编号满足下列条件：足下列条件：(1) 若若i=1，则，则 i 无父结点无父结点(它是根结点它是根结点); 否则否则(i1)它的父结点的它的父结点的 编号为：编号为： father(i) = i / 2(2) 若若2i n, 则则 i 无左儿子无左儿子; 否则否则(2in)其左儿子的编号为：其左儿子的编号为： Lson(i) = 2i(3) 若若2i+1n, 则则 i 无右儿子无右儿子; 否则否则(2i+1n)其右儿子编号为：其右儿子编号为： Rson

17、(i) = 2i + 1 A B D H I C G J K E F L 124895101163712对照上图验证对照上图验证由此性质可知，满二叉树和完全二叉树从结点编号可以方便的由此性质可知，满二叉树和完全二叉树从结点编号可以方便的确定结点的父子关系，因此可用顺序存储确定结点的父子关系，因此可用顺序存储NO：15完全二叉树的顺序表表示完全二叉树的顺序表表示普通二叉树的顺序表表示普通二叉树的顺序表表示2.5 2.5 树与二叉树树与二叉树NO：16 单支树单支树NO：172.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算3 3）平衡二叉树：平衡二叉树：平

18、衡二叉树又称平衡二叉树又称AVLAVL树，树，（Adelson-VerskiiAdelson-Verskii and Landis, and Landis,阿德尔逊阿德尔逊- -弗弗斯基斯基- -兰迪斯树），它或者是一棵空树，或者兰迪斯树），它或者是一棵空树，或者是具有下列是具有下列性质性质的二叉树：它的左子树和右子的二叉树：它的左子树和右子树都是平衡二叉树，且树都是平衡二叉树，且左子树和右子树的深度左子树和右子树的深度之差的绝对值不超过之差的绝对值不超过1 1。我们把结点的左子树。我们把结点的左子树深度减去它的右子树深度定义为结点的深度减去它的右子树深度定义为结点的平衡因平衡因子子，因此平衡

19、二叉树上所有结点的平衡因子只，因此平衡二叉树上所有结点的平衡因子只可能是可能是-1-1、0 0、1 1。只要二叉树上有一个结点的。只要二叉树上有一个结点的平衡因子绝对值大于平衡因子绝对值大于1 1，则该二叉树就是不平，则该二叉树就是不平衡的。衡的。如上图所示：如上图所示：1254376非平衡二叉树非平衡二叉树1256437平衡二叉树平衡二叉树125436非平衡二叉树非平衡二叉树NO：182.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 一般树转换为二叉树一般树转换为二叉树1 1）为了让一般树也能像二叉树一样用二叉链）为了让一般树也能像二叉树一样用二叉链

20、表表示，必须找出树与二叉树之间的关系，这表表示，必须找出树与二叉树之间的关系，这样当给定一棵树时，可以找到唯一的一棵二叉样当给定一棵树时，可以找到唯一的一棵二叉树与之对应，而且这种关系的逆变换也是存在树与之对应，而且这种关系的逆变换也是存在的。的。2 2）一般树中的结点次序没有要求，为了得到一般树中的结点次序没有要求，为了得到对应的二叉树，则需对树中每个孩子结点进行对应的二叉树，则需对树中每个孩子结点进行自左至右的排序。自左至右的排序。NO：192.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 对每个结点，除了与它的第一个孩子保对每个结点，除了与它的第

21、一个孩子保持联系外，去除与其它孩子的联系；持联系外，去除与其它孩子的联系；EACBDIHGFEACBDIHGFEACBDIHGFEACBDIHGF3 3）将一般树转换为二叉树的方法为将一般树转换为二叉树的方法为：（如图）（如图） 以树根为轴心，将整棵树顺时针旋以树根为轴心，将整棵树顺时针旋 转转4545。即纵向为左，横向为右。即纵向为左，横向为右。 改变形状；改变形状；在兄弟结点之间加一连线；在兄弟结点之间加一连线；EACBDIHGFEACBDIHGF 图中可以看到，在等价的二叉树中，一个结点图中可以看到，在等价的二叉树中，一个结点的左孩子是该结点的第一个孩子，而右孩子是的左孩子是该结点的第一

22、个孩子，而右孩子是该结点的兄弟，根结点的右子树为空（因为根该结点的兄弟，根结点的右子树为空（因为根没有兄弟）。依此特征，也可以将一棵等价的没有兄弟）。依此特征，也可以将一棵等价的二叉树转化为相应的树二叉树转化为相应的树NO：202.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 二叉树转换为一般树二叉树转换为一般树只有根结点没有右子树的二叉树才能转换为一棵只有根结点没有右子树的二叉树才能转换为一棵普通的树结构普通的树结构1) 二叉树的根为一般树的根二叉树的根为一般树的根2) 如果结点如果结点s在二叉树中是结点在二叉树中是结点f的左儿子，那么在的左儿子，那

23、么在一般树中就作为一般树中就作为f的第一个儿子的第一个儿子3) 如果结点如果结点s在二叉树中是结点在二叉树中是结点f的右儿子，那么在的右儿子，那么在一般树中一般树中s就作为就作为f的兄弟的兄弟ABCDFEGHIJKLMABCDEFGHLMKIJNO：212.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 森林转换成二叉树森林转换成二叉树1) 给森林增设一虚拟根结点，使森林中各树的根给森林增设一虚拟根结点，使森林中各树的根都作为该虚拟根的儿子，把森林变成一棵普通树都作为该虚拟根的儿子，把森林变成一棵普通树2) 用普通树转换成二叉树的方法将这棵树转换成用普通

24、树转换成二叉树的方法将这棵树转换成二叉树二叉树3) 删去虚拟根结点，而以虚拟根的左儿子为根，删去虚拟根结点，而以虚拟根的左儿子为根，就得到由森林转换的二叉树就得到由森林转换的二叉树DGIJKML虚根虚根BAHCENF虚根虚根AHCKNDEFGIJLMNO：222.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算由于二叉树结构和存储形式简单，对树运算的由于二叉树结构和存储形式简单，对树运算的算法描述也相对的简单一些，在程序设计中，算法描述也相对的简单一些，在程序设计中，如果要处理一棵普通树如果要处理一棵普通树(或森林或森林)，可以先将它，可以先将它转换成二叉

25、树，用二叉树有关算法去处理这棵转换成二叉树，用二叉树有关算法去处理这棵树，处理结束后，再将其还原成普通树树，处理结束后，再将其还原成普通树(或森林或森林)NO：232.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算三、二叉树的遍历三、二叉树的遍历遍历遍历是指循某条搜索路线依次访问某数据结构是指循某条搜索路线依次访问某数据结构中的全部结点，而且每个结点只被访问一次。中的全部结点，而且每个结点只被访问一次。 遍历二叉树的定义遍历二叉树的定义1 1）由于一棵非空二叉树是由）由于一棵非空二叉树是由根结点、左子树根结点、左子树和右子树和右子树三个基本部分组成，所以

26、遍历二叉树三个基本部分组成，所以遍历二叉树就是依次遍历这三部分。就是依次遍历这三部分。2 2）若我们以）若我们以D D、L L、R R分别表示访问根结点、遍分别表示访问根结点、遍历左子树、遍历右子树，则可以有以下历左子树、遍历右子树，则可以有以下6 6种形种形式：式：DLR,DRL,LDR,LRD,RDL,RLDDLR,DRL,LDR,LRD,RDL,RLD。NO：242.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算3 3）若规定先左后右，则有以下）若规定先左后右，则有以下3 3种形式：种形式：DLRDLR：前前( (先先) )序遍历序遍历LDRLDR

27、：中序遍历中序遍历LRDLRD：后序遍历后序遍历说明：其中的序是针对根结点来说的。说明：其中的序是针对根结点来说的。4 4）过程描述（以先序为例过程描述（以先序为例）：若二叉树为空，则为空操作，否则先访问根结若二叉树为空，则为空操作，否则先访问根结点，然后先序遍历左子树，再先序遍历右子树。点，然后先序遍历左子树，再先序遍历右子树。这是一个递归定义。这是一个递归定义。NO：252.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算5 5）举例：举例：如上图所示二叉树中，遍历的结果为：如上图所示二叉树中，遍历的结果为：先序先序( (DLR )：A B C D E

28、 F GA B C D E F G中序中序(LDR ) ：C B D A E G FC B D A E G F后序后序(LRD ) ：C D B G F E AC D B G F E A 遍历算法遍历算法1)1) 二叉树的先序遍历算法二叉树的先序遍历算法AGFDCEBNO：262.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算preorder(struct Btree *p) 0 if (p = NULL) return; 1 visit(p); / 处理根结点处理根结点 2 preorder(p-Lson); / 先序遍历左子树先序遍历左子树 3 pr

29、eorder(p-Rson); / 先序遍历右子树先序遍历右子树 4下面跟踪一下这个递归遍历算法，帮助大家理解下面跟踪一下这个递归遍历算法，帮助大家理解递归执行的概念递归执行的概念因为执行递归函数需要使用递归调用栈，在跟踪因为执行递归函数需要使用递归调用栈，在跟踪时将模拟递归栈的情况。假定递归栈采用时将模拟递归栈的情况。假定递归栈采用”保护现保护现场场”方式，每个栈架存放正在遍历的方式，每个栈架存放正在遍历的根结点根结点和和返返回地址回地址。ABCDEA, 3topA, 3B, 3topA, 3B, 4topA, 3B, 4topD, 3A, 3B, 4topD, 4A, 4top在递归调用在

30、递归调用之前，现场之前，现场(A,3)进栈，进栈，A表示当前表示当前遍历的树之遍历的树之根结点，根结点，3表示句表示句2执执行完后，要行完后，要执行句执行句3NO：272.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算（2）中序遍历）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子若二叉树为空，则结束遍历操作；否则中序遍历左子树；树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。inorder(structinorder(struct BtreeBtree * *p)p) if (p = NULL) return; if (p = NUL

31、L) return; inorder(pinorder(p-LsonLson); ); / / 中序遍历左子树中序遍历左子树 visit(pvisit(p); ); / / 处理根结点处理根结点 inorder(pinorder(p-RsonRson); ); / / 中序遍历右子树中序遍历右子树 NO：282.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算（3）后序遍历）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子若二叉树为空，则结束遍历操作；否则后序遍历左子树；树；后序遍历右子树；后序遍历右子树；访问根结点。访问根结点。postorder(

32、structpostorder(struct BtreeBtree * *p)p) if (p = NULL) return; if (p = NULL) return; postorder(ppostorder(p-LsonLson); ); / / 后序遍历左子树后序遍历左子树 postorder(ppostorder(p-RsonRson); ); / / 后序遍历右子树后序遍历右子树 visit(pvisit(p); ); / / 处理根结点处理根结点 NO：292.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 二叉树的遍历路线二叉树的遍历路线

33、(简便方法简便方法)当沿着遍历路线一周时，当沿着遍历路线一周时，1) 每当遍历路线从每当遍历路线从左侧左侧靠近一个结点时，就记下这靠近一个结点时，就记下这个结点，这样得到的结点序列就是个结点，这样得到的结点序列就是先序先序2) 从从正下方正下方靠近一个结点时，记下这个结点就得到靠近一个结点时，记下这个结点就得到中序中序序列序列3) 从从右侧右侧靠近一个结点时，记下这个结点就是靠近一个结点时，记下这个结点就是后序后序序列序列NO：302.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算D E FG HB CANO：312.5 2.5 树与二叉树树与二叉树第二

34、章第二章 常用数据结构及其运算常用数据结构及其运算 二叉树的中序遍历路线二叉树的中序遍历路线(另一方法另一方法)对一棵二叉树中序遍历时，若我们将二叉树严格地对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。的顺序就是该二叉树的中序遍历序列。NO：322.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据

35、结构及其运算常用数据结构及其运算D G B A E C H F G HD E FB CANO：332.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 按层次遍历二叉树按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列按层次顺序访问其中每个结点的遍历序列G HD E FB CA按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为： ABCDEFGHNO：342.5 2.5 树与二

36、叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算二叉树用顺序存储结构表示时，按层遍历的算法二叉树用顺序存储结构表示时，按层遍历的算法实现实现LevelOreder(QBTreeLevelOreder(QBTree BT) BT) for (i=0;i for (i=0;iif (!p-LchildLchild) ) Visite(pVisite(p- - Lchild);EnQueue(&Q,pLchild);EnQueue(&Q,p-LchildLchild); ); /处理左孩子处理左孩子 if (!p-if (!p-RchildRchild) ) Visite(pVi

37、site(p- - Rchild);EnQueue(&Q,pRchild);EnQueue(&Q,p-RchildRchild); ); /处理右孩子处理右孩子 2.5 2.5 树与二叉树树与二叉树NO：382.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 树的唯一性树的唯一性一棵二叉树的先序序列、中序序列、后序序列都一棵二叉树的先序序列、中序序列、后序序列都是唯一的，但不同的二叉树可能具有相同的先序是唯一的，但不同的二叉树可能具有相同的先序序列、或相同的中序序列、或相同的后序序列序列、或相同的中序序列、或相同的后序序列 如下图如下图5棵二叉树，先序序

38、列都是棵二叉树，先序序列都是ABCBBACACABCABCABC显然，单知道一棵二叉树的先显然，单知道一棵二叉树的先/中中/后序序列，无后序序列，无法确定这棵二叉树是怎么样的法确定这棵二叉树是怎么样的但是如果同时知道一棵二叉树的但是如果同时知道一棵二叉树的先序序列先序序列和和中序中序序列序列，或者同时知道，或者同时知道中序序列中序序列和和后序序列后序序列，就能，就能够确定这棵二叉树够确定这棵二叉树但已知但已知先序先序和和后序后序，二叉树仍不能唯一确定，二叉树仍不能唯一确定NO：392.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算2) 2) 遍历是二叉树

39、各种操作的基础，这里我们以遍历是二叉树各种操作的基础，这里我们以求二叉树中的叶子数为例说明：求二叉树中的叶子数为例说明：intint CountLeaf(BINTREECountLeaf(BINTREE * *t)t) if (!t) return(0); if (!t) return(0);/空树空树 elseelse if (!t- if (!t-lchild&!tlchild&!t-rchildrchild) )/只有根只有根 return(1);return(1); else else/其它情况，左右子树叶子之和其它情况，左右子树叶子之和 return(CountLeaf(tretur

40、n(CountLeaf(t-lchildlchild)+)+ CountLeaf(tCountLeaf(t-rchildrchild);); NO：402.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算交换二叉树的左右子树交换二叉树的左右子树： void void change_left_right(BTreechange_left_right(BTree BT) BT) if (BT) if (BT) change_left_right(BTchange_left_right(BT-lchildlchild);); change_left_right(

41、BTchange_left_right(BT-rchildrchild);); BT- BT-lchildlchildBT-BT-rchildrchild; ; NO：412.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算求二叉树的高度求二叉树的高度：首先分别求出左右子树的高度，首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大在此基础上得出该棵树的高度，即左右子树较大的高度值加的高度值加1。 intint hight(BTreehight(BTree BT) BT) /h1/h1和和h2h2分别是以分别是以BTBT为根的左右子树的高

42、度为根的左右子树的高度 if (BT=NULL) return 0;if (BT=NULL) return 0; else else h1= h1=hight(BThight(BT-lchildlchild);); h2= h2=hight(BThight(BT-rchildrchild);); return maxh1,h2+1; return maxh1,h2+1; NO：422.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算四、二叉树的应用四、二叉树的应用 二叉排序树二叉排序树1 1）定义：定义：二叉排序树或是空树，或是具有下二叉排序树或是空树，或

43、是具有下属性质的二叉树：属性质的二叉树：其左子树上所有结点的数据其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值；左子的数据值均大于或等于根结点的数据值；左子树和右子树又各是一棵二叉排序树。树和右子树又各是一棵二叉排序树。如上图所如上图所示。示。1031598921134218在二叉排序树中，若按中序遍历就可以得到有在二叉排序树中，若按中序遍历就可以得到有小到大的有序序列。上图小到大的有序序列。上图中序遍历中序遍历得到：得到： 2 2，3 3，4 4，8 8，9 9，9 9，1010，1313，1515，

44、1818，21 21 。 NO：432.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算2 2）生成：生成：二叉排序树是一种动态表结构，即二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向二叉排序树二叉排序树的生成过程是不断地向二叉排序树中插入新的结点。中插入新的结点。对任意一组元素序列生成一棵排序二叉树的过对任意一组元素序列生成一棵排序二叉树的过程为：程为： 二叉排序树初始为空，无序序列的第一个元素插入二叉排二叉排序树初始为空，无序序列的第一个元素插入二叉排序树，即为根结点；序树，即为根结点； 无序序列的第二个元素插入二叉排序树，与根结点比较，

45、无序序列的第二个元素插入二叉排序树，与根结点比较，小于根结点插入左子树，否则插入右子树；小于根结点插入左子树，否则插入右子树； 继续将无序序列的其他结点一一插入二叉排序树。继续将无序序列的其他结点一一插入二叉排序树。NO：442.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算1018371282310101810183101883101812831018128231018712823请看序列请看序列 1010，1818，3 3，8 8，1212，2 2，7 7，33 构构成一棵二叉排序树的过程。成一棵二叉排序树的过程。输入的无序序列的顺序不同，构造出的二

46、叉排序树的形式就输入的无序序列的顺序不同，构造出的二叉排序树的形式就不同，但中序遍历结果不变不同，但中序遍历结果不变NO：452.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算3 3）删除二叉排序树上的结点：删除二叉排序树上的结点：在二叉排序树在二叉排序树中删除一个结点时，必须将因删除结点而断开中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。树的性质不会失去。删除过程较为复杂，按照删除过程较为复杂，按照被删除结点在二叉排序树中的位置，可以有以被删除结点在二叉排序树中

47、的位置，可以有以下几种情况：下几种情况：首先设首先设p p为指向被删除结点为指向被删除结点P P的指针，的指针，f f为被删为被删除结点的双亲结点除结点的双亲结点F F的指针。且不失一般性，的指针。且不失一般性，可设可设p p是是f f的左指针的左指针。NO：462.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 被删除结点是叶子结点，则删除后不会被删除结点是叶子结点，则删除后不会影响整个二叉排序树的结构，因此只需要影响整个二叉排序树的结构，因此只需要修改它双亲结点的指针即可。修改它双亲结点的指针即可。 被删除结点只有左子树被删除结点只有左子树P PL

48、L或只有右子或只有右子树树P PR R，此时只要将其左子树或右子树直接此时只要将其左子树或右子树直接成为其双亲结点成为其双亲结点F F的左子树即可。的左子树即可。如图：如图：PFfpPLFfPL 若被删除结点若被删除结点P P的左右子树均非空，这的左右子树均非空，这时要找到时要找到P P的的中序前趋中序前趋S S，用结点，用结点S S代替代替P P， 并删除并删除P P。NO：472.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算如图：如图：P P的中序前趋的中序前趋 CL C QL Q SL S PCL C QL Q SL S q=p; s=p-lch

49、ildlchild; ; while (s- while (s-rchildrchild) ) q=s; s=s- q=s; s=s-rchildrchild; ; if (q=p) if (q=p) q- q-lchildlchild=s-=s-lchildlchild; ; else else q- q-rchildrchild=s-=s-lchildlchild; ; p-data=s-data; free(s); p-data=s-data; free(s); FCLPRfPCQSQLSLpqsFCLPRfSCQQLpqSLPFfpPLFfPLNO：492.5 2.5 树与二叉树树与二

50、叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 哈夫曼树哈夫曼树哈夫曼树哈夫曼树又称最优树，它是一类带权路径长度又称最优树，它是一类带权路径长度最短的树。最短的树。1 1）树的路径长度：树的路径长度：从树中一个结点到另一个从树中一个结点到另一个结点之间的分支数目称为这对结点之间的路径结点之间的分支数目称为这对结点之间的路径长度。树的路径长度是从树根到每一个叶子结长度。树的路径长度是从树根到每一个叶子结点的路径长度之和。路径长度用点的路径长度之和。路径长度用PLPL表示，上图表示，上图中两棵树的路径长度分别是：中两棵树的路径长度分别是：1764532(a)84736251(b)( (

51、a) PL=2+5=7a) PL=2+5=7(b) PL=3+2(b) PL=3+2* *3=93=9NO：502.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算2 2）树的带权路径长度：树的带权路径长度：结点带权路径长度为结点带权路径长度为从该结点到树根之间的路径长度与该结点上权从该结点到树根之间的路径长度与该结点上权值的乘积。树的带权路径长度为树中叶子结点值的乘积。树的带权路径长度为树中叶子结点的带权路径长度之和，记作：的带权路径长度之和，记作：nkkklwWPL1其中，其中，w wk k为树中每个叶子结点的权值，为树中每个叶子结点的权值，l lk

52、k为每为每个叶子结点到根结点的路径长度。个叶子结点到根结点的路径长度。WPLWPL最小最小的二叉树称最优二叉树或哈夫曼树。的二叉树称最优二叉树或哈夫曼树。NO：512.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算下图下图3 3棵二叉树的棵二叉树的WPLWPL分别是：分别是：abcd7 5 2 4dacb7542abcd7524( (a) WPL=7a) WPL=7* *2+52+5* *2+22+2* *2+42+4* *2=362=36(b) WPL=7(b) WPL=7* *3+53+5* *3+23+2* *1+41+4* *2=462=46(c

53、) WPL=7(c) WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=35 3=35 ( (哈夫曼树哈夫曼树) )假设假设a,b,c,d的权值都改为的权值都改为1，则？，则？在在n个结点的所有二叉树中，以完全二叉树个结点的所有二叉树中，以完全二叉树的路径长度最短的路径长度最短NO：522.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算 由给定的由给定的n n个权值个权值 w w1 1,w,w2 2, , ,w wn n 构成构成n n棵棵二叉树的集合二叉树的集合F=TF=T1 1,T,T2 2, , ,T Tn n(森林森林)

54、)，其，其中每棵二叉树只有一个权值为中每棵二叉树只有一个权值为W Wi i的根结点；的根结点； 在在F F中选取两棵根结点权值最小的树作中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上的二叉树的根结点的权值为其左右子树上根结点的权值之和；根结点的权值之和； 将新二叉树加入将新二叉树加入F F中，并去除原两棵树中，并去除原两棵树 重复、，直到重复、，直到F F中只含一棵树。中只含一棵树。3 3）哈夫曼树的构造哈夫曼树的构造a b c dab75c2d4b5c2d4ac2d4a b7 5 2 4 7 5 6

55、7 11 18(a) (b) (c) (d)NO：532.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算算法实现算法实现：存储结构描述：存储结构描述：由于哈夫曼树中由于哈夫曼树中没有度为没有度为 1 1 的结点，的结点，因此一棵有因此一棵有n n个叶子结点的哈夫曼树共个叶子结点的哈夫曼树共有有2 2n-1n-1个结点。结点采用数组型链表结个结点。结点采用数组型链表结构，每个结点由构，每个结点由4 4个数据域组成：个数据域组成：datadata：存放结点权指存放结点权指lchildlchild：左指针左指针rchildrchild：右指针右指针parent

56、parent：双亲指针双亲指针叶子结点个数叶子结点个数n根据性质：根据性质：n0=n2+1度为度为2的结点个数的结点个数n-1NO：542.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算算法描述：算法描述：HuffmanTree(intHuffmanTree(int n,NODEn,NODE node,intnode,int w) w) for (i=0;in;i+) for (i=0;in;i+) nodei.datanodei.data= =wiwi; ; nodei.lchildnodei.lchild= =nodei.rchildnodei.rc

57、hild=0;=0; for (i=0;i2 for (i=0;i2* *n-1;i+) nodei.parent=0;n-1;i+) nodei.parent=0; for (k=n;k2 for (k=n;k2* *n-1;k+)n-1;k+) SelectIJ(k,&i,&jSelectIJ(k,&i,&j););/查找最小的查找最小的i,ji,j nodek.data=nodei.data+nodej.data; nodek.data=nodei.data+nodej.data; nodek.lchildnodek.lchild=i; =i; nodek.rchildnodek.rch

58、ild=j;=j; nodei.parent=nodej.parent=k; nodei.parent=nodej.parent=k; NO：552.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算4 4）哈夫曼树的应用）哈夫曼树的应用-最佳判定算法最佳判定算法在解决某些判定问题时，利用哈夫曼树可在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。例如要编制一个将以得到最佳判定算法。例如要编制一个将学生成绩按分数段分级的程序，如果认为学生成绩按分数段分级的程序，如果认为学生各分数段的成绩分布是均匀的，则可学生各分数段的成绩分布是均匀的，则可以按上图中的

59、二叉树结构来实现，我们把以按上图中的二叉树结构来实现，我们把这种结构称为判定树。这种结构称为判定树。分数段分数段05960697079808990100比例比例0.050.050.150.150.400.400.300.300.100.10a60a70a80a90EDCBAYYYYNNNN但实际情况是学生成绩在各分数段的分布但实际情况是学生成绩在各分数段的分布是不均匀的，例如分布关系如下表所示：是不均匀的，例如分布关系如下表所示：NO：562.5 2.5 树与二叉树树与二叉树第二章第二章 常用数据结构及其运算常用数据结构及其运算假设有假设有1000010000个学生成绩输入，若按刚才的个学生成绩输入，若按刚才的判定过程进行分级，则有判定过程进行分级，则有80%80%的数据需要进的数据需要进行行3 3次或次或4 4次比较，共需进行次比较，共需进行3150031500次比较。次比较。如果以分布的比例为权构成一棵哈夫曼树，如果以分布的比例为权构成一棵哈夫曼树，如图：如图：