第5章 树和二叉树

1、树的逻辑结构树的逻辑结构 树的存储结构树的存储结构 二叉树的逻辑结构二叉树的逻辑结构 二叉树的存储结构及实现二叉树的存储结构及实现 树、森林与二叉树的转换树、森林与二叉树的转换 哈夫曼树哈夫曼树 第第 5 章章 树和二叉树树和二叉树 本章的主要内容是本章的主要内容是 树的定义树的定义 树：树：n（n0）个个结点结点的有限的有限集合集合。 当当n0时，称为空树；时，称为空树； 任意一棵非空树满足以下条件：任意一棵非空树满足以下条件： 有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点； 当当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m0）个个互互 不相交

2、不相交的有限集合的有限集合T1, ,T2, , , ,Tm，其中每个集合又是一棵树，其中每个集合又是一棵树， 并称为这个根结点的并称为这个根结点的子树子树。 5.1 树的逻辑结构树的逻辑结构 树的定义是采用递归方法树的定义是采用递归方法 (a) 一棵树结构一棵树结构 (b)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 5.1 树的逻辑结构树的逻辑结构 树的定义树的定义 A CB GFED HI A CB GFD A CB GFD E 树的应用举例树的应用举例文件结构文件结构 5.1 树的逻辑结构树的逻辑结构 My Computer C:D:E:etc WINDOWSProgram

3、FilesPictureMusic 树的基本术语树的基本术语 结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。 树的度：树的度：树中各结点度的最大值。树中各结点度的最大值。 5.1 树的逻辑结构树的逻辑结构 C G BD EF KL H M IJ A 5.1 树的逻辑结构树的逻辑结构 叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。 分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。 C G BD EF K L H M IJ A 树的基本术语树的基本术语 孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个

4、结点的孩子结树中某结点子树的根结点称为这个结点的孩子结 点，这个结点称为它孩子结点的双亲结点；点，这个结点称为它孩子结点的双亲结点； 兄弟兄弟：具有同一个双亲的孩子结点互称为兄弟。：具有同一个双亲的孩子结点互称为兄弟。 5.1 树的逻辑结构树的逻辑结构 C G BD E F KL H M IJ A 树的基本术语树的基本术语 路径：路径：如果树的结点序列如果树的结点序列n1, n2, , nk有如下关系：结点有如下关系：结点ni是是 ni+1的双亲（的双亲（1=ik），则把，则把n1, n2, , nk称为一条由称为一条由n1至至nk的的 路径；路径上经过的边的个数称为路径；路径上经过的边的个数

5、称为路径长度路径长度。 C G BD EF KL H M IJ A 5.1 树的逻辑结构树的逻辑结构 树的基本术语树的基本术语 祖先、子孙：祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到结到结 点点y，那么那么x就称为就称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。 5.1 树的逻辑结构树的逻辑结构 C G BD EF KL H M IJ A 树的基本术语树的基本术语 结点所在层数：结点所在层数：根结点的层数为根结点的层数为1 1；对其余任何结点，；对其余任何结点， 若某结点在第若某结点在第k k层，则其孩子结点在第层，则其孩子结点在第k+1k+1层。层。 树

6、的深度：树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。 1 1层层 2层层 4 4层层 3层层 高度高度4 C G BD EF KL H M IJ C 5.1 树的逻辑结构树的逻辑结构 树的基本术语树的基本术语 CBD EF KL HJ A 7 1 234 568 910 层序编号：层序编号：将树中结点按照从上层到下层、同层从左将树中结点按照从上层到下层、同层从左 到右的次序依次给他们编以从到右的次序依次给他们编以从1 1开始的连续自然数。开始的连续自然数。 5.1 树的逻辑结构树的逻辑结构 树的基本术语树的基本术语 有序树、无序树：有序树、无序树：如果一棵树中结

7、点的各子树从左如果一棵树中结点的各子树从左 到右是有次序的，称这棵树为有序树；反之，称为到右是有次序的，称这棵树为有序树；反之，称为 无序树。无序树。 数据结构中讨论的一般都是有序树数据结构中讨论的一般都是有序树 5.1 树的逻辑结构树的逻辑结构 树的基本术语树的基本术语 A CB GFED A CB GFED CBD EF KL HJ 森林：森林：m (m0)棵互不相交的树的集合。棵互不相交的树的集合。 5.1 树的逻辑结构树的逻辑结构 树的基本术语树的基本术语 A 同构：同构：对两棵树，若通过对结点适当地重命名，就可以使对两棵树，若通过对结点适当地重命名，就可以使 这两棵树完全相等（结点数

8、相同，结点对应关系也相等）这两棵树完全相等（结点数相同，结点对应关系也相等） ，则称这两棵树同构。，则称这两棵树同构。 5.1 树的逻辑结构树的逻辑结构 树的基本术语树的基本术语 A CB GFED D AE CFBG 树结构和线性结构的比较树结构和线性结构的比较 线性结构线性结构树结构树结构 第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个） 无前驱无前驱无双亲无双亲 最后最后一一个数据元素个数据元素 叶子结点叶子结点(可以有可以有多多个个) 无后继无后继无孩子无孩子 其它数据元素其它数据元素其它结点其它结点 一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子

