跳转至

04 二叉搜索树

04-二叉搜索树

定义

二叉搜索树（BST, Binary Search Tree），也称二叉排序树或二叉查找树。

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

  1. 非空左子树的所有键值小于其根结点的键值
  2. 非空右子树的所有键值大于其根结点的键值

  3. 左、右子树都是二叉搜索树

    image.png

ADT 操作特别函数

  • Position Find( ElementType X, BinTree BST )：从二叉搜索树BST中查找元素X，返回其所在结点的地址；
  • Position FindMin( BinTree BST )：从二叉搜索树BST中查找并返回最小元素所在结点的地址；
  • Position FindMax( BinTree BST )：从二叉搜索树BST中查找并返回最大元素所在结点的地址。
  • BinTree Insert( ElementType X, BinTree BST )
  • BinTree Delete( ElementType X, BinTree BST )

查找