7.3.1 二叉排序树的定义

教材导航 · 第7章

原书定位

印刷页P283起,对应PDF第295页。下文为目视整理的知识提要;完整内容见原书对照。

BST 又称二叉搜索树或二叉查找树。教材按互异关键字讨论:任一结点的全部左子树关键字小于它,全部右子树关键字大于它,左右子树也分别为 BST。

中序遍历得到严格递增序列。判定 BST 要检查整棵子树的上下界,不能仅比较父结点与两个孩子。允许重复关键字时需另定保存计数或分支规则。

二叉排序树示例

二叉排序树示例,原书P284。

下级知识点

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P283,PDF第295页

原书对照,原书P284,PDF第296页