第5章树和二叉树-1

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

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

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

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

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

6、语树的基本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社祖先、子孙：祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到结点到结点y，则则x称为称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。5.1 树的逻辑结构树的逻辑结构CGBDEFKLHMIJA树的基本术语树的基本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社p 结点所在层数：结点所在层数：根结点的层数为根结点的层数为1 1；对其余任何结点，若某结；对其余任何结点，若某结点在第点在第k k层，则其孩子结点在第层，则其孩子结点在第k+1k+1层。层。p 树的深

7、度：树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社CBDEFKLHJA71234568910层序编号：层序编号：将树中结点按照从上层到下层、同层从左到右的将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从次序依次给他们编以从1 1开始的连续自然数。开始的连续自然数。5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语数据结构（数据结构（C+版）第版）第2版版

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

9、（C+版）第版）第2版版清华大学出版社清华大学出版社树结构和线性结构的比较树结构和线性结构的比较线性结构线性结构树结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子一对一一对一 一对多一对多5.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的抽象数据类型定义树的抽象数据类型定义ADT Tree

10、Data 树是由一个根结点和若干棵子树构成，树是由一个根结点和若干棵子树构成， 树中结点具有相同数据类型及层次关系树中结点具有相同数据类型及层次关系Operation5.1 树的逻辑结构树的逻辑结构树的应用很广泛，在不同的实际应用中，树的基本操作不树的应用很广泛，在不同的实际应用中，树的基本操作不尽相同。下面给出一个树的抽象数据类型定义的例子，简尽相同。下面给出一个树的抽象数据类型定义的例子，简单起见，基本操作单起见，基本操作只包含树的遍历只包含树的遍历，针对具体应用，需要，针对具体应用，需要重新定义其基本操作。重新定义其基本操作。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大

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

12、能：前序遍历树功能：前序遍历树 输出：树的前序遍历序列输出：树的前序遍历序列 后置条件：树保持不变后置条件：树保持不变 PostOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：后序遍历树功能：后序遍历树 输出：树的后序遍历序列输出：树的后序遍历序列 后置条件：树保持不变后置条件：树保持不变endADT树的抽象数据类型定义树的抽象数据类型定义5.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社树的遍历操作树的遍历操作 树的遍历：树的遍历：从从根根结点出发，按照某种结点出发，按照某种次次序访问序访问树中所有结点，树中所有结

13、点，使得每个结点被访问一次且仅被访问一次。使得每个结点被访问一次且仅被访问一次。 如何理解如何理解访问访问? ?抽象抽象操作，操作，可以是对结点进行的各种处理，这里可以是对结点进行的各种处理，这里简化为输出简化为输出结点的数据。结点的数据。如何理解如何理解次序次序? ?树通常有前序（根）遍历、后序（根）遍历和层序（次）树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。遍历三种方式。5.1 树的逻辑结构树的逻辑结构树结构（非线性结构）树结构（非线性结构）线性结构。线性结构。遍历的实质遍历的实质? ?数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社前序遍历前序遍

14、历 树的前序遍历操作定义为：树的前序遍历操作定义为：若树为空，则空操作返回；若树为空，则空操作返回；否则否则 访问根结点；访问根结点； 按照从左到右的顺序前序按照从左到右的顺序前序遍历根结点的每一棵子树。遍历根结点的每一棵子树。 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 树的逻辑结构树的逻辑结构层序遍历序列：层序遍历序列：A B C D E F G H IACBGFEDH

16、I数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构实现树的存储结构，关键是什么实现树的存储结构，关键是什么? ?什么是存储结构什么是存储结构? ?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么? ?思考问题的出发点：如何表示结点的双亲和孩子思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。如何表示树中结点之间的逻辑关系。数据元素以及数据元素之间的数据元素以及数据元素之间的逻辑关系逻辑关系在存储器在存储器中的表示。中的表示。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社双亲表示法双亲表

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

18、Type 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 树的存储结构树的存储结构如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？双亲表示法双亲表示法ACBHFEDGI数据结

19、构（数据结构（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 2- -1 4 5 - -17- -1- -15.2 树的存储结构树的存储结构双亲表示法双

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

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

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

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

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

25、ta 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 树的存储结构树的存储结构12 345 7 68 如何查找如何查找双亲双

26、亲结点？时间性能？结点？时间性能？数据结构（数据结构（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版版清华大学出版社清华大学出版

