小蚂蚁学习数据结构(32)——二叉排序树的概念
小蚂蚁学习数据结构(32)——二叉排序树的概念
嗜学如命的小蚂蚁 发表于2年前
小蚂蚁学习数据结构(32)——二叉排序树的概念
  • 发表于 2年前
  • 阅读 109
  • 收藏 2
  • 点赞 1
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: 二叉排序树的概念

二叉排序树,定义:

    1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。

    2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。

    3,左右子树本身又是一颗二叉树。

    定义也是一个递归定义。

二叉排序树的特点:

    中序遍历二叉排序树,可以得到关键字序列是一个递增的有序序列。

二叉排序树查找思路:

    1,如果二叉排序树为空,则查找失败。

    2,如果key等于当前根节点,则查找成功。

    3,如果key小于当前根节点的值,在继续在根的左子树中查找。

    4,如果key大于当前根节点的值,在继续在根的右子树中查找。

二叉排序树的代码实现:

    (略),哈哈哈,今天是除夕,在家里心不静,就不写了,感觉也不难,以后有时间再写。

二叉排序树的查找:

    在二叉排序树上的平均查找长度与二叉树的形态有关。

    当树的形态比较均衡时,树的高度较小,平均查找长度也较小。

二叉排序树的插入:

    1,如果二叉排序树为空,则待插节点作为根节点插入空树中。

    2,如果待插入的关键字值和根节点关键字值相等,则无需插入。

    3,如果插入的关键字小于根节点的数值,则插入到左子树中。

    4,如果插入的关键字大于根节点的数值,则插入到右子树中。

    5,如此进行下去,当然,如果该数值已经存在就不再插入同一个数值。

二叉排序树的删除:

    1,删除叶子节点,很简单,直接删除,父节点的指针域赋予NULL

    2,删除单分支节点,将父节点与孩子节点直接相连

    3,删除双分子节点,用它的中序后继替换它,并使整棵树保持BST性质。

二叉排序树的查找分析:

    刚才也提到了,这个和二叉排序树的排列生成顺序有关,如果这个二叉排序树的形态是一条直线的话,这和顺序查找没有什么不同,为了防止这种情况的产生,就出来了一个平衡二叉树的概念。

平衡二叉树:

    略,马上晚会就开始了,PS:祝大家新年快乐,万事如意。 (*^-^*)


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



标签: 数据结构
共有 人打赏支持
粉丝 132
博文 161
码字总数 100864
×
嗜学如命的小蚂蚁
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: