首页 > 其他 > 详细

二叉搜索树

时间:2016-04-16 21:23:26      阅读:254      评论:0      收藏:0      [点我收藏+]

二叉搜索树

又称二叉排序树,它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不为空,则左子树上所有节点的值均小于它的父节点的值,若它的右字树不为空,则右子树上所有节点的值均大于它的父节点的值,它的左右子树叶分别是二叉排序树。二叉排序树能高效的实现查找,插入,删除。比较复杂的是删除操作后如何安排子节点.

插入节点

  • 若当前二叉树为空,则插入的元素为根节点
  • 若插入的元素小于根节点则在左子树中插入,若大于跟节点则在右子树中插入,递归执行此过程知道找到正确位置将元素插入

删除节点分几种情况:

  • 叶子节点:只要把指向该节点的指针指向空
  • 只有一个子节点的节点:只要把指向该节点指针指向其子节点就可以
  • 有两个子节点的节点:在左子树中查找前驱节点,如节点A,将A的值与与被删除节点进行交换,删除A节点

技术分享

两个概念:

前驱节点: 左子树中最大的节点

后继节点:右子树种的最小节点


技术分享
源代码

二叉搜索树

原文:http://www.cnblogs.com/phenixyu/p/5399201.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!