29、社二叉树的定义二叉树的定义 二叉树二叉树是是n(n0)个结点的有限集合，该集合或者为个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵空集（称为空二叉树），或者由一个根结点和两棵互不相交互不相交的、分别称为根结点的的、分别称为根结点的左子树左子树和和右子树右子树的的二叉树组成。二叉树组成。5.3 二叉树的逻辑结构二叉树的逻辑结构问题转化：将树转换为二叉树，从而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。决树的有关问题。研究二叉树的意义？研究二叉树的意义？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的特点二叉树的

30、特点 每个结点最多有两棵子树；每个结点最多有两棵子树； 二叉树是有序的，其次序不二叉树是有序的，其次序不能任意颠倒能任意颠倒。 5.3 二叉树的逻辑结构二叉树的逻辑结构注意：二叉树和树是两种树结构。注意：二叉树和树是两种树结构。ABCDEFGABAB数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数

31、据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构具有具有3 3个结点的树和具有个结点的树和具有3 3个结点的二叉树的形态个结点的二叉树的形态v二叉树和树是两种树结构。二叉树和树是两种树结构。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社特殊的二叉树特殊的二叉树斜树斜树1 . .所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树；2 . .所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树；3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜树斜树。1. 在斜树中，每一层只

32、有一个结点；在斜树中，每一层只有一个结点；2. .斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。 5.3 二叉树的逻辑结构二叉树的逻辑结构斜树的特点：斜树的特点：ABCABC数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社满二叉树满二叉树在一棵二叉树中，如果所在一棵二叉树中，如果所有分支结点都存在左子树有分支结点都存在左子树和右子树，并且所有叶子和右子树，并且所有叶子都在都在同一层上。同一层上。满二叉树的特点满二叉树的特点： 叶子只能出现在最下一层；叶子只能出现在最下一层； 只有度为只有度为0和度为和度为2的结点。的结点。5.3 二叉树的逻辑结构二叉树的逻辑结构

33、特殊的二叉树特殊的二叉树CDEFGHIJKLM NO1112 13 14 15数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社满二叉树满二叉树5.3 二叉树的逻辑结构二叉树的逻辑结构不是满二叉树，虽然不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多A1523467BCDEFGLM89特殊的二叉树特殊的二叉树数据结构（数据

34、结构（C+版）第版）第2版版清华大学出版社清华大学出版社完全二叉树完全二叉树对一棵具有对一棵具有n个结点的二个结点的二叉树按层序编号，如果编叉树按层序编号，如果编号为号为i（1in）的结点与的结点与同样深度的满二叉树中编同样深度的满二叉树中编号为号为i的结点在二叉树中的结点在二叉树中的位置完全相同。的位置完全相同。5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树CDEFGHIJKLM NO1112 13 14 15CDEFGHIJ数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社在满二叉树中，从最后在满二叉

35、树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意任意个结点，即是一个结点，即是一棵完全二叉树。棵完全二叉树。5.3 二叉树的逻辑结构二叉树的逻辑结构A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉树，结点不是完全二叉树，结点10与满二叉树中的结点与满二叉树中的结点10不是同一个结点不是同一个结点特殊的二叉树特殊的二叉树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1. 叶子结点只能出现在最下两层叶子结点只能出现在最下两层且最下层的叶子结点都集中在二且最下层的叶子结点都集中在二叉树的

36、左面；叉树的左面；2. 完全二叉树中如果有度为完全二叉树中如果有度为1的的结点，只可能有一个，且该结点结点，只可能有一个，且该结点只有左孩子。只有左孩子。3. 深度为深度为k的完全二叉树在的完全二叉树在k-1层层上一定是满二叉树。上一定是满二叉树。4. 在同样结点个数的二叉树中，在同样结点个数的二叉树中，完全二叉树的深度最小。完全二叉树的深度最小。 完全二叉树的特点完全二叉树的特点5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树CDEFGHIJ数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的基本性质二叉树的基本性质 性质性

37、质5-1 二叉树的第二叉树的第i层上最多有层上最多有2i- -1个结点（个结点（i1）。）。 证明：证明：当当i=1时时，第，第1层只有一个根结点，而层只有一个根结点，而 2i-1=20 =1，结论显然成立。结论显然成立。假定假定i=k（1ki）时结论成立，即第）时结论成立，即第k层上至多有层上至多有2k-1个结点，个结点， 则则 i=k+1时时，因为第，因为第k+1层上的结点是层上的结点是第第k层上结点的孩子，而二叉树中每个结点最多有层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第个孩子，故在第k+1层上最大结点个数为第层上最大结点个数为第k层上的层上的最大结点个数的二倍，即最大结点

