南京邮电大学数据结构A第5章ppt课件

1、数据构造数据构造A 第第5章章 树第第5章章 树树7、并查集和等价关系、并查集和等价关系5.1 树的根本概念树的根本概念5.1.1 树的定义层次构造的数据在现实自然界中大量存在。层次构造的数据在现实自然界中大量存在。国家、省、市、县和区。国家、省、市、县和区。书的章节、回目。书的章节、回目。上级和下级。上级和下级。整体和部分。整体和部分。祖先和后裔。祖先和后裔。5.1 树的根本概念树的根本概念5.1.1 树的定义层次构造的数据在现实自然界中大量存在。层次构造的数据在现实自然界中大量存在。图图5-1 5-1 西欧言语谱系图西欧言语谱系图原始印欧语原始印欧语古意大利语古意大利语日耳曼语日耳曼语西日

2、耳曼语西日耳曼语拉丁语拉丁语西西班班牙牙语语法法语语意意大大利利语语希腊语希腊语北日耳曼语北日耳曼语冰冰岛岛语语瑞瑞典典语语挪挪威威语语英英语语荷荷兰兰语语德德语语古希腊语古希腊语5.1 树的根本概念树的根本概念5.1.1 树的定义层次构造的数据在现实自然界中大量存在。层次构造的数据在现实自然界中大量存在。图图5-2 5-2 操作系统的目录构造操作系统的目录构造树树形形构构造造5.1 树的根本概念树的根本概念5.1.1 树的定义2、树的递归定义、树的递归定义定义定义5.2 树是包括树是包括n个结点的有限非空集合个结点的有限非空集合T，其中一个，其中一个特定的结点特定的结点r称为根，其他结点称为

3、根，其他结点T-r划分成划分成mm0个互不相交的子集个互不相交的子集T1，T2，.Tm，其中，每个子集都是，其中，每个子集都是树，被称为树根树，被称为树根r的子树。的子树。定义定义5.2是递归的，用子树来定义树，也就是说，在树的是递归的，用子树来定义树，也就是说，在树的定义中援用了树概念本身，所以，树被称为递归数据构造。定义中援用了树概念本身，所以，树被称为递归数据构造。5.1 树的根本概念树的根本概念5.1.2 根本术语结点结点(node)(node)：树中的元素。：树中的元素。根结点和它的子树根假设存在根结点和它的子树根假设存在之间构成一条边。之间构成一条边。E E、A A、F F、B B

4、、G G、C C、D D、L L、J J、M M、N N均为结点。均为结点。EAFGBCDLJMN途径途径(path)(path)：从某个结点沿树中的：从某个结点沿树中的边可到达另一个结点，那么称这两边可到达另一个结点，那么称这两个结点之间存在一条途径。个结点之间存在一条途径。E E和和N N之间存在一条途径。之间存在一条途径。5.1 树的根本概念树的根本概念5.1.2 根本术语EAFGBCDLJMN结点结点G和和C互为兄弟否？互为兄弟否？双亲双亲(parent)(parent)：假设一个结点有子：假设一个结点有子树，那么该结点称为子树根的双亲。树，那么该结点称为子树根的双亲。A A、F F、

5、B B的双亲是的双亲是E E。C C、D D的双亲是的双亲是F F。孩子孩子(child)(child)：某结点子树的根是：某结点子树的根是该结点的孩子。该结点的孩子。E E有三个孩子：有三个孩子：A A、F F、B B。D D有一个孩子：有一个孩子：J J。兄弟兄弟(sibling)(sibling)：有一样双亲的结：有一样双亲的结点互为兄弟。点互为兄弟。A A、F F、B B互为兄弟，互为兄弟，C C和和D D互为兄弟。互为兄弟。5.1 树的根本概念树的根本概念5.1.2 根本术语EAFGBCDLJMN后裔后裔(decendent)(decendent)：一个结点的：一个结点的一切子树上的

6、任何结点都是该结一切子树上的任何结点都是该结点的后裔。点的后裔。结点结点C C的后裔为：的后裔为：L L、M M、N N。祖先祖先(ancestor)(ancestor)：从根结点到：从根结点到某个结点的途径上的一切结点某个结点的途径上的一切结点都是该结点的祖先。都是该结点的祖先。结点结点L L的祖先为：的祖先为：E E、F F、C C。5.1 树的根本概念树的根本概念5.1.2 根本术语EAFGBCDLJMN结点的度结点的度(degree)(degree)：结点拥有的子树数。：结点拥有的子树数。结点结点E E的度为的度为3 3，结点，结点F F的度为的度为2 2，结点结点A A的度为的度为1

7、 1，结点，结点G G的度为的度为0 0。叶子叶子(leaf)(leaf)：度为零的结点。：度为零的结点。B B、G G、J J、M M、N N均为叶子结点。均为叶子结点。分支结点分支结点(branch)(branch)：度不为零的结点。：度不为零的结点。E E、A A、F F、C C等为分支结点。等为分支结点。树的度：树中结点的最大的度。树的度：树中结点的最大的度。该树的度为该树的度为3 3。5.1 树的根本概念树的根本概念5.1.2 根本术语结点的层次：根结点的层次为结点的层次：根结点的层次为1 1，其他结点的层次等于其，其他结点的层次等于其双亲结点的层次加双亲结点的层次加1 1。结点结点

