软件设计师考试考点分析与真题详解（第4版）(4)

软件设计师 http://www.educity.cn/jiaocheng/zg7.html

例如如图1-7所示的二叉树，其前序遍历、中序遍历和后序遍历结果分别如下。

图1-7 二叉树遍历的例子

前序遍历：1,2,4,5,7,8,3,6。 中序遍历：4,2,7,8,5,1,3,6。 后序遍历：4,8,7,5,2,6,3,1。

以上3种遍历方法都是递归定义的，可通过递归函数分别加以实现。 性质6：一棵二叉树的前序序列和中序序列可以唯一地确定这棵二叉树。

根据性质6，给定一棵二叉树的前序序列和中序序列，我们可以写出该二叉树的后序序列。例如，某二叉树的前序序列为 ABHFDECKG，中序序列为HBDFAEKCG，则构造二叉树的过程如图1-8所示。

软件设计师 http://www.educity.cn/jiaocheng/zg7.html

图1-8 已知前序序列和中序序列，求二叉树的过程

1.2.3 二叉排序树

二叉排序树又称为二叉查找树，其定义为二叉排序树或者是一棵空二叉树，或者是具有如下性质（BST性质）的二叉树：

（1）若它的左子树非空，则左子树上所有结点的值均小于根结点； （2）若它的右左子树非空，则右子树上所有结点的值均大于根结点； （3）左、右子树本身又各是一棵二叉排序树。 例如，如图1-9所示就是一棵二叉排序树。

图1-9 二叉排序树的例子

软件设计师 http://www.educity.cn/jiaocheng/zg7.html

根据二叉排序树的定义可知，如果中序遍历二叉排序树，就能得到一个排好序的结点序列。二叉排序树上有查找、插入和删除等3种操作。下面，我们假设二叉排序树的结点只存储结点的键值，其类型与前面的二叉树的结点类型相同。 1.静态查找

静态查找是在二叉排序树上查找键值为key的结点是否存在，这可按以下步骤在二叉排序树ST上找值为key的结点：

如果二叉排序树ST为空二叉树，则查找失败，结束查找；

如果二叉排序树的根结点的键值等于key，则查找成功，结束查找；

如果key小于根结点的键值，则沿着根结点的左子树查找，即将根结点的左子树作为新的二叉排序树ST继续查找；

如果key大于根结点的键值，则沿着根结点的右子树查找，即将根结点的右子树作为新的二叉排序树ST继续查找。 2.动态查找

在二叉排序树上，为插入和删除操作需要而使用的查找称为动态查找，动态查找应得到两个指针，一个指向键值为key的结点，另一个指向该结点的父结点。为此，查找函数可设4个参数，查找树的根结点指针root，待查找值key，存储键值为key结点的父结点的指针pre，存储键值为key结点的指针p，但函数要考虑以下几种不同情况。 （1）二叉排序树为空，查找失败，函数使*p=NULL，*pre=NULL；

（2）二叉排序树中没有键值为key的结点，函数一直寻找至查找路径的最后一个结点，*pre指向该结点，*p=NULL，如果插入键值为key的结点，就插在该结点下； （3）查找成功，*p指向键值为key的结点，*p指向它的父结点。

软件设计师 http://www.educity.cn/jiaocheng/zg7.html

3.插入结点

将利用动态查找函数确定新结点的插入位置，然后分以下几种情况进行相应的处理。 （1）如果相同键值的结点已在二叉排序树中，则不再插入； （2）如果二叉排序树为空树，则以新结点为二叉排序树；

（3）将要插入结点的键值与插入后的父结点的键值比较，就能确定新结点是父结点的左子结点，还是右子结点，并进行相应插入。 4.删除结点

删除二叉排序树上键值为key的结点的操作如下。 （1）调用查找函数确定被删结点的位置；

（2）如被删结点不在二叉排序树上，则函数返回。否则，按以下情况分别处理。 1）如果被删除的结点是根结点，又可分两种情况：

（i）被删除结点无左子树，则以被删除结点的右子树作为删除后的二叉排序树； （ii）被删除结点有左子树，则以被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树。 2）如果被删除结点不是根结点，且被删除结点无左子结点：

（i）被删除结点是它的父结点的左子结点，则把被删除结点的右子树作为被删除结点的父结点的左子树；

（ii）被删除结点是它的父结点的右子结点，则把被删除结点的右子树作为被删除结点的父结点的右子树；

3）如果被删除结点不是根结点，且被删除结点有左子结点，则被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树，同时进行以下操作：

软件设计师 http://www.educity.cn/jiaocheng/zg7.html

（i）被删除结点是它的父结点的左子结点，则把被删除结点的左子树作为被删结点的父结点的左子树；

（ii）被删除结点是它的父结点的右子结点，则把被删除结点的左子树作为被删除结点的父结点的右子树。

1.2.4 平衡二叉树

为了保证二叉排序树的高度为log2n,从而保证二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O（log2n），在往树中插入或删除结点时，要调整树的形态来保持树的\平衡\使之既保持BST性质不变，又保证树的高度在任何情况下均为log2n,从而确保树上的基本操作在最坏情况下的时间均为O（log2n）。

平衡二叉树（Balanced Binary Tree或Height-Balanced Tree）又称为AVL树，是指树中任一结点的左右子树的高度大致相同。如果任一结点的左右子树的高度均相同（如满二叉树），则二叉树是完全平衡的。通常，只要二叉树的高度为O（1og2n），就可看做是平衡的。

平衡的二叉排序树指满足BST性质的平衡二叉树。AVL树中任一结点的左、右子树的高度之差的绝对值不超过1.若将二叉树上结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是–1、0和1。 在最坏情况下，n个结点的AVL树的高度约为1.44log2n.而完全平衡的二叉树度高约为log2n,AVL树是接近最优的。

1.2.5 线索树

二叉树在一般情况下无法直接找到某结点在某种遍历序列中的前驱和后继结点。若增加指针域来存放结点的前驱和后继结点信息，将大大降低存储空间的利用率。考查n个结点