考研专业课之统考计算机蓝宝书(22)

来源：跨考网 2009-01-05 22:42

3.2.5 二叉排序树

二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：
(1). 若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右
子树上所有结点的值均大于根结点的值。

(2). 左右子树也都是二叉排序树。

从其定义可见，二叉排序树的查找过程为：
(1). 若查找树为空，查找失败。

(2). 查找树非空，将给定值kx与查找树的根结点关键码比较。

订阅收藏考研专业课之统考计算机蓝宝书

(3). 若相等，查找成功，结束查找过程，否则，
a．当给kx小于根结点关键码，查找将在以左子女为根的子树上继续进行，转(1)
b．当给kx大于根结点关键码，查找将在以右子女为根的子树上继续进行，转(2)
先讨论向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。
构造一棵二叉排序树则是逐个插入结点的过程。