8、E E的层次为的层次为1 1。结点结点M M的层次为的层次为5 5。树的高度：树中结点的树的高度：树中结点的最大层次。最大层次。树中结点的最大树中结点的最大层次为层次为5 5。树的高度为树的高度为5 5。12345EAFGBCDLJMN5.1 树的根本概念树的根本概念5.1.2 根本术语AG无序树：假设树中结点的各子树之间的次序是不重要的，无序树：假设树中结点的各子树之间的次序是不重要的，可以交换位置。可以交换位置。以下是同一棵无序树：以下是同一棵无序树：将左边树中一切结点的子树互换次序就是右边的树。将左边树中一切结点的子树互换次序就是右边的树。EAFGBCDLJMNEFBCDLJNM5.1

9、树的根本概念树的根本概念5.1.2 根本术语有序树：假设树中结点的各棵子树看成是从左到右有次序有序树：假设树中结点的各棵子树看成是从左到右有次序的，那么称该树为有序树。的，那么称该树为有序树。有序树的各子树从左到右为第一棵子树、第二棵，有序树的各子树从左到右为第一棵子树、第二棵，以下是二棵有序树：以下是二棵有序树：AGEAFGBCDLJMNEFBCDLJNM5.1 树的根本概念树的根本概念5.1.2 根本术语森林：是树的集合。森林：是树的集合。0 0个或多个不相交的树组成森林。个或多个不相交的树组成森林。果园或有序森林：有序树的有序集合。果园或有序森林：有序树的有序集合。假设将树中的根去掉，那

10、么得到根的子树组成的森假设将树中的根去掉，那么得到根的子树组成的森林。林。 BEAGFCDLJMNE 假设添加一个结点，将森林中各树的根作为新增结点假设添加一个结点，将森林中各树的根作为新增结点的孩子，那么森林即成为树。的孩子，那么森林即成为树。 5.2 二叉树二叉树二叉树是非常重要的树形数二叉树是非常重要的树形数据构造。据构造。很多从实践问题中笼统出来很多从实践问题中笼统出来的数据是二叉树形的；以后的数据是二叉树形的；以后我们将看到恣意树或森林可我们将看到恣意树或森林可方便地转换成二叉树，从而方便地转换成二叉树，从而为普通树和森林的存储和处为普通树和森林的存储和处置提供了有效方法。置提供了有

11、效方法。5.2 二叉树二叉树5.1.2 根本术语 方法二：改良构造，组织成树形构造。比较次数不会超方法二：改良构造，组织成树形构造。比较次数不会超越树高，提高了效率。越树高，提高了效率。二叉树运用实例二叉树运用实例 设有序表为设有序表为21，25，28，33，36，45，如今，如今要在表中查找元素要在表中查找元素33。282136253345方法一：顺序搜索。效率低，平均比较一半的元素。方法一：顺序搜索。效率低，平均比较一半的元素。21，25，28，33，36，45比较了比较了4 4次！次！比较了比较了3 3次！次！33335.2 二叉树二叉树5.2.1 二叉树的定义定义定义5.35.3 二叉

12、树二叉树(binary tree)(binary tree)是结点的有限集合，是结点的有限集合，该集合或者为空集，或者是由一个根和两个互不该集合或者为空集，或者是由一个根和两个互不相交的、称为该根的左子树和右子树的二叉树组相交的、称为该根的左子树和右子树的二叉树组成。成。 上述定义阐明二叉树可以为空集，因此，二上述定义阐明二叉树可以为空集，因此，二叉树有叉树有5 5种根本形状。种根本形状。(a) (b) (c) (d) (e)(a) (b) (c) (d) (e)图图5-4 5-4 二叉树的五种根本形状二叉树的五种根本形状5.2 二叉树二叉树5.2.1 二叉树的定义树与二叉树的区别：树与二叉树

13、的区别： 树不能是空树，即至少有一个根结点。而二树不能是空树，即至少有一个根结点。而二叉树可以是空树。叉树可以是空树。 普通树的子树之间是无序的。而二叉树中结普通树的子树之间是无序的。而二叉树中结点的子树要区分左、右子树，即使只需一棵子点的子树要区分左、右子树，即使只需一棵子树。树。 树中每个节点可有树中每个节点可有0 0棵或假设干子树。而二棵或假设干子树。而二叉树的每个节点最多只能有叉树的每个节点最多只能有2 2棵子树。棵子树。EFEF5.2 二叉树二叉树5.2.2 二叉树的性质性质性质5.1 5.1 二叉树的第二叉树的第i(i1)i(i1)层上至多有层上至多有2i-1 2i-1 个结点。个