9、 一对一一对一 一对多一对多 5.1 树的逻辑结构树的逻辑结构 树的抽象数据类型定义树的抽象数据类型定义 ADT Tree Data 树是由一个根结点和若干棵子树构成，树是由一个根结点和若干棵子树构成， 树中结点具有相同数据类型及层次关系树中结点具有相同数据类型及层次关系 Operation InitTree 前置条件：树不存在前置条件：树不存在 输入：无输入：无 功能：初始化一棵树功能：初始化一棵树 输出：无输出：无 后置条件：构造一个空树后置条件：构造一个空树 5.1 树的逻辑结构树的逻辑结构 DestroyTree 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：销毁一棵树

10、功能：销毁一棵树 输出：无输出：无 后置条件：释放该树占用的存储空间后置条件：释放该树占用的存储空间 Root 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：求树的根结点功能：求树的根结点 输出：树的根结点的信息输出：树的根结点的信息 后置条件：树保持不变后置条件：树保持不变 树的抽象数据类型定义树的抽象数据类型定义 5.1 树的逻辑结构树的逻辑结构 Parent 前置条件：树已存在前置条件：树已存在 输入：结点输入：结点x 功能：求结点功能：求结点x的双亲的双亲 输出：结点输出：结点x的双亲的信息的双亲的信息 后置条件：树保持不变后置条件：树保持不变 Depth 前置条件：树

11、已存在前置条件：树已存在 输入：无输入：无 功能：求树的深度功能：求树的深度 输出：树的深度输出：树的深度 后置条件：树保持不变后置条件：树保持不变 树的抽象数据类型定义树的抽象数据类型定义 5.1 树的逻辑结构树的逻辑结构 PreOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：前序遍历树功能：前序遍历树 输出：树的前序遍历序列输出：树的前序遍历序列 后置条件：树保持不变后置条件：树保持不变 PostOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：后序遍历树功能：后序遍历树 输出：树的后序遍历序列输出：树的后序遍历序列 后置条件：树保持不变后

12、置条件：树保持不变 endADT 树的抽象数据类型定义树的抽象数据类型定义 5.1 树的逻辑结构树的逻辑结构 树的遍历操作树的遍历操作 树的遍历：树的遍历：从从根根结点出发，按照某种结点出发，按照某种次次序访问序访问树中所有结点树中所有结点 ，使得每个结点被访问一次且仅被访问一次。，使得每个结点被访问一次且仅被访问一次。 如何理解如何理解访问访问? ? 抽象抽象操作，操作，可以是对结点进行的各种处理，这里可以是对结点进行的各种处理，这里简化为输出简化为输出 结点的数据。结点的数据。 如何理解如何理解次序次序? ? 树树通常有前序（根）遍历、后序（根）遍历和层序（次）通常有前序（根）遍历、后序（

13、根）遍历和层序（次） 遍历三种方式。遍历三种方式。 5.1 树的逻辑结构树的逻辑结构 树结构（非线性结构）树结构（非线性结构）线性结构。线性结构。 遍历的实质遍历的实质? ? 前序遍历前序遍历 树的树的前序遍历前序遍历操作定义为：操作定义为： 若树为空，则空操作返回；否则若树为空，则空操作返回；否则 访问根结点；访问根结点； 按照从左到右的顺序按照从左到右的顺序前序遍历前序遍历 根结点的每一棵子树。根结点的每一棵子树。 5.1 树的逻辑结构树的逻辑结构 前序遍历序列：前序遍历序列： A B D E H I F C G A CB GFED HI 后序遍历后序遍历 树的后序遍历操作定义为：树的后序

14、遍历操作定义为： 若树为空，则空操作返回；否则若树为空，则空操作返回；否则 按照从左到右的顺序后序遍历按照从左到右的顺序后序遍历 根结点的每一棵子树；根结点的每一棵子树； 访问根结点。访问根结点。 5.1 树的逻辑结构树的逻辑结构 后序遍历序列：后序遍历序列： D H I E F B G C A A CB GFED HI 层序遍历层序遍历 树的层序遍历操作定义为：树的层序遍历操作定义为： 从树的第一层（即根结点）开从树的第一层（即根结点）开始始 ，自上而下自上而下逐层遍历，在逐层遍历，在同一层同一层 中，按从左到右中，按从左到右的顺序对结点逐的顺序对结点逐 个访问。个访问。 5.1 树的逻辑结

15、构树的逻辑结构 层序遍历序列：层序遍历序列： A B C D E F G H I A CB GFED HI A CB HFEDG I 写出该树的前序、后序、层写出该树的前序、后序、层 次遍历的序列次遍历的序列 根据前序、后序序列，如何确定一棵树？根据前序、后序序列，如何确定一棵树？ 前序：前序：ABDEIFCGH 后序：后序：DIEFBGHCA 原则：原则： 利用前序确定树根利用前序确定树根 利用后序确定子树利用后序确定子树 5.2 树的存储结构树的存储结构 实现树的存储结构，关键是什么实现树的存储结构，关键是什么? ? 树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么? ? 一对多的

