数据结构-王红梅-第5章树和二叉树ppt课件

1、数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的逻辑构造树的逻辑构造树的存储构造树的存储构造二叉树的逻辑构造二叉树的逻辑构造二叉树的存储构造及实现二叉树的存储构造及实现二叉树遍历的非递归算法二叉树遍历的非递归算法 树、森林与二叉树的转换树、森林与二叉树的转换哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码第第 5 章章 树和二叉树树和二叉树本章的主要内容是本章的主要内容是数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的定义树的定义树：树：n nn0n0个结点的有限集合。当个结点的有限集合。当n n0 0时，称为时，称为空树；恣意一棵非空树满足以下条件

2、：空树；恣意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点；有且仅有一个特定的称为根的结点； 当当n n1 1时，除根结点之外的其他结点被分成时，除根结点之外的其他结点被分成m mm0m0个互不相交的有限集合个互不相交的有限集合T1,T2, ,TmT1,T2, ,Tm，其中，其中每个集合又是一棵树，并称为这个根结点的子树。每个集合又是一棵树，并称为这个根结点的子树。5.1 树的逻辑构造树的逻辑构造树的定义是采用递归方法树的定义是采用递归方法数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社(a) 一棵树构造一棵树构造 (b)一个非树构造一个非树构造 (c)一个非树

3、构造一个非树构造 5.1 树的逻辑构造树的逻辑构造树的定义树的定义ACBGFEDHIACBGFDACBGFDE数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的运用举例树的运用举例文件构造文件构造5.1 树的逻辑构造树的逻辑构造My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的根本术语树的根本术语p 结点的度：结点所拥有的子树的个数。结点的度：结点所拥有的子树的个数。p 树的度：树中各结点度的最大值。树的度：树中各结点度的最大值。5.1 树的逻

4、辑构造树的逻辑构造CGBDEFKLHMIJA数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.1 树的逻辑构造树的逻辑构造p 叶子结点：度为叶子结点：度为0 0的结点，也称为终端结点。的结点，也称为终端结点。p 分支结点：度不为分支结点：度不为0 0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFKLHMIJA树的根本术语树的根本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社p 孩子、双亲：树中某结点子树的根结点称为这个结点的孩孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；子结点，

5、这个结点称为它孩子结点的双亲结点；p 兄弟：具有同一个双亲的孩子结点互称为兄弟。兄弟：具有同一个双亲的孩子结点互称为兄弟。 5.1 树的逻辑构造树的逻辑构造CGBDEFKLHMIJA树的根本术语树的根本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社p 途径：假设树的结点序列途径：假设树的结点序列n1, n2, , nk有如下关系：结点有如下关系：结点ni是是ni+1的双亲的双亲1=ik，那么把，那么把n1, n2, , nk称为一条由称为一条由n1至至nk的途径；的途径；p 途径上经过的边的个数称为途径长度。途径上经过的边的个数称为途径长度。 CGBDEFKLHMI

6、JA5.1 树的逻辑构造树的逻辑构造树的根本术语树的根本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社祖先、子孙：在树中，假设有一条途径从结点祖先、子孙：在树中，假设有一条途径从结点x x到结点到结点y y，那，那么么x x称为称为y y的祖先，而的祖先，而y y称为称为x x的子孙。的子孙。5.1 树的逻辑构造树的逻辑构造CGBDEFKLHMIJA树的根本术语树的根本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社p 结点所在层数：根结点的层数为结点所在层数：根结点的层数为1 1；对其他任何结点，假设某；对其他任何结点，假设某结点在第结点

7、在第k k层，那么其孩子结点在第层，那么其孩子结点在第k+1k+1层。层。p 树的深度：树中一切结点的最大层数，也称高度。树的深度：树中一切结点的最大层数，也称高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC5.1 树的逻辑构造树的逻辑构造树的根本术语树的根本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社CBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从次序依次给他们编以从1 1开场的延续自然数。开场的延续自然数。5.1 树的

8、逻辑构造树的逻辑构造树的根本术语树的根本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社有序树、无序树：假设一棵树中结点的各子树从左到右是有有序树、无序树：假设一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。次序的，称这棵树为有序树；反之，称为无序树。数据构造中讨论的普通都是有序树数据构造中讨论的普通都是有序树 5.1 树的逻辑构造树的逻辑构造树的根本术语树的根本术语ACBGFEDACBGFED数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社CBDEFKLHJ森林：森林：m (m0)棵互不相交的树的集合。任何一棵树删去