14、结点。 可用归纳法证明之。当可用归纳法证明之。当i=1i=1时，二叉树至多只需一个结时，二叉树至多只需一个结点，结论成立。点，结论成立。 设当设当i=ki=k时结论成立，即二叉树上至多有时结论成立，即二叉树上至多有2k-1 2k-1 个结点个结点 当当i=k+1i=k+1时，时， 每个结点最多只需两个孩子，每个结点最多只需两个孩子， 第第k+1k+1层上至多有层上至多有2 2* *2k1 =2k2k1 =2k个结点，性质成立。个结点，性质成立。5.2 二叉树二叉树5.2.2 二叉树的性质性质性质5.2 5.2 高度为高度为h h的二叉树上至多有的二叉树上至多有2h12h1个结点。个结点。当当h

15、=0h=0时，二叉树为空二叉树。时，二叉树为空二叉树。当当h0h0时，利用性质时，利用性质1 1，高度为，高度为h h的二叉树中结点的总数最多为：的二叉树中结点的总数最多为：1012112(222.2)21hihhi12311.1nnaaaaaa补充：等比数列的求和公式是11 (1)2ii i性质 二叉树的第层上至多有个结点。5.2 二叉树二叉树5.2.2 二叉树的性质5.2 二叉树二叉树5.2.2 二叉树的性质性质性质5.3 5.3 包含包含n n个元素的二叉树的高度至少为个元素的二叉树的高度至少为 log2 log2 (n+1)(n+1) 根据性质根据性质2 2，高度为，高度为h h的二叉

16、树最多有的二叉树最多有2h 12h 1个结点性质个结点性质2 2，因此，因此n n2h 1, 2h 1, 那么有那么有h h log2(n+1) log2(n+1)。由于由于h h是整数，所以是整数，所以h h log2 (n+1)log2 (n+1)。5.2 二叉树二叉树5.2.2 二叉树的性质性质性质5.4 5.4 恣意一棵二叉树中，假设叶结点的个数为恣意一棵二叉树中，假设叶结点的个数为n0n0，度，度为为2 2的结点的个数为的结点的个数为n2n2，那么必有，那么必有n0=n2+1n0=n2+1。设二叉树的度为设二叉树的度为1 1的结点数为的结点数为n1n1，树中结点总数为，树中结点总数为

17、n n，那么那么n=n0+n1+n2 n=n0+n1+n2 二叉树中只需度为二叉树中只需度为0 0、1 1、2 2三种类型的结点三种类型的结点设分支数为设分支数为B B，n n个结点的二叉树，除了根结点外，每个结点个结点的二叉树，除了根结点外，每个结点都有一个分支进入，那么都有一个分支进入，那么B=n-1B=n-1；分支是由度为；分支是由度为1 1或者度为或者度为2 2的射出的，又有的射出的，又有B=2n2+n1B=2n2+n1；那么有：那么有：n-1=2n2+n1 n-1=2n2+n1 n=2n2+n1+1n=2n2+n1+1由由 可得到：可得到：n0+n1+n2=2n2+n1+1 n0+n

18、1+n2=2n2+n1+1 n0+n2=2n2 +1 n0+n2=2n2 +1即即n2=n0-1n2=n0-1。5.2 二叉树二叉树5.2.2 二叉树的性质定义定义5.4 5.4 高度为高度为h h的二叉树恰好有的二叉树恰好有2h 12h 1个结点时称为满个结点时称为满二叉树。二叉树。0123456789101112 1314(a)满二叉树满二叉树0123456789(b)完全二叉树完全二叉树图图5.6 几种特殊的二叉树几种特殊的二叉树9定义定义5.5 一棵二叉树中，只需最下面两层结点的度可以小一棵二叉树中，只需最下面两层结点的度可以小于于2，并且最下一层的叶结点集中在靠左的假设干位置上。，并

19、且最下一层的叶结点集中在靠左的假设干位置上。这样的二叉树称为完全二叉树。这样的二叉树称为完全二叉树。5.2 二叉树二叉树5.2.2 二叉树的性质定义定义5.6 5.6 扩展二叉树也称扩展二叉树也称2-2-树，其中除叶子结点外，其树，其中除叶子结点外，其他结点都必需有两个孩子。他结点都必需有两个孩子。5323301112131735895.2 二叉树二叉树5.2.2 二叉树的性质：完全二叉树的性质性质性质5.5 5.5 具有具有n n个结点的完全二叉树的高度为个结点的完全二叉树的高度为log2 (n+1)log2 (n+1)。证明：根据性质证明：根据性质2 2高度为高度为h-1h-1的完全二叉树

20、结点个数最多为的完全二叉树结点个数最多为2h-1-12h-1-1高度为高度为h h的完全二叉树结点个数最多为的完全二叉树结点个数最多为2h-12h-1高度为高度为h h的完全二叉树结点个数取值范围的完全二叉树结点个数取值范围2h-1 , 2h)2h-1 , 2h)结论：结论： n n个结点的二叉树中完全二叉树最矮，高度为个结点的二叉树中完全二叉树最矮，高度为log2 (n+1)log2 (n+1)。 n n个结点的完全二叉树和二叉断定树的高度是一样的个结点的完全二叉树和二叉断定树的高度是一样的2log1n 2h-1n2h-1n2h2hlog2nlog2nh log2n+1h log2n+1hh

