的度。
树是一种层次结构。树的最大层次称为树的深度。
*考点 16 二叉树及基本性质
二叉树具有以下两个特点：
（1）非空二叉树只有一个根结点；
（2）每个结点最多有两棵子树，且分别称为该结点的左子树和右子树。
二叉树有以下性质：
（1）在二叉树的第 k 层上，最多有 2*(k-1)(k>=1)个结点。
（2）深度为 m 的二叉树最多有 2*m-1 个结点。(1、2 中*代表次幂)
（3）在任意一棵二叉树中，度为 0 的结点总是比度为 2 的结点多一个。
（4）具有 n 个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]取整数部分（表示以
2 为底）。
注：（4）根据（2）得到
在满二叉树中，每一层上的结点都达到最大值，即在满二叉树的第 k 层上有 2*(k-1)个结
点，且深度为 m 的满二叉树有 2*m-1 个结点。注意：2 的（k-1）次幂与 2 的 m 次幂减一的
区别。
完全二叉树指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右
边的若干结点。
满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。
考点 17 二叉树的存储结构
与线性链表类似，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点也
由两部分组成：数据域与指针域。指针域有两个一个指向左子结点存储地址，称为左指针
域，另一个为右指针域。
*考点 18 二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。
二叉树的遍历可以分三种：
(1)前序遍历。若二叉树为空，则结束返回。否则：根结点、左子树、右子树。
(2)中序遍历。左子树、根结点、右子树。
(3)后序遍历。左子树、右子树、根结点。
1.7 查找技术
*考点 19 顺序查找
在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比
较便查找成功，查找效率最高；如果被查找的元素是线性表中的最后一个元素，或者被
查元素不在线性表中，则需要与线性表中的所有元素进行比较，这是顺序查找的最坏情
况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中的一半
元素进行比较。
（在下列两种情况下只能采用顺序查找：一线性表为无序表即表中元素的排列是无序的 ；
二即使是有序线性表，如果采用链式存储结构，也只能采用顺序查找。）
*考点 20 二分法查找
二分法查找只适用于顺序存储的有序表。在此说的有序表是指线性表中的元素按值非递减
排列（即从小到大，但允许相邻元素值相等）。
对于长度为 n 的有序线性表，在最坏情况下，二分法查找只需要比较 log2n 次，而顺序查
找需要比较 n 次。
1.8 排序技术