16、关系一对多的关系 存储结构的关键：如何表示结点的双亲和孩子存储结构的关键：如何表示结点的双亲和孩子 如何表示树中结点之间的逻辑关系。如何表示树中结点之间的逻辑关系。 双亲表示法双亲表示法 基本思想：基本思想： 用一维数组来存储树的各个结点（一般按用一维数组来存储树的各个结点（一般按层序层序存储），存储）， 数组中的一个元素对应树中的数组中的一个元素对应树中的一个结点，一个结点， 每个结点记录两类信息：结点的数据信息以及该结点的双亲每个结点记录两类信息：结点的数据信息以及该结点的双亲 在数组中的下标。在数组中的下标。 5.2 树的存储结构树的存储结构 data parent data：存储树中结

17、点的数据信息存储树中结点的数据信息 parent：存储该结点的双亲在数组中的下标存储该结点的双亲在数组中的下标 template struct PNode T data; /数据域数据域 int parent; /指针域，双亲在数组中的下标指针域，双亲在数组中的下标 ; data parent 5.2 树的存储结构树的存储结构 树的双亲表示法实质上是一个树的双亲表示法实质上是一个静态链表静态链表。 双亲表示法中结点数据类型的定义双亲表示法中结点数据类型的定义 下标下标 data parent 0 1 2 3 4 5 6 7 8 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H

18、2 I 4 5.2 树的存储结构树的存储结构 如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？ 双亲表示法双亲表示法 A CB HFEDG I 5.2 树的存储结构树的存储结构 双亲表示法双亲表示法 A CB HFEDG I 如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？ 下标下标 data parent firstchild 1 3 6 -1 8 -1 -1 -1 -1 0 1 2 3 4 5 6 7 8 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 下标下标 data parent rightsib - -1 2 - -1 4 5 - -1

19、 7 - -1 - -1 5.2 树的存储结构树的存储结构 双亲表示法双亲表示法 0 1 2 3 4 5 6 7 8 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 A CB HFEDG I 如何查找如何查找兄弟兄弟结点？时间性能？结点？时间性能？ A CB HFEDG I A BC DEFGH I 5.2 树的存储结构树的存储结构 孩子表示法孩子表示法-多重链表表示法（多叉链表）多重链表表示法（多叉链表） 链表中的每个结点包括一个数据域和多个指针域，每个指针链表中的每个结点包括一个数据域和多个指针域，每个指针 域指向该结点的一个孩子结点。域指向该结点的一个孩子结

20、点。 如何确定链表中的结点结构？如何确定链表中的结点结构？ 5.2 树的存储结构树的存储结构 孩子表示法孩子表示法-多重链表表示法（多叉链表）多重链表表示法（多叉链表） 方案一：方案一：指针域的个数等于树的度指针域的个数等于树的度 data child1 child2 childd 其中：其中：data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息； child1childd：指针域，指向该结点的孩子。指针域，指向该结点的孩子。 5.2 树的存储结构树的存储结构 缺点：浪费空间缺点：浪费空间 A CB HFEDG I A BC DEFGH I 链表中的每个结点包括一个数据域和多个

21、指针域，每个指针链表中的每个结点包括一个数据域和多个指针域，每个指针 域指向该结点的一个孩子结点。域指向该结点的一个孩子结点。 如何确定链表中的结点结构？如何确定链表中的结点结构？ 5.2 树的存储结构树的存储结构 方案二：方案二： 指针域的个数等于该结点的度指针域的个数等于该结点的度 data degree child1 child2 childd 其中：其中：data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息； degree：度域，存放该结点的度；度域，存放该结点的度； child1childd：指针域，指向该结点的孩子。指针域，指向该结点的孩子。 孩子表示法孩子表示法-

22、多重链表表示法多重链表表示法 5.2 树的存储结构树的存储结构 缺点：结点结构不一致缺点：结点结构不一致 A CB HFEDG I A 2 I 0 B 3C 2 G 0H 0E 1F 0D 0 A CB HFEDG I 0 1 2 3 4 5 6 7 8 下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构 12 345 7 6 8 孩子表示法孩子表示法-孩子链表表示法（每个结点创建一个单链表）孩子链表表示法（每个结点创建一个单链表） 基本思想：基本思想： 把每个结点的孩子排列把每个结点的孩子排列起来，看成是一个线性表，且以单链起来，看

23、成是一个线性表，且以单链 表存储，表存储，则则n个结点共有个结点共有 n 个孩子链表个孩子链表。 这这 n 个单链表共有个单链表共有 n 个头指针，个头指针，这这 n 个头指针又组成了一个个头指针又组成了一个 线性表。线性表。 为了便于进行查找为了便于进行查找采用顺序存储存储每个链表的头指针采用顺序存储存储每个链表的头指针。 最后，最后，将存放将存放 n 个头指针的数组和存放个头指针的数组和存放n个结点的数组结合起个结点的数组结合起 来，构成孩子链表的来，构成孩子链表的表头数组表头数组。 5.2 树的存储结构树的存储结构 特点：将每个结点的所有孩子放在一起，构成线性表。特点：将每个结点的所有孩