21、是整数是整数 h= h=2log1n 性质性质2 2 高度为高度为h h的二叉树上至多有的二叉树上至多有2h 12h 1个结点。个结点。2h-1 - 12h-1 - 1 n 2h 1 n 2h 1l o g 2 ( n + 1 ) hl o g 2 ( n + 1 ) h log2(n+1)+1log2(n+1)+1h = h = log2 (n+1)log2 (n+1)5.2 二叉树二叉树5.2.2 二叉树的性质：完全二叉树的性质性质性质5.6 5.6 假定对一棵有假定对一棵有n n个结点的完全二叉树中的结点，按从上个结点的完全二叉树中的结点，按从上到下、从左到右的顺序，从到下、从左到右的顺

22、序，从0 0到到n-1n-1编号见图编号见图5.6(c)5.6(c)，设树中，设树中一个结点的序号为一个结点的序号为i i，0 0i in n ，那么有以下关系成立：，那么有以下关系成立：1 1当当i=0i=0时，该结点为二叉树的根。时，该结点为二叉树的根。2 2假设假设i0i0，那么该结点的双亲的序号为，那么该结点的双亲的序号为(i-1)/2(i-1)/23 3假设假设2i+12i+1n n，那么该结点的左孩子的序号为，那么该结点的左孩子的序号为2i+12i+1，否那么，否那么该结点无左孩子。该结点无左孩子。4 4假设假设2i+22i+2n n，那么该结点的右孩子的序号为，那么该结点的右孩子

23、的序号为2i+22i+2，否那么，否那么该结点无右孩子。该结点无右孩子。(a)(a)满二叉树满二叉树0123456789 10 11 12 13 140123456789(b)(b)完全二叉树完全二叉树5.2 二叉树二叉树5.2.3 二叉树ADTADT BinaryTree Data: 二叉树是结点的有限集合，该集合或者为空集，或者是由一个根二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两个互不相交的称为该根的左子树和右子树的二叉树组成。和两个互不相交的称为该根的左子树和右子树的二叉树组成。 Operations: Create()： 创建一棵空二叉树。创建一棵空二叉树。 Dest

24、roy(): 撤销一棵二叉树。撤销一棵二叉树。 IsEmpty()：假设二叉树空，那么前往：假设二叉树空，那么前往true，否那么前往，否那么前往false。 Clear(): 移去一切结点，成为空二叉树。移去一切结点，成为空二叉树。 Root(x)：取：取x为根结点；假设操作胜利，那么前往为根结点；假设操作胜利，那么前往true，否那么前往，否那么前往false MakeTree(x,left，right)：创建一棵二叉树，：创建一棵二叉树，x为根结点，为根结点，left为为 左子树，左子树，right为右子树。为右子树。 BreakTree(x ,left, right)：拆分二叉树为三部

25、分，：拆分二叉树为三部分，x为根的值，为根的值， left和和right分别为原树的左右子树分别为原树的左右子树 PreOrder： 运用函数运用函数Visit访问结点，先序遍历二叉树。访问结点，先序遍历二叉树。 InOrder： 运用函数运用函数Visit访问结点，中序遍历二叉树。访问结点，中序遍历二叉树。 PostOrder：运用函数：运用函数Visit访问结点，后序遍历二叉树。访问结点，后序遍历二叉树。 5.2 二叉树二叉树5.2.4 二叉树的存储表示1. 1. 完全二叉树的顺序表示完全二叉树的顺序表示 完全二叉树中的结点可以按层次顺序存储在一片延完全二叉树中的结点可以按层次顺序存储在一

26、片延续的存储单元中。根结点保管在编号为续的存储单元中。根结点保管在编号为0 0的位置上。的位置上。留意：普通的二叉树不适宜用这种存储构造。留意：普通的二叉树不适宜用这种存储构造。0 01 12 23 34 45 56 67 78 89 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9图图6.5 6.5 图图6.4(b)6.4(b)完全二叉树的顺序表示完全二叉树的顺序表示0123456789图图6.4(b) 6.4(b) 完全二叉树完全二叉树5.2 二叉树二叉树5.2.4 二叉树的存储表示lChild element rChildlChild element rCh

27、ild一棵有一棵有n n个结点的二叉树中，每个结点有个结点的二叉树中，每个结点有2 2个指针域。个指针域。指针域有指针域有2n2n个。除了根结点外，其它结点均有一个指向它个。除了根结点外，其它结点均有一个指向它的指针，此项开支用掉的指针，此项开支用掉n-1n-1个指针域。个指针域。空指针域的数目为空指针域的数目为2n-(n-1)=n+12n-(n-1)=n+1。2. 2. 二叉树的链接表示二叉树的链接表示ABCDEFA AB B C C D D E E F F (a)(a)二叉树二叉树(b)(b)二叉树的链接表示二叉树的链接表示图图6-6 6-6 二叉树的链接表示二叉树的链接表示5.2 二叉树

