构造二叉排序树的函数_构造二叉排序树的过程_构造二叉排序树

【习题及解析】

【例3-34】 二叉树为二叉排序树的（）条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。

A.充分不必要 B.必要不充分 C.充分必要 D.既不充分也不必要

【分析】 本题考查二叉排序树的定义。由二叉排序树的定义可知，在二叉排序树中，任一非终端结点的关键字的值大于其左子树中所有结点的关键字的值（当然也大于其左孩子的值），小于右子树中所有结点的关键字的值（当然也小于其右孩子的值）。分析至此，我们知道该题的选项中至少应该包括必要条件，故A、D可以排除。下面我们看是否充分，也即满足题干要求的二叉树是否一定是二叉排序树。我们可以用反证法，举出一个例子证明满足题干要求的二叉树不一定是二叉排序树。图3-39所示的二叉树满足题干的要求，54，46，但显然这不是一棵二叉排序树，其中序遍历序列为4,6,5，并非一个单增或单减的序列。故正确答案中不应包含充分条件，排除C。所以本题应该选B。

【解答】 B。

【例3-35】 设数据集合d={1,12,5,8,3,10,7,13,9}，试完成下列各题：

①依次取d中各数据，构造一棵二叉排序树bt。

②如何依据此二叉树bt得到d的一个有序序列。

③画出在二叉树bt中删除"12"后的树结构。

【分析】 本题考查的是有关二叉排序树的基本概念。其中①考查二叉排序树的生成和插入；②考查如何根据二叉排序树得到有序序列，即二叉排序树中序遍历；③考查二叉排序树的删除，且是删除结点中被删结点左右子树都非空的情形。依照前面介绍的二叉排序树的删除结点的规则，删除结点12时应先将其左子树中最右结点(结点10)的右指针指向其右子树的根结点(结点13)，即将结点10的右指针指向结点13，然后用其左子树的根(结点5)来替代被删除的结点12，即将结点1的右指针指向结点5。

【解答】 ①构造二叉排序树的过程如图3-40所示。

②d的有序序列为bt的中序遍历次序，即1,3,5,7,8,9,10,12,13。

③删除"12"后树结构如图3-41所示。

【例3-36】 已知一棵二叉排序树，其结构如图3-42a所示。画出依次删除关键字为a1=13，a2=12，a3=4，a4=8的各个结点后，该二叉排序树的结构。

【分析】 本题主要考查知识点二叉排序树的删除。构造二叉排序树其中a1=13为叶结点，可以直接删除，即将其父结点指向该结点的指针置为空。a2=12和a4=8结点为左右子树均非空的结点，删除的时候需将其左子树中的最右结点替代被删除的结点。a3=4结点为左子树为空，右子树非空的结点，删除时需用右子树的根结点替代被删除的结点。

【解答】 依次删除关键字为a1=13，a2=12，a3=4，a4=8的各个结点后，该二叉排序树的变化情况如图3-42所示。构造二叉排序树

二叉排序树的插入和建立（通过插入实现）算法不考虑树的平衡问题，因此有可能产生高度不平衡的二叉排序树，极端情况下将退化成一个单链表，如图3-43所示，失去了二叉排序树的优点。因此在二叉排序树的插入过程中必须调整树的结构，使之平衡化。为此我们引入平衡二叉树(L树)的概念。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26201-1.html