24、子放在一起，构成线性表。 孩子表示法孩子表示法-孩子链表表示法（每个结点创建一个单链表）孩子链表表示法（每个结点创建一个单链表） A CB HFEDG I 0 1 2 3 4 5 6 7 8 下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构 12 345 7 6 8 孩子表示法孩子表示法-孩子链表表示法（每个结点创建一个单链表）孩子链表表示法（每个结点创建一个单链表） child next 孩子结点孩子结点 struct CTNode int child; CTNode *next; ; 5.2 树的存储结构树的存储结构 templ

25、ate struct CBNode T data; CTNode *firstchild; ; 孩子链表表示法孩子链表表示法 Data firstchild 表头结点表头结点 A CB HFEDG I 0 1 2 3 4 5 6 7 8 下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构 如何查找如何查找孩子孩子结结 点？点？ 12 345 7 6 8 A CB HFEDG I 0 1 2 3 4 5 6 7 8 下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构 12 34

26、5 7 6 8 如何查找如何查找双亲双亲 结点？结点？ 孩子双亲表示法孩子双亲表示法 5.2 树的存储结构树的存储结构 A CB HFEDG I 将双亲表示法和孩子链表表示法结合起来将双亲表示法和孩子链表表示法结合起来 下标下标 data parent 0 1 2 3 4 5 6 7 8 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 12 7 6 8 A CB HFEDG I 0 1 2 3 4 5 6 7 8 下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构 12 345 7 6 8 如何查找如何查

27、找兄弟兄弟 结点？结点？ 孩子兄弟表示法孩子兄弟表示法 5.2 树的存储结构树的存储结构 A CB HFEDG I 某结点的第一个孩子是惟一的某结点的第一个孩子是惟一的 某结点的右兄弟是惟一的某结点的右兄弟是惟一的 设置两个分别指向该结点的设置两个分别指向该结点的 第一个孩子和右兄第一个孩子和右兄弟的指针弟的指针 5.2 树的存储结构树的存储结构 孩子兄弟表示法孩子兄弟表示法 A CB HFEDG I B C D G H E F I A template struct TNode T data; TNode *firstchild, *rightsib; ; 5.2 树的存储结构树的存储结构

28、结点结构结点结构firstchild data rightsib data：数据域，存储该结点的数据信息；数据域，存储该结点的数据信息； firstchild：指针域，指向该结点第一个孩子；指针域，指向该结点第一个孩子； rightsib：指针域，指向该结点的右兄弟结点。指针域，指向该结点的右兄弟结点。 孩子兄弟表示法孩子兄弟表示法 5.2 树的存储结构树的存储结构 孩子兄弟表示法孩子兄弟表示法 A CB HFEDG I B C D G H E F I A 如何查找如何查找兄弟兄弟结点结点 ？ 5.2 树的存储结构树的存储结构 孩子兄弟表示法孩子兄弟表示法 A CB HFEDG I A B C

29、 D E F G H I 如何查找如何查找孩子孩子结点结点 ？ 树的存储结构小结树的存储结构小结 顺序存储：本质上是静态指针顺序存储：本质上是静态指针 双亲表示法双亲表示法 双亲、孩子表示法双亲、孩子表示法 链式存储：链式存储： 多重链表示法多重链表示法 孩子链表表示法孩子链表表示法 双亲孩子表示法双亲孩子表示法 孩子兄弟表示法孩子兄弟表示法 二叉树的定义二叉树的定义 二叉树是二叉树是n（n0）个结点的有限集合，该集合或者为空个结点的有限集合，该集合或者为空 集（称为空二叉树），或者由一个根结点和两棵集（称为空二叉树），或者由一个根结点和两棵互不相互不相 交交的、分别称为根结点的的、分别称为根

30、结点的左子树左子树和和右子树右子树的二叉树组成的二叉树组成 。 5.3 二叉树的逻辑结构二叉树的逻辑结构 结构简单，适合于计算机处理结构简单，适合于计算机处理 问题转化：将树转换为二叉树，从而利用二叉树解决树的问题转化：将树转换为二叉树，从而利用二叉树解决树的 有关问题。有关问题。 研究二叉树的意义？研究二叉树的意义？ 二叉树的特点：二叉树的特点： 每个结点最多有两棵子树；每个结点最多有两棵子树； 二叉树是有序的，其次序不二叉树是有序的，其次序不 能任意颠倒能任意颠倒。 5.3 二叉树的逻辑结构二叉树的逻辑结构 注意：二叉树和树是两种树结构。注意：二叉树和树是两种树结构。 A B C D E

31、F G A B A B 二叉树的基本形态二叉树的基本形态 空二叉树空二叉树只有一个根结点只有一个根结点 左子树左子树 根结点只有左子树根结点只有左子树 右子树右子树 根结点只有右子树根结点只有右子树 左子树左子树右子树右子树 根结点同时有左右子树根结点同时有左右子树 5.3 二叉树的逻辑结构二叉树的逻辑结构 5.3 二叉树的逻辑结构二叉树的逻辑结构 具有具有3 3个结点的二叉树的形态个结点的二叉树的形态 特殊的二叉树特殊的二叉树 斜树斜树 1 . .所所有结点都只有左子树的有结点都只有左子树的 二叉树称为二叉树称为左斜树左斜树； 2 . .所有结点都只所有结点都只有右子树的有右子树的 二叉树称

