二叉树的概念
定义：二叉树是一种有序的树形结构。 定义：二叉树是一种有序的树形结构。它与一般 树形结构的区别是： 树形结构的区别是：
每个结点最多有两棵子树； 每个结点最多有两棵子树； 子树有左右之分，次序不能任意颠倒。 子树有左右之分，次序不能任意颠倒。 二叉树的5种基本形态 二叉树的 种基本形态 第42页 二叉树的性质
【性质1】 在二叉树的第 层上最多有 i-1个结点（i≥1） 在二叉树的第i层上最多有 个结点（ ≥ ） 层上最多有2 A B E F G H 第43页 C D
【性质2】深度为 的二叉树最多有2h -1个结点（h ≥1） 深度为h的二叉树最多有 个结点（ ） 深度为 的二叉树最多有 个结点 满二叉树：如果一个深度为 的二叉树拥有 满二叉树：如果一个深度为h的二叉树拥有 h-1个结 的二叉树拥有2 个结 点，则将它称为满二叉树。 则将它称为满二叉树。 满二叉树 完全二叉树：有一棵深度为 ，具有 个结点的二叉树， 完全二叉树：有一棵深度为h，具有n个结点的二叉树， 个结点的二叉树 若将它与一棵同深度的满二叉树中的所有结点按从上 到下，从左到右的顺序分别进行编号， 到下，从左到右的顺序分别进行编号，且该二叉树中 的每个结点分别与满二叉树中编号为1~n的结点位置 的结点位置 的每个结点分别与满二叉树中编号为 一一对应，则称这棵二叉树为完全二叉树。 一一对应，则称这棵二叉树为完全二叉树。 完全二叉树 第44页
满二叉树 满 二 叉 树 也 是 完 满 全 二 二 叉 树 完全二叉树 第45页
完 全 二 叉 树 是 叉 树 非完全二叉树
深度为4的 深度为 的 完全二叉树 第46页
【性质3】二叉树上叶子结点数比度为 的结点数多 二叉树上叶子结点数比度为2的结
16
点数多 二叉树上叶子结点数比度为 的结点数多1 A B E F G H C D 叶子结点 度为2的结点 第47页
【性质4】具有 个结点的完全二叉树的深度为 ?log2 (n+1) ? 具有n个结点的完全二叉树的深度为 具有 其中， 其中，?log2n? 的结果是不大于 ? 的结果是不大于log2n的最大整数 的最大整数
深度为4的 深度为 的 满二叉树 深度为4的 深度为 的 完全二叉树
log2(8+1) ? = ln9/In2=4 ?log2 (15+ 1)? =In16/In2=4 ? 深度为3的完全二叉树 具有4～ 深度为 的完全二叉树 具有 ～7 深度为4的完全二叉树 具有8～ 深度为 的完全二叉树 具有 ～15 深度为5的完全二叉树 具有15～ 深度为 的完全二叉树 具有 ～31
深度为6的完全二叉树 深度为 的完全二叉树 深度为7的完全二叉树 深度为 的完全二叉树 深度为8的完全二叉树 深度为 的完全二叉树 深度为9的完全二叉树 深度为 的完全二叉树 深度为10的完全二叉树 深度为 的完全二叉树 深度为11的完全二叉树 深度为 的完全二叉树
具有32～ 具有 ～63 具有64～ 具有 ～127 具有128～255 具有 ～ 具有256～511 具有 ～ 具有512～1023 具有 ～ 具有1024～2047 具有 ～ 第48页 树型结构方面的考题
1：在深度为7的满二叉树中,叶子结点的个数为（2006年4月） 在深度为7的满二叉树中,叶子结点的个数为（2006年 A)32 A)32 B)31 B)31 C)64 C)64 D)63 D)63 1答案：C。 答案： 。 答案
2：在深度为7的满二叉树中，度为2的结点个数为【 在深度为7的满二叉树中，度为2的结点个数为【
07年 】 。(07年4月） 2答案：63。 答案： 。 答案
一棵二叉树中共有70个叶子结点与80个度为1的结点， 70个叶子结点与80个度为 3：一棵二叉树中共有 70个叶子结点与80 个度为1的结点，则该二叉树中的总 07年 结点数为 （07年9月） A）219 B）221 C）229 3答案：A。 答案： 。 答案
D）231 个叶子结点。 】个叶子结点。 】个。（2005 4答案：19。 答案： 。 答案
17
某二叉树中度为2的结点有18 18个 4： 某二叉树中度为2的结点有18个，则该二叉树中有 【 （2005年4月） 2005年 年9月）
一棵二叉树第六层（根结点为第一层）的结点数最多为【 5：一棵二叉树第六层（根结点为第一层）的结点数最多为【
5答案：32。 答案： 。 答案 第49页 二叉树的存储
在计算机中，二叉树通常采用链式存储结构。 在计算机中，二叉树通常采用链式存储结构。
Llink info Rlink t
二叉树的存储结点的结构 A B D G ∧ A C B F ∧ ∧ C ∧ E D G ∧ E ∧ ∧ F ∧ 第50页 二叉树的遍历
遍历指不重复地访问二叉树中的所有结点。 遍历指不重复地访问二叉树中的所有结点。 不重复地访问二叉树中的所有结点 二叉树的遍历的次序与树型结构上的大多 数运算有联系。 数运算有联系。 遍历的方式有三种 序遍历（ （1）先（前）序遍历（DLR） ） ） （2）
18
中序遍历（LDR） ）中序遍历（ ） （3）后序遍历（LRD） ）后序遍历（ ） H 第51页 A C F G D B E
二叉树的遍历
遍历指不重复地访问二叉树中的所有结点。 遍历指不重复地访问二叉树中的所有结点。 不重复地访问二叉树中的所有结点 序遍历（ （1）先（前）序遍历（DLR） ） ） 若二叉树为空，则结束遍历操作； 若二叉树为空，则结束遍历操作；否则 访问根结点； 访问根结点； 先序遍历左子树； 先序遍历左子树； 遍历左子树 先序遍历右子树。 先序遍历右子树。 遍历右子树 G E B F A C D
先序遍历的结果： 先序遍历的结果： A B E C F G H D H 第52页
（2）中序遍历（LDR） ）中序遍历（ ） 若二叉树为空，则结束遍历操作； 若二叉树为空，则结束遍历操作；否则 中序遍历左子树； 中序遍历左子树； 访问根结点； 访问根结点； 中序遍历右子树。 中序遍历右子树。 中序遍历的结果： 中序遍历的结果： E B A F H G C D （3）后序遍历（LRD） ）后序遍历（ ） 若二叉树为空，则结束遍历操作； 若二叉树为空，则结束遍历操作；否则 后序遍历左子树； 后序遍历左子树； 后序遍历右子树； 后序遍历右子树； 访问根结点。 访问根结点。 后序遍历的结果： 后序遍历的结果： E B H G F D C A 第53页 A B E F G H C D 练习： 练习：
下图所示的二叉树经过三种遍历得到的顺序分别为？ 下图所示的二叉树经过三种遍历得到的顺序分别为？ A B D G E H C F
先序序列： 先序序列： ABDGCEFH 中序序列： 中序序列： DGBAECHF 后序序列： 后序序列： GDBEHFCA
19
根据先序遍历序列， 根据先序遍历序列，建立二叉树 第54页
树型结构方面的考题 2
1:设二叉树如下： 设二叉树如下： 设二叉树如下 （2010年3月） 年 月 对该二叉树进行后序遍历的 结果为 【3】 】 EDBGHFCA A B C F E G H D
2: 对如下二叉树（2006年4月） 对如下二叉树（ 年 月 进行后序遍历的结果为 A) ABCDEF B) DBEAFC D C) ABDECF D) DEBFCA 第55页 ⒌ 查找技术
查找是数据处理的重要内容。 查找是数据处理的重要内容。 查找指在一个给定的数据结构中查找指定的元素， 查找指在一个给定的数据结构中查找指定的元素， 该元素也称关键字。 该元素也称关键字。 若找到了满足条件的结点，称查找成功； 若找到了满足条件的结点，称查找成功；否则称查 找失败。 找失败。 衡量一个查找算法的主要标准是查找过程中对关键 字进行的平均比较次数。 字进行的平均比较次数。 通常根据不同的数据结构，采用不同的查找方法： 通常根据不同的数据结构，采用不同的查找方法： 顺序查找 二分查找 第56页 顺序查找
线性表中最简单的查找方法。 线性表中最简单的查找方法。 方法：从线性表的第一个元素开始， 方法：从线性表的第一个元素开始，依次将线性表 中的元素与关键字进行比较，若相等，则查找成功； 中的元素与关键字进行比较，若相等，则查找成功； 若将所有元素都与关键字进行了比较但不相等，则 若将所有元素都与关键字进行了比较但不相等， 查找失败。 查找失败。 顺序查找法的适用场合： 顺序查找法的适用场合： 对线性表中元素的排列次序没有要求； 对线性表中元素的排列次序没有要求； 对线性表的存储结构没有要求， 对线性表的存储结构没有要求，链式结构和顺 序结构均可。 序结构均可。 第57页
二分查找(折半查找)
20