7.3.1 二叉排序树的定义
原书定位
印刷页P283起,对应PDF第295页。下文为目视整理的知识提要;完整内容见原书对照。
BST 又称二叉搜索树或二叉查找树。教材按互异关键字讨论:任一结点的全部左子树关键字小于它,全部右子树关键字大于它,左右子树也分别为 BST。
中序遍历得到严格递增序列。判定 BST 要检查整棵子树的上下界,不能仅比较父结点与两个孩子。允许重复关键字时需另定保存计数或分支规则。

二叉排序树示例,原书P284。
下级知识点
对应练习
关联知识
- 5.3.1.2 中序遍历
- 5.3.2 线索二叉树
- 7.2.2 折半查找
- 7.3 树形查找
- 7.3.1.1 二叉排序树的查找
- 7.3.1.2 二叉排序树的插入
- 7.3.1.3 二叉排序树的构造
- 7.3.1.4 二叉排序树的删除
- 7.3.1.5 二叉排序树的查找效率
- 7.3.2 平衡二叉树
- 7.3.3 红黑树
- 8.2.2 折半插入排序
原书对照
展开原书对照截图

