点的先后顺序都是不变的。
3、满二叉树与完全二叉树
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在
满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第 k 层上有 2k-1 个结点,
且深度为 m 的满二叉树有 2m-1 个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一
层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其
右分支下的子孙结点的最大层次为 p,则其左分支下的子孙结点的最大层次或为 p,或为
p+1。
完全二叉树具有以下两个性质:
性质 5:具有 n 个结点的完全二叉树的深度为[log2n]+1。
性质 6:设完全二叉树共有 n 个结点。如果从根结点开始,按层次(每一层从左到右)用自
然数 1,2,……,n 给结点进行编号,则对于编号为 k(k=1,2,……,n)的结点有以
下结论:
① 若 k=1,则该结点为根结点,它没有父结点;若 k>1,则该结点的父结点编号为
INT(k/2)。
② 若 2k≤n,则编号为 k 的结点的左子结点编号为 2k;否则该结点无左子结点(显然也没
有右子结点)。
③ 若 2k+1≤n,则编号为 k 的结点的右子结点编号为 2k+1;否则该结点无右子结点。
考点 8 二叉树的遍历
考试链接:
考点 8 在笔试考试中考核几率为 30%,分值为 2 分,读者应该熟练掌握各种遍历的具体算
法,能由两种遍历的结果推导另一种遍历的结果。
在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。在先左后右的原则下,根据访
问根结点的次序,二叉树的遍历分为三类:前序遍历、中序遍历和后序遍历。
(1)前序遍历:先访问根结点、然后遍历左子树,最后遍历右子树;并且,在遍历左、右
子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。
(2)中序遍历:先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右
子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。
(3)后序遍历:先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右
子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。
疑难解答:树与二叉树的不同之处是什么?
在二叉树中,每一个结点的度最大为 2,即所有子树(左子树或右子树)也均为二叉树,而
树结构中的每一个结点的度可以是任意的。
1.5 查找技术
考点 9 顺序查找
考试链接:
考点 9 在笔试考试中考核几率在 30%,一般出现选择题中,分值为 2 分,读者应该具体掌
握顺序查找的算法。
查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始,依次
将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;若线性表中所有的元素
都与被查找元素进行了比较但都不相等,则表示查找失败。