38、个数的二倍，即22k-12k。结论成立。结论成立。5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-2 一棵深度为一棵深度为k的二叉树中，最多有的二叉树中，最多有2k- -1个结个结点，最少有点，最少有k个结点。个结点。 证明：由性质证明：由性质1，深度为，深度为k的二叉树中结点个数最多的二叉树中结点个数最多 = =2k-1；每一层至少要有一个结点，因此深度为每一层至少要有一个结点，因此深度为k的二叉树，的二叉树，至少有至少有k个结点。个结点。kii1)(层上结点的最大个数第5.3 二叉树的逻辑结构二叉树的逻辑结构深度为深

39、度为k且具有且具有2k-1个结点的二叉树个结点的二叉树一定是一定是满二叉树，满二叉树，深度为深度为k且具有且具有k个结点的二叉树个结点的二叉树不一定不一定是斜树。是斜树。二叉树的基本性质二叉树的基本性质 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的结点数为的结点数为n2，则有则有: n0n21。 证明证明: 设设n为二叉树的结点总数，为二叉树的结点总数，n1为二叉树中度为为二叉树中度为1的结点数，则有：的结点数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都

40、有唯一的在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为一个分枝进入，一个度为1的结点射出一个分枝，的结点射出一个分枝，一个度为一个度为2的结点射出两个分枝，所以有：的结点射出两个分枝，所以有： nn12n21因此可以得到：因此可以得到：n0n21 。5.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的基本性质二叉树的基本性质 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构n个结点的满二叉树有多少个叶子结点？个结点的满二叉树有多少个叶子结点？解：因为在满二叉树中没有度为解：因为在满二叉树中没有度为1的结点，只有度为的

41、结点，只有度为0的叶子结点和度为的叶子结点和度为2的分支结点，所以，的分支结点，所以，n n0 + n2n0n2 + 1 即叶子结点即叶子结点n0（n + 1）/2 二叉树的基本性质二叉树的基本性质 性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的结点数为的结点数为n2，则有则有: n0n21。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 5.3 二叉树的逻辑结构二叉树的逻辑结构证明：假设具有证明：假设具有n个结点的完全

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

43、树的基本性质 性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 对不等式取对数，有：对不等式取对数，有： k-1log2nk即：即： log2nklog2n+1由于由于k是整数，故必有是整数，故必有k log2n +1。 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社性质性质5-5 对一棵具有对一棵具有n个结点的完全二叉树中从个结点的完全二叉树中从1开开始按层序编号，则对于任意的序号为始按层序编号，则对于任意的序号为i（1in）的结的结点（简称为结点点（简称为结点i），），有：有： （1）如果）如果i1，则结点则结点i的

44、双亲结点的序号为的双亲结点的序号为 i/2；如如果果i1，则结点则结点i是根结点，无双亲结点。是根结点，无双亲结点。 （2）如果）如果2in，则结点则结点i的左孩子的序号为的左孩子的序号为2i；如果如果2in，则结点则结点i无左孩子。无左孩子。 （3）如果）如果2i+1n，则结点则结点i的右孩子的序号为的右孩子的序号为2i+1；如果如果2i+1n，则结点则结点 i无右孩子。无右孩子。 5.3 二叉树的逻辑结构二叉树的逻辑结构完全二叉树的基本性质完全二叉树的基本性质 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版一棵具有对一棵具有n个结点的完全个结

45、点的完全二叉树中从二叉树中从1开始按层序编开始按层序编号，则号，则l 结点结点i的双亲结点为的双亲结点为 i/2；l 结点结点i的左孩子为的左孩子为2i；l 结点结点i的右孩子为的右孩子为2i1。 5.3 二叉树的逻辑结构二叉树的逻辑结构性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。完全二叉树的基本性质完全二叉树的基本性质 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的抽象数据类型定义二叉树的抽象数据类型定义ADT BiTreeData 由一个根结点和两棵互不相交的左右子树构

46、成，由一个根结点和两棵互不相交的左右子树构成， 结点具有相同数据类型及层次关系结点具有相同数据类型及层次关系Operation 5.3 二叉树的逻辑结构二叉树的逻辑结构同树类似，在不同的应用中，二叉树的基本操作不尽相同。下同树类似，在不同的应用中，二叉树的基本操作不尽相同。下面给出一个二叉树抽象数据类型定义的例子，简单起见，基本面给出一个二叉树抽象数据类型定义的例子，简单起见，基本操作只包含二叉树的遍历，在实际应用中，应根据具体需要重操作只包含二叉树的遍历，在实际应用中，应根据具体需要重新定义其基本操作。新定义其基本操作。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社

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

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

49、rder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：后序遍历二叉树功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：层序遍历二叉树功能：层序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 endADT二叉树的抽象数据类型定义二叉树的抽象数据类型定义5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C+版）第版）第2版

50、版清华大学出版社清华大学出版社二叉树的遍历操作二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一访问二叉树中的所有结点，使得每个结点被访问一次且仅被次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化5.3 二叉树的逻辑结构二叉树的逻辑结构抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 数据结构（数据结构

51、（C+版）第版）第2版版清华大学出版社清华大学出版社二叉树的遍历方式：二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：前序前序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。 5.3 二叉树的逻辑结构二叉树的逻辑结构考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社前序（根）遍历前序（根）遍历若二叉树为

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

53、子树。 5.3 二叉树的逻辑结构二叉树的逻辑结构中序遍历序列：中序遍历序列：D G B A E C FABCDEFG二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社后序（根）遍历后序（根）遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；5.3 二叉树的逻辑结构二叉树的逻辑结构后序遍历序列：后序遍历序列：G D B E F C AABCDEFG二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C

54、+版）第版）第2版版清华大学出版社清华大学出版社层序遍历层序遍历二叉树的层次遍历是指从二二叉树的层次遍历是指从二叉树的第一层（即根结点）叉树的第一层（即根结点）开始，开始，从上至下从上至下逐层遍历，逐层遍历，在同一层中，则按在同一层中，则按从左到右从左到右的顺序对结点逐个访问。的顺序对结点逐个访问。 5.3 二叉树的逻辑结构二叉树的逻辑结构层序遍历序列：层序遍历序列：A B C D E F GABCDEFG二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构二叉树遍历操作练习二叉树遍历操作练习前序遍历结

55、果：前序遍历结果：- + a * b - c d / e f中序遍历结果：中序遍历结果：a + b * c - d - e / f后序遍历结果：后序遍历结果：a b c d - * + e f / -数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构若已知一棵二叉树的前序（或中序，或后序，或若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？层序）序列，能否唯一确定这棵二叉树呢？ABC例：已知前序序列为例：已知前序序列为ABC，则可能的二叉树有，则可能的二叉树有5种。种。ABC二叉树的遍历操作二叉树的遍历操

56、作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构例：已知前序遍历序列为例：已知前序遍历序列为ABC，后序遍历序列为，后序遍历序列为CBA，则下列二叉树都满足条件。，则下列二叉树都满足条件。ABCABC若已知一棵二叉树的前序序列和后序序列，能否若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？唯一确定这棵二叉树呢？二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社若已知一棵二叉树的前序序列和中序序列，能否若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树

57、呢？怎样确定？唯一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为序列分别为ABCDEFGHI 和和BCAEDGHFI，如何构如何构造该二叉树呢造该二叉树呢? ? 5.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社前序：前序：A B C D E F G H I中序：中序：B C A E D G H F I前序：前序：B C中序：中序：B C5.3 二叉树的逻辑结构二叉树的逻辑结构 B C D EF GH IA前序：前序：

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

59、的中序序列；3. 在前序序列中确定左右子树的前序序列；在前序序列中确定左右子树的前序序列；4. 由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；5. 由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。 5.3 二叉树的逻辑结构二叉树的逻辑结构已知一棵二叉树的前序序列和中序序列，构造该二叉已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：树的过程如下： 二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序存储结构顺序存储结构二叉树的顺序存储结构就是用一维数组存储二叉树二

60、叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的中的结点，并且结点的存储位存储位置置（下标）应能体现（下标）应能体现结点之间的结点之间的逻辑关系逻辑关系父子关系。父子关系。 如何利用数组下标来反映结点之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以唯一地中结点的序号可以唯一地反映出结点之间的逻辑关系反映出结点之间的逻辑关系 。5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 A B C D E F G H I J数组下标数组下标 1 2 3