二叉搜索树的递归与非递归实现

2017-05-22 14:06 阅读 868 次 评论 2 条

二叉搜索树是一个备受面试笔试青睐的考点,其核心实现的难点主要围绕删除某个结点展开话题,鉴于其重要性,就二叉搜索树的删除作以图示,其余作以文字描述。

二叉搜索树的性质

二叉搜索树又称为二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

① 若它的左子树存在,则左子树所有结点的值都小于根节点的值。

② 若它的右子树存在,则右子树所有结点的值都大于根节点的值。

③ 它的左右子树也分别为二叉搜索树。

二叉搜索树的删除

删除某个结点在二叉排序树里是非常重要的,其难点在于针对不同的情况要写出不同的删除算法,总结起来有以下四点:

①叶子结点:直接删除。(可归类到②③中)

②删除的结点没有左孩子,只有右孩子(将右孩子连接到双亲结点上)。

③删除的结点没有右孩子,只有左孩子(将左孩子连接到双亲结点上)。

④删除的结点左右孩子都存在(找到右子树中中序遍历的第一个节点进行替换,将双亲结点与待删除的结点的孩子节点连接)。

非递归版本的实现

递归版本的实现

测试程序:

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:二叉搜索树的递归与非递归实现 | 术与道的分享
分类:编程素养 标签:
1024do.com导航_术与道导航平台

发表评论


表情

  1. alanxgorlan
    alanxgorlan 【农民】 @回复

    这几个图讲的不能更清楚!!! [强] [强] [强]