9、棵互不相交的树的集合。任何一棵树删去根结点就变成了森林。根结点就变成了森林。 5.1 树的逻辑构造树的逻辑构造树的根本术语树的根本术语A数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树构造和线性构造的比较树构造和线性构造的比较第一个数据元素第一个数据元素根结点只需一个根结点只需一个无前驱无前驱无双亲无双亲最后一个数据元素最后一个数据元素叶子结点叶子结点(可以有多个可以有多个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子5.1 树的逻辑构造树的逻辑构造数据结构（数据结构（C+版）第版）

10、第2版版清华大学出版社清华大学出版社树的笼统数据类型定义树的笼统数据类型定义ADT TreeData 树是由一个根结点和假设干棵子树构成，树是由一个根结点和假设干棵子树构成， 树中结点具有一样数据类型及层次关系树中结点具有一样数据类型及层次关系Operation5.1 树的逻辑构造树的逻辑构造树的运用很广泛，在不同的实践运用中，树的根本操作不树的运用很广泛，在不同的实践运用中，树的根本操作不尽一样。下面给出一个树的笼统数据类型定义的例子，简尽一样。下面给出一个树的笼统数据类型定义的例子，简单起见，根本操作只包含树的遍历，针对详细运用，需求单起见，根本操作只包含树的遍历，针对详细运用，需求重新定

11、义其根本操作。重新定义其根本操作。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社InitTree 前置条件：树不存在前置条件：树不存在 输入：无输入：无 功能：初始化一棵树功能：初始化一棵树 输出：无输出：无 后置条件：构造一个空树后置条件：构造一个空树DestroyTree 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：销毁一棵树功能：销毁一棵树 输出：无输出：无 后置条件：释放该树占用的存储空间后置条件：释放该树占用的存储空间 树的笼统数据类型定义树的笼统数据类型定义5.1 树的逻辑构造树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出

12、版社清华大学出版社 PreOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：前序遍历树功能：前序遍历树 输出：树的前序遍历序列输出：树的前序遍历序列 后置条件：树坚持不变后置条件：树坚持不变 PostOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：后序遍历树功能：后序遍历树 输出：树的后序遍历序列输出：树的后序遍历序列 后置条件：树坚持不变后置条件：树坚持不变endADT树的笼统数据类型定义树的笼统数据类型定义5.1 树的逻辑构造树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的遍历操作树的遍历操作 树的遍历

13、：从根结点出发，按照某种次序访问树中一切结点，树的遍历：从根结点出发，按照某种次序访问树中一切结点，使得每个结点被访问一次且仅被访问一次。使得每个结点被访问一次且仅被访问一次。 如何了解访问如何了解访问? ?笼统操作，可以是对结点进展的各种处置，这里简化为输出笼统操作，可以是对结点进展的各种处置，这里简化为输出结点的数据。结点的数据。如何了解次序如何了解次序? ?树通常有前序根遍历、后序根遍历和层序次树通常有前序根遍历、后序根遍历和层序次遍历三种方式。遍历三种方式。5.1 树的逻辑构造树的逻辑构造树构造非线性构造树构造非线性构造线性构造。线性构造。遍历的本质遍历的本质? ?数据结构（数据结构（

14、C+版）第版）第2版版清华大学出版社清华大学出版社前序遍历前序遍历 树的前序遍历操作定义为：树的前序遍历操作定义为：假设树为空，那么空操作前假设树为空，那么空操作前往；否那么往；否那么 访问根结点；访问根结点； 按照从左到右的顺序前序按照从左到右的顺序前序遍历根结点的每一棵子树。遍历根结点的每一棵子树。 5.1 树的逻辑构造树的逻辑构造前序遍历序列：前序遍历序列：A B D E H I F C GACBGFEDHI数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社后序遍历后序遍历 树的后序遍历操作定义为：树的后序遍历操作定义为：假设树为空，那么空操作前假设树为空，那么空操作

15、前往；否那么往；否那么 按照从左到右的顺序后序按照从左到右的顺序后序遍历根结点的每一棵子树；遍历根结点的每一棵子树； 访问根结点。访问根结点。 5.1 树的逻辑构造树的逻辑构造后序遍历序列：后序遍历序列：D H I E F B G C AACBGFEDHI数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社层序遍历层序遍历 树的层序遍历操作定义为：树的层序遍历操作定义为：从树的第一层即根结点从树的第一层即根结点开场，自上而下逐层遍历，开场，自上而下逐层遍历，在同一层中，按从左到右的在同一层中，按从左到右的顺序对结点逐个访问。顺序对结点逐个访问。 5.1 树的逻辑构造树的逻辑构

16、造层序遍历序列：层序遍历序列：A B C D E F G H IACBGFEDHI数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造实现树的存储构造，关键是什么实现树的存储构造，关键是什么? ?什么是存储构造什么是存储构造? ?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么? ?思索问题的出发点：如何表示结点的双亲和孩子思索问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。如何表示树中结点之间的逻辑关系。数据元素以及数据元素之间的逻辑关系在存储器数据元素以及数据元素之间的逻辑关系在存储器中的表示。中的表示。数据结

17、构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社根本思想：用一维数组来存储树的各个结点普通根本思想：用一维数组来存储树的各个结点普通按层序存储，数组中的一个元素对应树中的一个按层序存储，数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数结点，包括结点的数据信息以及该结点的双亲在数组中的下标。组中的下标。 5.2 树的存储构造树的存储构造 data parentdata：存储树中结点的数据信息：存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标：存储该结点的双亲在数组中的下标数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出

18、版社template struct PNode DataType data; /数据域数据域 int parent; /指针域，双亲在数组中的下标指针域，双亲在数组中的下标 ; data parent5.2 树的存储构造树的存储构造树的双亲表示法本质上是一个静态链表。树的双亲表示法本质上是一个静态链表。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社下标下标 data parent012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 树的存储构造树的存储构造如何查找双亲结点？时间性能？如何查找双亲结点？时间性能？ACBHFE

19、DGI数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造ACBHFEDGI如何查找孩子结点？时间性能？如何查找孩子结点？时间性能？下标下标 data parentfirstchild 1 3 6 -1 8 -1-1-1-1012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 添加第一添加第一个孩子的域个孩子的域数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社下标下标 data parent rightsib-1-1 2 2-1-1 4 4 5 5 -1-17 7-1-1-1-15.

20、2 树的存储构造树的存储构造012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 ACBHFEDGI如何查找兄弟结点？时间性能？如何查找兄弟结点？时间性能？添加右兄弟的域添加右兄弟的域数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社链表中的每个结点包括一个数据域和多个指针域，链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。每个指针域指向该结点的一个孩子结点。 如何表示孩子？如何表示孩子？5.2 树的存储构造树的存储构造孩子链表表示法孩子链表表示法方案一：指针域的个数等于树的度方案一：指针域的个数等于树

21、的度data child1 child2 childd其中：其中：data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； child1childd：指针域，指向该结点的孩子。：指针域，指向该结点的孩子。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造缺陷：浪费空间缺陷：浪费空间ACBHFEDGIABCDEFGHI 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社链表中的每个结点包括一个数据域和多个指针域，链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。每个指针域指向该

22、结点的一个孩子结点。 如何表示孩子？如何表示孩子？5.2 树的存储构造树的存储构造孩子链表表示法孩子链表表示法方案二：方案二： 指针域的个数等于该结点的度指针域的个数等于该结点的度 data degree child1 child2 childd其中：其中：data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； degree：度域，存放该结点的度；：度域，存放该结点的度； child1childd：指针域，指向该结点的孩子。：指针域，指向该结点的孩子。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造缺陷：结点构造不一致缺

23、陷：结点构造不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社孩子链表表示法孩子链表表示法孩子链表的根本思想：把每个结点的孩子陈列起来，看成是孩子链表的根本思想：把每个结点的孩子陈列起来，看成是一个线性表，且以单链表存储，那么一个线性表，且以单链表存储，那么n个结点共有个结点共有 n 个孩子链个孩子链表。这表。这 n 个单链表共有个单链表共有 n 个头指针，这个头指针，这 n 个头指针又组成了个头指针又组成了一个线性表，为了便于进展查找采用顺序存储。最后，将存一个线性表，为了便于进展查找采用顺序存

24、储。最后，将存放放 n 个头指针的数组和存放个头指针的数组和存放n个结点的数组结合起来，构成孩个结点的数组结合起来，构成孩子链表的表头数组。子链表的表头数组。 5.2 树的存储构造树的存储构造如何表示孩子？如何表示孩子？将结点的一切孩子放在一同，构成线性表。将结点的一切孩子放在一同，构成线性表。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社child next孩子结点孩子结点struct CTNode int child; CTNode *next;5.2 树的存储构造树的存储构造template struct CBNode DataType data; CTNode

25、*firstchild; ;孩子链表表示法孩子链表表示法data firstchild表头结点表头结点数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社ACBHFEDGI012345678下标下标 data firstchild A B C D E F G H I 5.2 树的存储构造树的存储构造如何查找孩子结点？时间性能？如何查找孩子结点？时间性能？12 345 7 68 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社ACBHFEDGI012345678下标下标 data firstchild A B C D E F G H I 5.2 树的存储构

26、造树的存储构造12 345 7 68 如何查找双亲结点？时间性能？如何查找双亲结点？时间性能？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 ACBHFEDGI数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造ACBHFEDGI某结点的第一个孩子是独一的某结点的第一个孩子是独一的某结点的右兄弟是独一的某结点的右兄弟是独一的设置两个

27、分别指向该结点的设置两个分别指向该结点的第一个孩子和右兄弟的指针第一个孩子和右兄弟的指针 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template struct TNode DataType data; TNode *firstchild, *rightsib;5.2 树的存储构造树的存储构造结点构造结点构造firstchild data rightsibdata：数据域，存储该结点的数据信息；：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；：指针域，指向该结点第一个孩子；rightsib：指针域，指向该结点的右兄弟结点。：指针

28、域，指向该结点的右兄弟结点。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造ACBHFEDGI A B C D E F G H I如何查找兄弟结点？时间性能？如何查找兄弟结点？时间性能？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储构造树的存储构造ACBHFEDGI A B C D E F G H I如何查找孩子结点？时间性能？如何查找孩子结点？时间性能？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树是二叉树是n(n0)个结点的有限集合，该集合或者为个结点的有限集合，该

29、集合或者为空集称为空二叉树，或者由一个根结点和两棵空集称为空二叉树，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树组成。5.3 二叉树的逻辑构造二叉树的逻辑构造研讨二叉树的意义？研讨二叉树的意义？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的特点二叉树的特点 每个结点最多有两棵子树；每个结点最多有两棵子树； 二叉树是有序的，其次序不二叉树是有序的，其次序不能恣意颠倒。能恣意颠倒。 5.3 二叉树的逻辑构造二叉树的逻辑构造留意：二叉树和树是两种树构造。留意：二叉树和树是两种树构造。A

30、BCDEFGABAB数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的根本形状二叉树的根本形状空二叉树空二叉树只需一个根结点只需一个根结点左子树左子树根结点只需左子树根结点只需左子树右子树右子树根结点只需右子树根结点只需右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树5.3 二叉树的逻辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑构造二叉树的逻辑构造具有具有3 3个结点的树和具有个结点的树和具有3 3个结点的二叉树的形状个结点的二叉树的形状v二叉树和树是两种树构造。二叉树和树是两

31、种树构造。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社特殊的二叉树特殊的二叉树斜树斜树1 .一切结点都只需左一切结点都只需左子树的二叉树称为左子树的二叉树称为左斜树；斜树；2 .一切结点都只需右一切结点都只需右子树的二叉树称为右子树的二叉树称为右斜树；斜树；3.左斜树和右斜树统左斜树和右斜树统称为斜树。称为斜树。1. 在斜树中，每一层只需一个结点；在斜树中，每一层只需一个结点；2.斜树的结点个数与其深度一样。斜树的结点个数与其深度一样。 5.3 二叉树的逻辑构造二叉树的逻辑构造斜树的特点：斜树的特点：ABCABC数据结构（数据结构（C+版）第版）第2版版清华大学出版社

32、清华大学出版社满二叉树满二叉树在一棵二叉树中，假在一棵二叉树中，假设一切分支结点都存设一切分支结点都存在左子树和右子树，在左子树和右子树，并且一切叶子都在同并且一切叶子都在同一层上。一层上。满二叉树的特点：满二叉树的特点： 叶子只能出如今最下一层；叶子只能出如今最下一层； 只需度为只需度为0和度为和度为2的结点。的结点。5.3 二叉树的逻辑构造二叉树的逻辑构造特殊的二叉树特殊的二叉树CDEFGHIJKLM NO1112 13 14 15数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社满二叉树满二叉树5.3 二叉树的逻辑构造二叉树的逻辑构造不是满二

33、叉树，虽然不是满二叉树，虽然一切分支结点都有左一切分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树特殊的二叉树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社完全二叉树完全二叉树对一棵具有对一棵具有n个结点的个结点的二叉树按层序编号，二叉树按层序编号，假设编号为假设编号为i1in的结点与同样深度的的结点与同样深度的满二叉树中编号为满二叉树

34、中编号为i的的结点在二叉树中的位结点在二叉树中的位置完全一样。置完全一样。5.3 二叉树的逻辑构造二叉树的逻辑构造特殊的二叉树特殊的二叉树CDEFGHIJKLM NO1112 13 14 15CDEFGHIJ数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社在满二叉树中，从最后在满二叉树中，从最后一个结点开场，延续去一个结点开场，延续去掉恣意个结点，即是一掉恣意个结点，即是一棵完全二叉树。棵完全二叉树。5.3 二叉树的逻辑构造二叉树的逻辑构造A1523467910BCDEFGHIJK11L12M13N14O158A1523

35、4678910BCDEFGHIJ不是完全二叉树，结点不是完全二叉树，结点10与满二叉树中的结点与满二叉树中的结点10不是同一个结点不是同一个结点特殊的二叉树特殊的二叉树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1. 叶子结点只能出如今最下两层叶子结点只能出如今最下两层且最下层的叶子结点都集中在二且最下层的叶子结点都集中在二叉树的左面；叉树的左面；2. 完全二叉树中假设有度为完全二叉树中假设有度为1的的结点，只能够有一个，且该结点结点，只能够有一个，且该结点只需左孩子。只需左孩子。3. 深度为深度为k的完全二叉树在的完全二叉树在k-1层层上一定是满二叉树。上一定是满二

36、叉树。4. 在同样结点个数的二叉树中，在同样结点个数的二叉树中，完全二叉树的深度最小。完全二叉树的深度最小。 完全二叉树的特点完全二叉树的特点5.3 二叉树的逻辑构造二叉树的逻辑构造特殊的二叉树特殊的二叉树CDEFGHIJ数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-1 二叉树的第二叉树的第i层上最多有层上最多有2i-1个结点个结点i1。 证明：当证明：当i=1时，第时，第1层只需一个根结点，而层只需一个根结点，而 2i-1=20 =1，结论显然成立。，结论显然成立。假定假定i=k1ki时结论成立，即第时结论成立，即第k层上至多有层

37、上至多有2k-1个结点，个结点， 那么那么 i=k+1时，由于第时，由于第k+1层上的结点层上的结点是第是第k层上结点的孩子，而二叉树中每个结点最多有层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第个孩子，故在第k+1层上最大结点个数为第层上最大结点个数为第k层上的层上的最大结点个数的二倍，即最大结点个数的二倍，即22k-12k。结论成立。结论成立。5.3 二叉树的逻辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-2 一棵深度为一棵深度为k的二叉树中，最多有的二叉树中，最多有2k-1个结个结点，最少有点，最少有k个结点。个结点。

38、证明：由性质证明：由性质1 1，深度为，深度为k k的二叉树中结点个数最多的二叉树中结点个数最多 = = =2k-1=2k-1；每一层至少要有一个结点，因此深度为每一层至少要有一个结点，因此深度为k k的二叉树，的二叉树，至少有至少有k k个结点。个结点。kii1)(层上结点的最大个数第5.3 二叉树的逻辑构造二叉树的逻辑构造深度为深度为k且具有且具有2k-1个结点的二叉树一定是满二叉树，个结点的二叉树一定是满二叉树，深度为深度为k且具有且具有k个结点的二叉树不一定是斜树。个结点的二叉树不一定是斜树。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-3 在一棵二

39、叉树中，假设叶子结点数为在一棵二叉树中，假设叶子结点数为n0，度为度为2的结点数为的结点数为n2，那么有，那么有: n0n21。 证明证明: 设设n为二叉树的结点总数，为二叉树的结点总数，n1为二叉树中度为二叉树中度为为1的结点数，那么有：的结点数，那么有： nn0n1n2 在二叉树中，除了根结点外，其他结点都有独一的在二叉树中，除了根结点外，其他结点都有独一的一个分枝进入，一个度为一个分枝进入，一个度为1的结点射出一个分枝，的结点射出一个分枝，一个度为一个度为2的结点射出两个分枝，所以有：的结点射出两个分枝，所以有： nn12n21因此可以得到：因此可以得到：n0n21 。5.3 二叉树的逻

40、辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑构造二叉树的逻辑构造n个结点的满二叉树有多少个叶子结点？个结点的满二叉树有多少个叶子结点？解：由于在满二叉树中没有度为解：由于在满二叉树中没有度为1的结点，只需度为的结点，只需度为0的叶子结点和度为的叶子结点和度为2的分支结点，所以，的分支结点，所以，n n0 + n2n0n2 + 1 即叶子结点即叶子结点n0n + 1/2 性质性质5-3 在一棵二叉树中，假设叶子结点数为在一棵二叉树中，假设叶子结点数为n0，度为度为2的结点数为的结点数为n2，那么有，那么有: n0n21。 数据结

41、构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 5.3 二叉树的逻辑构造二叉树的逻辑构造证明：假设具有证明：假设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质根据完全二叉树的定义和性质2，有下式成立，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第第k-1层层第第k层层最少结点数最少结点数最多结点数最多结点数数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑构造二叉树的逻辑构造证明：假

42、设具有证明：假设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质根据完全二叉树的定义和性质2，有下式成立，有下式成立 2k-1 n 2k性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 对不等式取对数，有：对不等式取对数，有： k-1log2nk即：即： log2nklog2n+1由于由于k是整数，故必有是整数，故必有k log2n +1。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-5 对一棵具有对一棵具有n个结点的完全二叉树中从个结点的完全二叉树中从1开开场按层序

43、编号，那么对于恣意的序号为场按层序编号，那么对于恣意的序号为i1in的的结点简称为结点结点简称为结点i，有：，有： 1假设假设i1，那么结点，那么结点i的双亲结点的序号为的双亲结点的序号为 i/2；假设假设i1，那么结点，那么结点i是根结点，无双亲结点。是根结点，无双亲结点。 2假设假设2in，那么结点，那么结点i的左孩子的序号为的左孩子的序号为2i；假设假设2in，那么结点，那么结点i无左孩子。无左孩子。 3假设假设2i+1n，那么结点，那么结点i的右孩子的序号为的右孩子的序号为2i+1；假设；假设2i+1n，那么结点，那么结点 i无右孩子。无右孩子。 5.3 二叉树的逻辑构造二叉树的逻辑构

44、造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版一棵具有对一棵具有n个结点的完全个结点的完全二叉树中从二叉树中从1开场按层序编开场按层序编号，那么号，那么 结点结点i的双亲结点为的双亲结点为 i/2； 结点结点i的左孩子为的左孩子为2i； 结点结点i的右孩子为的右孩子为2i1。 5.3 二叉树的逻辑构造二叉树的逻辑构造性质性质5阐明，在完全二叉树中，结点的层序编号反映阐明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社ADT BiTreeData

45、 由一个根结点和两棵互不相交的左右子树构成，由一个根结点和两棵互不相交的左右子树构成， 结点具有一样数据类型及层次关系结点具有一样数据类型及层次关系Operation 5.3 二叉树的逻辑构造二叉树的逻辑构造同树类似，在不同的运用中，二叉树的根本操作不尽一样。下同树类似，在不同的运用中，二叉树的根本操作不尽一样。下面给出一个二叉树笼统数据类型定义的例子，简单起见，根本面给出一个二叉树笼统数据类型定义的例子，简单起见，根本操作只包含二叉树的遍历，在实践运用中，应根据详细需求重操作只包含二叉树的遍历，在实践运用中，应根据详细需求重新定义其根本操作。新定义其根本操作。数据结构（数据结构（C+版）第版

46、）第2版版清华大学出版社清华大学出版社 InitBiTree 前置条件：无前置条件：无 输入：无输入：无 功能：初始化一棵二叉树功能：初始化一棵二叉树 输出：无输出：无 后置条件：构造一个空的二叉树后置条件：构造一个空的二叉树DestroyBiTree 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：销毁一棵二叉树功能：销毁一棵二叉树 输出：无输出：无 后置条件：释放二叉树占用的存储空间后置条件：释放二叉树占用的存储空间 5.3 二叉树的逻辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 PreOrder 前置条件：二叉树已存在

47、前置条件：二叉树已存在 输入：无输入：无 功能：前序遍历二叉树功能：前序遍历二叉树 输出：二叉树中结点的一个线性陈列输出：二叉树中结点的一个线性陈列 后置条件：二叉树不变后置条件：二叉树不变 InOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：中序遍历二叉树功能：中序遍历二叉树 输出：二叉树中结点的一个线性陈列输出：二叉树中结点的一个线性陈列 后置条件：二叉树不变后置条件：二叉树不变 5.3 二叉树的逻辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 PostOrder 前置条件：二叉树已存在前置条件：二叉树已存在

48、输入：无输入：无 功能：后序遍历二叉树功能：后序遍历二叉树 输出：二叉树中结点的一个线性陈列输出：二叉树中结点的一个线性陈列 后置条件：二叉树不变后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：层序遍历二叉树功能：层序遍历二叉树 输出：二叉树中结点的一个线性陈列输出：二叉树中结点的一个线性陈列 后置条件：二叉树不变后置条件：二叉树不变 endADT5.3 二叉树的逻辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 二叉树的遍历是指从根结点出发，按照某种次序二叉树的遍历是指从根结点出发，

49、按照某种次序访问二叉树中的一切结点，使得每个结点被访问一访问二叉树中的一切结点，使得每个结点被访问一次且仅被访问一次。次且仅被访问一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性构造线性化非线性构造线性化5.3 二叉树的逻辑构造二叉树的逻辑构造笼统操作，可以是对结点进展的各种笼统操作，可以是对结点进展的各种处置，这里简化为输出结点的数据。处置，这里简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的遍历方式：二叉树的遍历方式：DLRDLR、LDRLDR、LRDLRD、DRL

50、DRL、RDLRDL、RLD RLD 假设限定先左后右，那么二叉树遍历方式有三种：假设限定先左后右，那么二叉树遍历方式有三种：前序：前序：DLR中序：中序：LDR后序：后序：LRD层序遍历：按二叉树的层序编号的次序访问各结点。层序遍历：按二叉树的层序编号的次序访问各结点。 5.3 二叉树的逻辑构造二叉树的逻辑构造思索二叉树的组成：思索二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社前序根遍历前序根遍历假设二叉树为空，那么空操作假设二叉树为空，那么空操作前往；否那么：前往；否那么：访问根结点；访问根结点；前

51、序遍历根结点的左子树；前序遍历根结点的左子树；前序遍历根结点的右子树。前序遍历根结点的右子树。5.3 二叉树的逻辑构造二叉树的逻辑构造前序遍历序列：前序遍历序列：A B D G C E FABCDEFG数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社中序根遍历中序根遍历假设二叉树为空，那么空操作前假设二叉树为空，那么空操作前往；否那么：往；否那么：中序遍历根结点的左子树；中序遍历根结点的左子树；访问根结点；访问根结点；中序遍历根结点的右子树。中序遍历根结点的右子树。 5.3 二叉树的逻辑构造二叉树的逻辑构造中序遍历序列：中序遍历序列：D G B A E C FABCDEF

52、G数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社后序根遍历后序根遍历假设二叉树为空，那么空操作前假设二叉树为空，那么空操作前往；否那么：往；否那么：后序遍历根结点的左子树；后序遍历根结点的左子树；后序遍历根结点的右子树。后序遍历根结点的右子树。访问根结点；访问根结点；5.3 二叉树的逻辑构造二叉树的逻辑构造后序遍历序列：后序遍历序列：G D B E F C AABCDEFG数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社层序遍历层序遍历二叉树的层次遍历是指从二二叉树的层次遍历是指从二叉树的第一层即根结点叉树的第一层即根结点开场，从上至下逐层遍历，开

53、场，从上至下逐层遍历，在同一层中，那么按从左到在同一层中，那么按从左到右的顺序对结点逐个访问。右的顺序对结点逐个访问。 5.3 二叉树的逻辑构造二叉树的逻辑构造层序遍历序列：层序遍历序列：A B C D E F GABCDEFG数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑构造二叉树的逻辑构造二叉树遍历操作练习二叉树遍历操作练习前序遍历结果：前序遍历结果：- + a * b - c d / e f中序遍历结果：中序遍历结果：a + b * c - d - e / f后序遍历结果：后序遍历结果：a b c d - * + e f / -数据结构（数据结

54、构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑构造二叉树的逻辑构造假设知一棵二叉树的前序或中序，或后序，或假设知一棵二叉树的前序或中序，或后序，或层序序列，能否独一确定这棵二叉树呢？层序序列，能否独一确定这棵二叉树呢？ABC例：知前序序列为例：知前序序列为ABC，那么能够的二叉树有，那么能够的二叉树有5种。种。ABC数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑构造二叉树的逻辑构造例：知前序遍历序列为例：知前序遍历序列为ABC，后序遍历序列为，后序遍历序列为CBA，那么以下二叉树都满足条件。，那么以下二叉树都满足条件。AB

55、CABC假设知一棵二叉树的前序序列和后序序列，能否假设知一棵二叉树的前序序列和后序序列，能否独一确定这棵二叉树呢？独一确定这棵二叉树呢？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社假设知一棵二叉树的前序序列和中序序列，能否假设知一棵二叉树的前序序列和中序序列，能否独一确定这棵二叉树呢？怎样确定？独一确定这棵二叉树呢？怎样确定？ 例如：知一棵二叉树的前序遍历序列和中序遍历序例如：知一棵二叉树的前序遍历序列和中序遍历序列分别为列分别为ABCDEFGHI ABCDEFGHI 和和BCAEDGHFIBCAEDGHFI，如何构造该二叉，如何构造该二叉树呢树呢? ? 5.3 二叉

56、树的逻辑构造二叉树的逻辑构造数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社前序：前序：A B C D E F G H IA B C D E F G H I中序：中序：B C A E D G H F IB C A E D G H F I前序：前序：B CB C中序：中序：B CB C5.3 二叉树的逻辑构造二叉树的逻辑构造 B C D EF GH IA前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHI数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社前序：前序：F G H IF G H I中序：中序：G H F

57、IG H F I5.3 二叉树的逻辑构造二叉树的逻辑构造前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHIABCDEFIGH数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1. 根据前序序列的第一个元素建立根结点；根据前序序列的第一个元素建立根结点；2. 在中序序列中找到该元素，确定根结点的左右子树在中序序列中找到该元素，确定根结点的左右子树的中序序列；的中序序列；3. 在前序序列中确定左右子树的前序序列；在前序序列中确定左右子树的前序序列；4. 由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；5.

58、由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。 5.3 二叉树的逻辑构造二叉树的逻辑构造知一棵二叉树的前序序列和中序序列，构造该二叉树知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：的过程如下： 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序存储构造顺序存储构造二叉树的顺序存储构培育是用一维数组存储二叉树二叉树的顺序存储构培育是用一维数组存储二叉树中的结点，并且结点的存储位置下标应能表达中的结点，并且结点的存储位置下标应能表达结点之间的逻辑关系结点之间的逻辑关系父子关系。父子关系。 如何利用数组下标来反映结点之间的逻辑关系

59、如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树和满二叉树中结点的序号可以独一地完全二叉树和满二叉树中结点的序号可以独一地反映出结点之间的逻辑关系反映出结点之间的逻辑关系 。5.4 二叉树的存储构造及实现二叉树的存储构造及实现数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 A B C D E F G H I J数组下标数组下标 1 2 3 4 5 6 7 8 9 10完全二叉树的顺序存储完全二叉树的顺序存储5.4 二叉树的存储构造及实现二叉树的存储构造及实现CDEFGHIJ以以编编号号为为下下标标数据结构（数据结构（C+版）第版）第2版

60、版清华大学出版社清华大学出版社二叉树的顺序存储二叉树的顺序存储ABC DE F G数组下标数组下标 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉树的存储构造及实现二叉树的存储构造及实现ABCDFGE以以编编号号为为下下标标ABCDFGE123561013按照完全按照完全二叉树编号二叉树编号数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的顺序存储二叉树的顺序存储ABC DE F G数组下标数组下标 0 1 2 3 4 5 6 7 8 9 10 11 125.4 二叉树的存储构造及实现二叉树的存储构造及实现ABCDFGEABCDFGE1235