32、为二叉树称为右斜树右斜树； 3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜斜 树树。 1. 在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点； 2. .斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。 5.3 二叉树的逻辑结构二叉树的逻辑结构 斜树的特点：斜树的特点： A B C A B C 满二叉树满二叉树 在一棵二叉树中，在一棵二叉树中，如果所有如果所有 分支结点都存在左子树和右分支结点都存在左子树和右 子树子树，并且所有叶子都在并且所有叶子都在同同 一层上一层上。 满二叉树的特点满二叉树的特点： 1. 叶子只能出现在最下一层；叶子只能出现在最下一层； 2. 只有度为

33、只有度为0和度为和度为2的结点。的结点。 5.3 二叉树的逻辑结构二叉树的逻辑结构 特殊的二叉树特殊的二叉树 A 1 5 23 467 8910 BC DEFG HIJKLM NO 1112 13 14 15 满二叉树满二叉树 5.3 二叉树的逻辑结构二叉树的逻辑结构 不是满二叉树，虽然不是满二叉树，虽然 所有分支结点都有左所有分支结点都有左 右子树，但叶子不在右子树，但叶子不在 同一层上。同一层上。 满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多 满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多 A 1 5 23 46

34、7 BC DEFG LM 89 特殊的二叉树特殊的二叉树 完全二叉树完全二叉树 对一棵具有对一棵具有n个结点的二叉树个结点的二叉树 按层序编号，如果编号为按层序编号，如果编号为i（ 1in）的结点与同样深度的的结点与同样深度的 满二叉树中编号为满二叉树中编号为i的结点在的结点在 二叉树中的位置完全相同。二叉树中的位置完全相同。 5.3 二叉树的逻辑结构二叉树的逻辑结构 特殊的二叉树特殊的二叉树 A 1 5 23 467 8910 BC DEFG HIJKLM NO 1112 13 14 15 A 1 5 23 467 8910 BC DEFG HIJ 在满二叉树中，从最后在满二叉树中，从最后

35、一个结点开始，一个结点开始，连续连续去去 掉掉任意任意个结点，即是一个结点，即是一 棵完全二叉树。棵完全二叉树。 5.3 二叉树的逻辑结构二叉树的逻辑结构 A 1 5 23 467 910 BC DEFG HIJK 11 L 12 M 13 N 14 O 158 A 1 5 23 467 8910 BC DEFG HIJ 不是完全二叉树，结点不是完全二叉树，结点 10与满二叉树中的结点与满二叉树中的结点 10不是同一个结点不是同一个结点 特殊的二叉树特殊的二叉树 1. 叶子结点只能出现在最下两层叶子结点只能出现在最下两层 ，且最下层的叶子结点都集中在，且最下层的叶子结点都集中在 二叉树的左部；

36、二叉树的左部； 2. 完全二叉树中如果有度为完全二叉树中如果有度为1的的 结点，只可能有一个，且该结结点，只可能有一个，且该结点点 只有左孩子。只有左孩子。 3. 深度为深度为k的完全二叉树在的完全二叉树在k-1层层 上一定是满二叉树。上一定是满二叉树。 完全二叉树的特点完全二叉树的特点 5.3 二叉树的逻辑结构二叉树的逻辑结构 特殊的二叉树特殊的二叉树 A 1 5 23 467 8910 BC DEFG HIJ 二叉树的基本性质二叉树的基本性质 性质性质5-1 二叉树的第二叉树的第i层上最多有层上最多有2i- -1个结点（个结点（i1）。）。 证明：证明：当当i=1时时，第，第1层只有一个根

37、结点，而层只有一个根结点，而 2i-1=20 =1，结论显然成立。结论显然成立。 假定假定i=k（1ki）时结论成立，即第）时结论成立，即第k层上至多有层上至多有2k-1个结点，个结点， 则则 i=k+1时时，因为第，因为第k+1层上的结点是第层上的结点是第k层上结点的孩子，而层上结点的孩子，而 二叉树中每个结点最多有二叉树中每个结点最多有2个孩子，故在第个孩子，故在第k+1层上最大结点个层上最大结点个 数为第数为第k层上的最大结点个数的二倍，即层上的最大结点个数的二倍，即22k-12k。结论成立结论成立 。 5.3 二叉树的逻辑结构二叉树的逻辑结构 性质性质5-2 一棵深度为一棵深度为k的二

