二叉排序树概念

二叉排序树又称二叉查找树。它或者是空二叉树，或者满足以下递归性质：

  • 左子树上所有结点关键字均小于根结点关键字。
  • 右子树上所有结点关键字均大于根结点关键字。
  • 左子树和右子树也分别是二叉排序树。

1000

查找与排序含义

二叉排序树可用于元素查找和排序：

  • 查找时，从根开始比较关键字，小于根就进入左子树，大于根就进入右子树。
  • 中序遍历二叉排序树，可以得到关键字的递增序列。

例如图中以 50 为根：

  • 左子树中的 26, 21, 30 都小于 50。
  • 右子树中的 66, 60, 70, 68 都大于 50。
  • 对任一子树也要继续满足“左小、根中、右大”。

二叉排序树的查找、插入、删除通常在查找章节展开；这里先记住定义和中序遍历性质。