28、二叉树5.2.4 二叉树的存储表示二叉树的二叉链表构造有利于从双亲到孩子方向的访问，二叉树的二叉链表构造有利于从双亲到孩子方向的访问，但从孩子无法反向访问其父节点。但从孩子无法反向访问其父节点。假设在二叉链表结点中添加一个假设在二叉链表结点中添加一个parent域，令它指向该结域，令它指向该结点的双亲结点，就可以实现从孩子到双亲，以及从双亲到点的双亲结点，就可以实现从孩子到双亲，以及从双亲到孩子的双向链接构造。孩子的双向链接构造。A AB B C C D D E E F F 5.2 二叉树二叉树5.2.5 二叉树类templatestruct BTNode BTNode() lChild =

29、rChild = NULL; BTNode(const T& x) element =x; lChild = rChild = NULL; BTNode(const T& x, BTNode* l, BTNode* r) element = x; lChild = l; rChild = r; T element; BTNode *lChild, *rChild;程序程序5.1 二叉树结点类二叉树结点类5.2 二叉树二叉树5.2.5 二叉树类templateclass BinaryTree public: BinaryTree()root = NULL; BinaryTree()Clear()

30、; bool IsEmpty()const; void Clear(); bool Root(T& x)const; void MakeTree(const T& e,BinaryTree& left,BinaryTree& right); void BreakTree(T& e,BinaryTree& left,BinaryTree& right); void PreOrder(void(*Visit)(T& x); void InOrder(void(*Visit)(T& x); void PostOrder(void(*Visit)(T& x); protected: BTNode* r

31、oot; private: int Size(BTNode* t); void Clear(BTNode* t); void PreOrder(void(*Visit)(T& x),BTNode* t); void InOrder(void(*Visit)(T& x), BTNode* t); void PostOrder(void(*Visit)(T& x), BTNode* t);程序程序5.2 二叉树类二叉树类5.2 二叉树二叉树5.2.6 实现二叉树根本运算本小节中，我们主要实现本小节中，我们主要实现MakeTree、BreakTree和和Root运运算，而将二叉树遍历算法留待下一小节

32、专门讨论。算，而将二叉树遍历算法留待下一小节专门讨论。Clear()函数释放二叉链表中的一切结点，它需求经过遍函数释放二叉链表中的一切结点，它需求经过遍历二叉树来实现。历二叉树来实现。5.2 二叉树二叉树5.2.6 实现二叉树根本运算程序程序5.3 部分二叉树运算部分二叉树运算templatebool BinaryTree:Root(T& x)const if(root) x = root-element; return true; else return false;ABCDEF5.2 二叉树二叉树5.2.6 实现二叉树根本运算程序程序5.3 部分二叉树运算部分二叉树运算templatevo

33、id BinaryTree:MakeTree(const T& x, BinaryTree& left,BinaryTree& right) if(root|&left=&right) return; root = new BTNode(x, left.root, right.root); left.root = right.root = NULL; DCEFBTNode(const T& x, BTNode* l,BTNode* r) element = x; lChild = l; rChild = r; A Aleft.rootright.root=NULL=NULL5.2 二叉树二叉树

34、5.2.6 实现二叉树根本运算程序程序5.3 部分二叉树运算部分二叉树运算 if(root|&left=&right) return; root = new BTNode(x, left.root, right.root); left.root = right.root = NULL;D C E F t3t2(1) t1.root != NULL;(2) &t2 = &t3t1.MakeTree(A, t2, t3);N P t1(1) t1的结点全部丧失的结点全部丧失?(2) t1左右子树的结点是同左右子树的结点是同一空间一空间?5.2 二叉树二叉树5.2.6 实现二叉树根本运算程序程序5.

35、3 部分二叉树运算部分二叉树运算templatetemplatevoid BinaryTree:BreakTree(T& x, void BinaryTree:BreakTree(T& x, BinaryTree&left,BinaryTree&right) BinaryTree&left,BinaryTree&right) if(!root|&left=&right|left.root|right.root) if(!root|&left=&right|left.root|right.root) return; return; x = root-element; x = root-eleme

36、nt; left.root = root-lChild; left.root = root-lChild; right.root = root-rChild; right.root = root-rChild; delete root; delete root; root = NULL; root = NULL; D DC CE EF FA Aleft.rootleft.rootright.rootright.rootroot=root=root5.2 二叉树二叉树5.2.6 实现二叉树根本运算int main(void) BinaryTreea, b, x, y, z; y.MakeTree

37、(E, a, b); z.MakeTree(F, a, b); x.MakeTree(C, y, z); y.MakeTree(D, a, b); z.MakeTree(B, y, x); z.BreakTree(e, y, x); return 0;程序程序5.4 main5.4 main函数函数一个测试程序一个测试程序a b x y zEyCxFzDyBz5.3 二叉树的遍历二叉树的遍历5.1.2 根本术语遍历遍历traversetraverse一个有限一个有限结点的集合，意味着对该集结点的集合，意味着对该集合中的每个结点访问且仅访合中的每个结点访问且仅访问一次。问一次。A AB BD D

38、C CE EF F二叉树遍历算法二叉树遍历算法: : (I) (I) 先左后右：先左后右：VLRVLR，LVRLVR，LRVLRV(II)(II)先右后左：先右后左：VRLVRL，RVLRVL，RLV-RLV-逆逆5.3 二叉树的遍历二叉树的遍历5.3.1 二叉树遍历算法 先序遍历先序遍历VLRVLR假设二叉树为空，那么空操作；假设二叉树为空，那么空操作；否那么否那么 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。A AB BD DC CE EF F先序遍历序列：先序遍历序列： A B D C E F A B D C E F 先序遍历序列：先序遍历

39、序列： A B D G H E C F A B D G H E C F ttttttt= t= t=t=ttt=t=t=A AB BC CD DE EF FG GH H5.3 二叉树的遍历二叉树的遍历5.3.1 二叉树遍历算法(2) (2) 中序遍历中序遍历LVRLVR假设二叉树为空，那么空操作；假设二叉树为空，那么空操作；否那么否那么 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 中序遍历序列：中序遍历序列：B D A E C F B D A E C F A AB BD DC CE EF F中序遍历中序遍历A AB BC CD DE EF FG

40、 GH HI IJ JK K5.3 二叉树的遍历二叉树的遍历5.3.1 二叉树遍历算法(3)(3)后序遍历后序遍历 LRVLRV 假设二叉树为空，那么空操作假设二叉树为空，那么空操作； 否那么否那么 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。后序遍历序列：后序遍历序列：D B E F C A D B E F C A A AB BD DC CE EF F后序遍历后序遍历A AB BC CD DE EF FG GH HI IJ JK K层次遍历层次遍历A AB BC CD DE EF FG GH HI IJ JK K5.3 二叉树的遍历二叉树的遍历

41、5.3.2 二叉树遍历的递归算法 对于遍历运算，设计了一个面向用户的公有成员函数对于遍历运算，设计了一个面向用户的公有成员函数和一个详细实现遍历操作的递归私有成员函数，两者共同和一个详细实现遍历操作的递归私有成员函数，两者共同完成遍历运算的功能。完成遍历运算的功能。 公有成员函数：非递归函数，作为与用户的接口。它调用公有成员函数：非递归函数，作为与用户的接口。它调用私有的递归函数。私有的递归函数。 私有成员函数：递归函数，详细实现遍历操作。被公有成私有成员函数：递归函数，详细实现遍历操作。被公有成员函数调用。员函数调用。5.3 二叉树的遍历二叉树的遍历5.3.2 二叉树遍历的递归算法程序程序5

42、.5 访问元素函数访问元素函数templatevoid Visit(T& x) cout x t;程序程序5.6 先序遍历先序遍历templatevoid BinaryTree:PreOrder(void(*Visit)(T& x) PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void(*Visit)(T& x), BTNode* t) if(t) Visit(t-element); PreOrder(Visit, t-lChild); PreOrder(Visit, t-rChild); 5.3 二叉树的遍历二叉树的遍历5.3.

43、2 二叉树遍历的递归算法补充：中序遍历补充：中序遍历templatevoid BinaryTree:InOrder(void(*Visit)(T& x) InOrder(Visit,root);templatevoid BinaryTree:InOrder(void(*Visit)(T& x), BTNode* t) if(t) InOrder(Visit, t-lChild); Visit(t-element); InOrder(Visit, t-rChild); 5.3 二叉树的遍历二叉树的遍历5.3.2 二叉树遍历的递归算法补充：后序遍历补充：后序遍历templatevoid Binar

44、yTree:PostOrder(void(*Visit)(T& x) PostOrder(Visit,root);templatevoid BinaryTree:PostOrder(void(*Visit)(T& x), BTNode* t) if(t) PostOrder(Visit, t-lChild); PostOrder(Visit, t-rChild); Visit(t-element); 5.3 二叉树的遍历二叉树的遍历 显然，二叉树遍历算法根本操作是访问结点，不论按显然，二叉树遍历算法根本操作是访问结点，不论按何种次序遍历，对含有何种次序遍历，对含有n n个结点的二叉树，其时间复

45、杂度均个结点的二叉树，其时间复杂度均为为O(n)O(n)。5.3 二叉树的遍历二叉树的遍历关于三种遍历算法：关于三种遍历算法：1.1.给定一棵二叉树，能写出它的三种遍历序列。给定一棵二叉树，能写出它的三种遍历序列。2.2.给出二叉树的先序遍历序列和中序遍历序列可以独一确给出二叉树的先序遍历序列和中序遍历序列可以独一确 定一棵二叉树。定一棵二叉树。3.3.给出二叉树的后序遍历序列和中序遍历序列可以独一确给出二叉树的后序遍历序列和中序遍历序列可以独一确 定一棵二叉树。定一棵二叉树。4.4.当当n1n1时，给出二叉树的先序遍历序列和后序遍历序列不时，给出二叉树的先序遍历序列和后序遍历序列不 可以独一

46、确定一棵二叉树。可以独一确定一棵二叉树。例如：先序序列：例如：先序序列：ABAB，后序序列：，后序序列：BABAA AB BA AB B5.3 二叉树的遍历二叉树的遍历例例 知结点的先序序列和中序序列分别为：知结点的先序序列和中序序列分别为：先序序列先序序列 A B C D E F G中序序列中序序列 C B E D A F G那么可按上述分解求得整棵二叉树那么可按上述分解求得整棵二叉树,其构造过程其构造过程:(1) 由先序序列可知二叉树的根为由先序序列可知二叉树的根为A，A的左子树的的左子树的中序序列为中序序列为CBED，右子树的中序序列为，右子树的中序序列为FG。(2) 此外，此外，A的左

47、子树的先序序列必为的左子树的先序序列必为BCDE，右子，右子树的前序序列为树的前序序列为FG。(3) 类似地，可由左子树的先序序列和中序序列构类似地，可由左子树的先序序列和中序序列构造造A的左子树，由右子树的先序序列和中序序列构的左子树，由右子树的先序序列和中序序列构造造A的右子树。的右子树。5.3 二叉树的遍历二叉树的遍历5.3.3 二叉树遍历的运用实例1.1.计算二叉树的结点数计算二叉树的结点数 程序程序5.7 5.7 求二叉树的结点数求二叉树的结点数templatetemplateint BinaryTree:Size() int BinaryTree:Size() return Siz

48、e(root); return Size(root); templatetemplateint BinaryTree:Size(BTNodeint BinaryTree:Size(BTNode* * t) t) if(!t) return 0; if(!t) return 0; return Size(t-lChild) + Size(t- return Size(t-lChild) + Size(t-rChild) + 1;rChild) + 1; 利用二叉树遍历思想可以处理许多二叉树的运用问题。利用二叉树遍历思想可以处理许多二叉树的运用问题。A AB BD DC CE EF F5.3 二叉

49、树的遍历二叉树的遍历5.3.3 二叉树遍历的运用实例2.2.二叉树复制二叉树复制程序程序5.8 5.8 二叉树复制二叉树复制templatetemplateBTNodeBTNode* * BinaryTree:Copy(BTNode BinaryTree:Copy(BTNode* * t) t) if(!root) return NULL; if(!root) return NULL; BTNode BTNode* * q = new BTNode(t-element); q = new BTNode(t-element); q-lChild = Copy(t-lChild); q-lChil

50、d = Copy(t-lChild); q-rChild = Copy(t-rChild); q-rChild = Copy(t-rChild); return q; return q; 利用二叉树遍历思想可以处理许多二叉树的运用问题。利用二叉树遍历思想可以处理许多二叉树的运用问题。A AB BD DC CE EF Ft tA AB BD DC CE EF Fq q=5.3 二叉树的遍历二叉树的遍历5.3.3 二叉树遍历的运用实例3.3.补充：删除二叉树补充：删除二叉树templatetemplatevoid BinaryTree:Clear(BTNodevoid BinaryTree:Cle

51、ar(BTNode* * t) t) if(t) if(t) Clear(t-lChild); Clear(t-lChild); Clear(t-rChild); Clear(t-rChild); cout deleteelement.endl; cout deleteelement.=C CK K=再看一例再看一例5.5 树和森林树和森林5.5.1 森林与二叉树的转换1. 1. 树树(Tree)(Tree)转换为二叉树转换为二叉树(BTree)(BTree)算法算法留意：留意： 左 孩 子 右 兄 弟 。左 孩 子 右 兄 弟 。 ( ( 树树 二 叉 树二 叉 树 ) ) 二 叉 树 中

52、有 两 个 结 点二 叉 树 中 有 两 个 结 点 X X 和和 Y Y ， 且， 且 X X 是是 Y Y 的 双 亲的 双 亲 树的根结点没有兄弟，所以树对应的二叉树根结点没树的根结点没有兄弟，所以树对应的二叉树根结点没有右子树有右子树二叉树中二叉树中树中树中Y Y是是X X左左孩子孩子Y Y是是X X孩子孩子Y Y是是X X右右孩子孩子Y Y是是X X兄弟兄弟5.5 树和森林树和森林5.5.1 森林与二叉树的转换2.2.森林森林(Forest)(Forest)转换成二叉树转换成二叉树(BTree)(BTree) 可以将任何森林独一地表示成一棵二叉树。可以将任何森林独一地表示成一棵二叉树

53、。方法如下：方法如下：(1)(1)假设假设F F为空，那么为空，那么B B为空二叉树为空二叉树(2)(2)假设假设F F非空，那么非空，那么B B的根是的根是F F中第一棵子树中第一棵子树T1T1的根的根R1R1，B B的左子树是的左子树是T1T1的子树森林的子树森林T11T11，T12T12，T1mT1m，B B的右的右子树是森林子树是森林T2T2，TnTn所对应的二叉树所对应的二叉树 最后所构成的二叉树就是森林所对应的二叉树。最后所构成的二叉树就是森林所对应的二叉树。5.5 树和森林树和森林5.5.1 森林与二叉树的转换2.2.森林森林(Forest)(Forest)转换成二叉树转换成二叉

54、树(BTree)(BTree)A AB BC CK KD DE EF FG GH HJ JA AB BC CK KD DE EH HF FJ JG GA AD DE EH HF FJ JG GB BC CK K5.5 树和森林树和森林5.5.1 森林与二叉树的转换3.3.二叉树转换成森林二叉树转换成森林(BF)(BF)A AB BC CK KD DE EF FG GH HJ JA AD DE EH HF FJ JG GB BC CK K1.1. 连线连线2.2. 去线去线3.3. 整形整形5.5 树和森林树和森林5.5.1 森林与二叉树的转换3.3.二叉树转换成森林二叉树转换成森林(BF)(B

55、F)一棵二叉树一棵二叉树B B转换成的森林中有多少棵树？转换成的森林中有多少棵树？ 一 棵 二 叉 树一 棵 二 叉 树转化成的森林中转化成的森林中所具有的树的数所具有的树的数目，等于二叉树目，等于二叉树从根结点开场沿从根结点开场沿右链到第一个没右链到第一个没有右孩子的结点有右孩子的结点所经过的结点数所经过的结点数目。目。A AB BE EC CD DF FG GH HI IJ J经过经过3个结点，个结点，故森林中故森林中3棵树棵树5.5 树和森林树和森林5.5.1 森林与二叉树的转换3.3.二叉树转换成森林二叉树转换成森林(BF)(BF)A AB BC CD DE EF FG GH HI I

56、J JA AB BC CD DE EF FG GH HI IJ J5.5 树和森林树和森林5.5.2 树和森林的存储表示1. 1. 多重链表表示法多重链表表示法其中其中m m是树的度。每个结点的指针域个数均为是树的度。每个结点的指针域个数均为m m，故又，故又称为等长的多重链表。称为等长的多重链表。 优点：处置简单。优点：处置简单。缺陷：空指针域多，有浪费。缺陷：空指针域多，有浪费。 设树中有设树中有n n个结点，总共有个结点，总共有n n* *m m个指针域，其中，个指针域，其中，只需只需n-1n-1个非空指针域，故空指针域个数为：个非空指针域，故空指针域个数为： n n* *m-(n-1)

57、=n(m-1)+1m-(n-1)=n(m-1)+1 element child1 child2 childm5.5 树和森林树和森林5.5.2 树和森林的存储表示2. 2. 孩子兄弟表示法孩子兄弟表示法 孩子兄弟孩子兄弟( (左子左子/ /右兄弟右兄弟) )表示法本质上就是树所对应的表示法本质上就是树所对应的二叉树的二叉链表表示法。其每个结点为：二叉树的二叉链表表示法。其每个结点为：leftChild element rightSiblingD DE EF FG GH HJ JD DE EF FG GH HJ J J J G G F F H H E E D D 5.5 树和森林树和森林5.5.

58、2 树和森林的存储表示3. 3. 双亲表示法双亲表示法 每个结点有两个域：每个结点有两个域：elementelement和和parentparent。parentparent域为域为指向该结点的双亲结点的下标。指向该结点的双亲结点的下标。 可以对树中结点按自上而下、自左向右可以对树中结点按自上而下、自左向右( (按层次按层次) )的次的次序顺序存储起来。序顺序存储起来。思索：如何查找结点的双亲和孩子？思索：如何查找结点的双亲和孩子？012345DEFGHJ-1 00012element parent顺序存储的顺序存储的双亲表示法双亲表示法D DE EF FG GH HJ J双亲表示法双亲表示法

59、5.5 树和森林树和森林5.5.2 树和森林的存储表示4. 4. 三重链表表示法三重链表表示法优点：可以很方便地得到节点的双亲和孩子信息。优点：可以很方便地得到节点的双亲和孩子信息。leftChild element rightSibling parentD DE EF FG GH HJ J J J G G F F H H D D E E5.5 树和森林树和森林5.5.2 树和森林的存储表示5. 5. 带右链的先序表示法带右链的先序表示法 数据元素有三个数据项，数据元素有三个数据项，element, lTag, siblingelement, lTag, sibling。 sibling si

60、bling 指向结点的兄弟指向结点的兄弟 lTag lTag为为0 0表示有孩子，孩子存于相邻单元表示有孩子，孩子存于相邻单元 lTag lTag为为1 1表示无孩子表示无孩子 数据元素按对应二叉树的先序遍历的顺序存储结点。数据元素按对应二叉树的先序遍历的顺序存储结点。5.5 树和森林树和森林5.5.2 树和森林的存储表示5. 5. 带右链的先序表示法带右链的先序表示法5.5 树和森林树和森林5.5.3 树和森林的遍历 1按深度方向遍历 对森林的深度遍历与二叉树类似，根据树的递归定义，可以有两种遍历次序：先序遍历和中序遍历。森林森林(F)对应对应二叉树二叉树(B)先序遍历先序遍历等价于等价于先