38、叉树中，最多有的二叉树中，最多有2k- -1个结点，最个结点，最 少有少有k个结点。个结点。 证明：由性质证明：由性质1可知，深度为可知，深度为k的二叉树中结点个数最多的二叉树中结点个数最多 = =2k-1； 每一层至少要有一个结点，因此深度为每一层至少要有一个结点，因此深度为k的二叉树，的二叉树， 至少有至少有k个结点。个结点。 k i i 1 )(层上结点的最大个数第 5.3 二叉树的逻辑结构二叉树的逻辑结构 深度为深度为k且具有且具有2k-1个结点的二叉树个结点的二叉树一定是一定是满二叉树，满二叉树， 深度为深度为k且具有且具有k个结点的二叉树个结点的二叉树不一定不一定是斜树。是斜树。

39、二叉树的基本性质二叉树的基本性质 性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的的 结点数为结点数为n2，则有则有: n0n21。 证明证明: 设设n为二叉树的结点总数，为二叉树的结点总数，n1为二叉树中度为为二叉树中度为1的结点的结点 数，则有：数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分在二叉树中，除了根结点外，其余结点都有唯一的一个分 枝进入，由于这些分枝是由度为枝进入，由于这些分枝是由度为1和度为和度为2的结点射出的，的结点射出的， 一个度为一个度为1的结点射出一个分枝，一个度为的结点射出一个分枝，一

40、个度为2的结点射出两的结点射出两 个分枝，所以有：个分枝，所以有： nn12n21 因此可以得到：因此可以得到：n0n21 。 5.3 二叉树的逻辑结构二叉树的逻辑结构 二叉树的基本性质二叉树的基本性质 5.3 二叉树的逻辑结构二叉树的逻辑结构 在有在有n个结点的满二叉树中，有多少个叶子结点？个结点的满二叉树中，有多少个叶子结点？ 因为在满二叉树中没有度为因为在满二叉树中没有度为1的结点，只有度为的结点，只有度为0的叶子结点的叶子结点 和度为和度为2的分支结点，所以，的分支结点，所以， n n0 + n2 n0n2 + 1 即叶子结点即叶子结点n0（n + 1）/2 二叉树的基本性质二叉树的基

41、本性质 性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的的 结点数为结点数为n2，则有则有: n0n21。 性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 5.3 二叉树的逻辑结构二叉树的逻辑结构 证明：假设具有证明：假设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k， 根据完全二叉树的定义和性质根据完全二叉树的定义和性质2，有下式成立，有下式成立 2k-1 n 2k 2k-1-1 2k-12k-1 第第k-1层层 第第k层层 最少结点数最少结点数最多结点数最多结点数 完全二叉树

42、的基本性质完全二叉树的基本性质 5.3 二叉树的逻辑结构二叉树的逻辑结构 证明：假设具有证明：假设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，根据完全，根据完全 二叉树的定义和性质二叉树的定义和性质2，有下式成立，有下式成立 2k-1 n 2k 完全二叉树的基本性质完全二叉树的基本性质 性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 对不等式取对数，有：对不等式取对数，有： k-1log2nk 即：即： log2nklog2n+1 由于由于k是整数，故必有是整数，故必有k log2n +1。 性质性质5-5 对一棵具有对一棵

43、具有n个结点的完全二叉树中从个结点的完全二叉树中从1开始按层序开始按层序 编号，则对于任意的序号为编号，则对于任意的序号为i（1in）的结点（简称为结点的结点（简称为结点i ），），有：有： （1）如果）如果i1，则结点则结点i的双亲结点的序号为的双亲结点的序号为 i/2；如果如果i1 ，则结点则结点i是根结点，无双亲结点。是根结点，无双亲结点。 (2)如果如果2in，则结点则结点i的左孩子的序号为的左孩子的序号为2i； 如果如果2in，则结点则结点i无左孩子。无左孩子。 (3)如果如果2i1n，则结点则结点i的右孩子的序号为的右孩子的序号为2i1；如果如果2i1 n，则结点则结点 i无右孩子

44、。无右孩子。 5.3 二叉树的逻辑结构二叉树的逻辑结构 完全二叉树的基本性质完全二叉树的基本性质 可以用归纳法证明其中的（可以用归纳法证明其中的（2）和（）和（3）：）： 当当i=1时，结论成立时，结论成立 1 2 3 (2)(2)如果如果2 2i in n，则结则结 点点i i的左孩子的序号为的左孩子的序号为 2 2i i； 如果如果2 2i in n，则结点则结点i i 无左孩子。无左孩子。 (3)(3)如果如果2 2i i1n1n，则则 结点结点i i的右孩子的序号的右孩子的序号 为为2 2i i1 1；如果如果2 2i i1 1 n n，则结点则结点 i i无右孩无右孩 子。子。 假设

45、：假设： 对于序号为对于序号为j(1ji)的结点，当的结点，当2jn时，其左孩时，其左孩 子存在且序号为子存在且序号为2j，当当2jn 时，其左孩子不时，其左孩子不 存在；存在； 当当2j+1n时，时， 其右孩子存在且序号为其右孩子存在且序号为2j+1， 当当2j+1n时，其右孩子不存在。时，其右孩子不存在。 (2)(2)如果如果2 2i in n， 则结点则结点i i的左的左 孩子的序号为孩子的序号为 2 2i i； 如果如果2 2i in n， 则结点则结点i i无左无左 孩子。孩子。 (3)(3)如果如果2 2i i 1n1n，则结点则结点 i i的右孩子的的右孩子的 序号为序号为2 2

46、i i1 1； 如果如果2 2i i1 1n n， 则结点则结点 i i无右无右 孩子。孩子。 j 2j2j+1 当当i=j+1时，时， 根据完全二叉树的定义，根据完全二叉树的定义， 若若 其左孩子存在，其左孩子结其左孩子存在，其左孩子结 点的序号等于点的序号等于 =2i， 且有且有 2in； 如果如果2in， 则左孩子不存则左孩子不存 在。在。 若右孩子结点存在，右孩子若右孩子结点存在，右孩子 结点的序号为结点的序号为2i+1，且有且有 2i+1n； 如果如果2i+1n，则右孩子不存则右孩子不存 在。在。 故（故（2）和（）和（3）得证。）得证。 j 2j 2j+1 i=j+1 2i2i+1

47、 由（由（2）和（）和（3）我）我 们 可 以 很 容 易 证 明们 可 以 很 容 易 证 明 （1）。）。 如果如果i i1 1，则结点则结点i i是是 根结点，无双亲结点。根结点，无双亲结点。 如果如果i i1 1，则结点则结点i i的的 双 亲 结 点 的 序 号 为双 亲 结 点 的 序 号 为 i/2i/2； i 2i2i+1 1 1 8910 4567 23 对一棵具有对一棵具有n个结点的完全个结点的完全 二叉树中从二叉树中从1开始按层序编开始按层序编 号，则号，则 l 结点结点i的双亲结点为的双亲结点为 i/2； l 结点结点i的左孩子为的左孩子为2i； l 结点结点i的右孩子

48、为的右孩子为2i1。 5.3 二叉树的逻辑结构二叉树的逻辑结构 性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映 了结点之间的逻辑关系。了结点之间的逻辑关系。 二叉树的抽象数据类型定义二叉树的抽象数据类型定义 ADT BiTree Data 由一个根结点和两棵互不相交的左右子树构成，由一个根结点和两棵互不相交的左右子树构成， 结点具有相同数据类型及层次关系结点具有相同数据类型及层次关系 Operation InitBiTree 前置条件：无前置条件：无 输入：无输入：无 功能：初始化一棵二叉树功能：初始化一棵二叉树 输出：无输出：无 后置条件：构造一个

49、空的二叉树后置条件：构造一个空的二叉树 5.3 二叉树的逻辑结构二叉树的逻辑结构 DestroyBiTree 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：销毁一棵二叉树功能：销毁一棵二叉树 输出：无输出：无 后置条件：释放二叉树占用的存储空间后置条件：释放二叉树占用的存储空间 InsertL 前置条件：二叉树已存在前置条件：二叉树已存在 输入：数据值输入：数据值x，指针，指针parent 功能：将数据域为功能：将数据域为x的结点插入到二叉树中，作为结点的结点插入到二叉树中，作为结点 parent的左孩子。如果结点的左孩子。如果结点parent原来有左孩子，原来有左孩子

50、， 则将结点则将结点parent原来的左孩子作为结点原来的左孩子作为结点x的左孩子的左孩子 输出：无输出：无 后置条件：如果插入成功，得到一个新的二叉树后置条件：如果插入成功，得到一个新的二叉树 二叉树的抽象数据类型定义二叉树的抽象数据类型定义 DeleteL 前置条件：二叉树已存在前置条件：二叉树已存在 输入：指针输入：指针parent 功能：在二叉树中删除结点功能：在二叉树中删除结点parent的左子树的左子树 输出：无输出：无 后置条件：如果删除成功，得到一个新的二叉树后置条件：如果删除成功，得到一个新的二叉树 Search 前置条件：二叉树已存在前置条件：二叉树已存在 输入：数据值输入

51、：数据值x 功能：在二叉树中查找数据元素功能：在二叉树中查找数据元素x 输出：指向该元素结点的指针输出：指向该元素结点的指针 后置条件：二叉树不变后置条件：二叉树不变 二叉树的抽象数据类型定义二叉树的抽象数据类型定义 PreOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：前序遍历二叉树功能：前序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 InOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：中序遍历二叉树功能：中序遍历二叉树 输出：二叉树中结点的一个线性

52、排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 二叉树的抽象数据类型定义二叉树的抽象数据类型定义 PostOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：后序遍历二叉树功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：层序遍历二叉树功能：层序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变

53、endADT 二叉树的抽象数据类型定义二叉树的抽象数据类型定义 二叉树的遍历操作二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二访问二 叉树中的所有结点，使得每个结点被访问一次且仅被叉树中的所有结点，使得每个结点被访问一次且仅被访问访问 一次。一次。 二叉树遍历操作的目的？二叉树遍历操作的目的？ 非线性结构线性化非线性结构线性化 5.3 二叉树的逻辑结构二叉树的逻辑结构 抽象操作，抽象操作，可以是对结点进行的各种处理，可以是对结点进行的各种处理， 这里这里简化为输出结点的数据。简化为输出结点的数据。 前序遍历前序遍历 中序遍历中序遍历

54、 后序遍历后序遍历 层序遍历层序遍历 二叉树的遍历方式：二叉树的遍历方式： DLR、LDR、LRD、 DRL、RDL、RLD 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种： 前序前序：DLR 中序中序：LDR 后序后序：LRD 层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。 5.3 二叉树的逻辑结构二叉树的逻辑结构 考虑二叉树的组成：考虑二叉树的组成： 根结点根结点D 左子树左子树L 右子树右子树R 二二 叉叉 树树 前序（根）遍历前序（根）遍历 若二叉树为空，则空操作返回；否则若二叉树为空，则空操作返回；否则

55、 ： 访问根结点；访问根结点； 前序前序遍历遍历根根结点的左子树；结点的左子树； 前序前序遍历遍历根根结点的右子树。结点的右子树。 5.3 二叉树的逻辑结构二叉树的逻辑结构 前序遍历序列：前序遍历序列：A B D G C E F A B C D E F G 二叉树的遍历操作二叉树的遍历操作 中序（根）遍历中序（根）遍历 若二叉树为空，则空操作返回；否则若二叉树为空，则空操作返回；否则 ： 中序中序遍历遍历根根结点的左子树；结点的左子树； 访问根结点；访问根结点； 中序中序遍历遍历根根结点的右子树。结点的右子树。 5.3 二叉树的逻辑结构二叉树的逻辑结构 中序遍历序列：中序遍历序列：D G B

56、A E C F A B C D E F G 二叉树的遍历操作二叉树的遍历操作 后序（根）遍历后序（根）遍历 若二叉树为空，则空操作返回；否则若二叉树为空，则空操作返回；否则 ： 后序后序遍历遍历根根结点的左子树；结点的左子树； 后序后序遍历遍历根根结点的右子树。结点的右子树。 访问根结点；访问根结点； 5.3 二叉树的逻辑结构二叉树的逻辑结构 后序遍历序列：后序遍历序列：G D B E F C A A B C D E F G 二叉树的遍历操作二叉树的遍历操作 层序遍历层序遍历 二叉树的层次遍历是指从二叉树二叉树的层次遍历是指从二叉树 的第一层（即根结点）开始，的第一层（即根结点）开始，从从 上

57、至下上至下逐层遍历，在同一层中，逐层遍历，在同一层中， 则按则按从左到右从左到右的顺序对结点逐个的顺序对结点逐个 访问。访问。 5.3 二叉树的逻辑结构二叉树的逻辑结构 层序遍历序列：层序遍历序列：A B C D E F G A B C D E F G 二叉树的遍历操作二叉树的遍历操作 5.3 二叉树的逻辑结构二叉树的逻辑结构 二叉树遍历操作练习二叉树遍历操作练习 前序遍历结果：前序遍历结果：- + a * b - c d / e f 中序遍历结果：中序遍历结果：a + b * c - d - e / f 后序遍历结果：后序遍历结果：a b c d - * + e f / - 5.3 二叉树的

58、逻辑结构二叉树的逻辑结构 若已知一棵二叉树的前序（或中序，或后序，或层序）若已知一棵二叉树的前序（或中序，或后序，或层序） 序列，能否唯一确定这棵二叉树呢？序列，能否唯一确定这棵二叉树呢？ A B C 例：已知前序序列为例：已知前序序列为ABC，则可能的二叉树有，则可能的二叉树有5种。种。 A B C 二叉树的遍历操作二叉树的遍历操作 5.3 二叉树的逻辑结构二叉树的逻辑结构 例：已知前序遍历序列为例：已知前序遍历序列为ABC，后序遍历序列为，后序遍历序列为CBA， 则下列二叉树都满足条件。则下列二叉树都满足条件。 A B C A B C 若已知一棵二叉树的前序序列和后序序列，能否唯一确若已知

59、一棵二叉树的前序序列和后序序列，能否唯一确 定这棵二叉树呢？定这棵二叉树呢？ 二叉树的遍历操作二叉树的遍历操作 若已知一棵二叉树的前序序列和中序序列，能否唯一确若已知一棵二叉树的前序序列和中序序列，能否唯一确 定这棵二叉树呢？怎样确定？定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别 为为ABCDEFGHI 和和BCAEDGHFI，如何构造该二叉树呢如何构造该二叉树呢? ? 5.3 二叉树的逻辑结构二叉树的逻辑结构 二叉树的遍历操作二叉树的遍历操作 前序：前序：A B C D E F G H I 中序：中序：B

60、 C A E D G H F I 前序：前序：B C 中序：中序：B C B C D E F G H I A 前序：前序： D E F G H I 中序：中序： E D G H F I A B C D E FG HI 前序：前序：F G H I 中序：中序：G H F I 前序：前序： D E F G H I 中序：中序： E D G H F I A B C D E FG HI A B C D EF IG H 顺序存储结构顺序存储结构 二叉树的顺序存储结构就是用一维数组存储二叉树中的结二叉树的顺序存储结构就是用一维数组存储二叉树中的结 点，并且结点的点，并且结点的存储位存储位置置（下标）应能体