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

3.2.5 二叉排序树

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

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

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

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

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

• ·2010年迦思佑考研6000词逻辑辨证记忆
• ·2010年迦思佑张纪元考研6000词汇记忆课堂录音
• ·10版研究生英语难句过关-盘内容
• ·【VIP专享】2009新东方考研英语复试听力(音频+讲义)
• ·沪江考研原创：和我一起突破考研长难句1-33
• ·胡敏考研英语词汇-读故事记单词（09最新版）MP3
• ·2010淘金高阶考研英语词汇词典版MP3
• ·2010考研英语阅读理解精读100篇（高分版）文本下载
• ·2009年考研英语大纲词汇
• ·2010考研英语万能作文MP3

• 麦考瑞内部雅思7-7.5分部分题库
• 一月速背6000单词
• 英语口语需要自然流露
• 7月名师讲座
• 点滴积累学英语系列之一