美文网首页
4 二叉查找树(binary search tree)

4 二叉查找树(binary search tree)

作者: Allen的光影天地 | 来源:发表于2018-10-31 16:52 被阅读7次

定义

可以为空,如果不为空的话,需要满足以下条件:

  1. 左子树所有键值小于其根节点的键值
  2. 右子树所有键值大于其根节点的键值
  3. 左右都是二叉查找树

操作函数

  1. 查找函数
    与节点作比较,小于节点就到左子树,大于节点就到右子树查找
    两种实现方法:
    一种是递归实现,代码很简洁,效率不高,属于伪递归
    一种是循环实现,从编译的角度,所有的伪递归都可以用循环实现
  2. 查找最大元素和最小元素
    最大元素,一定是最右边;最小元素,一定是最左面
  3. 二叉树的插入
    关键是找到元素的插入位置,而且在插入的时候,要往哪插?这里需要记录上一个节点
  4. 二叉树的删除
    三种情况:
    1. 删除叶节点:直接删除,将父节点相关的指针设为null
    2. 删除节点只有一个孩子:将父节点的指针指向要删除节点的孩子节点
    3. 删除的节点左右都有孩子:用左子树的最大元素或右子树的最小元素替代被删除节点

相关文章

网友评论

      本文标题:4 二叉查找树(binary search tree)

      本文链接:https://www.haomeiwen.com/subject/wwvatqtx.html