数据结构-二叉排序树

二叉排序树详细讲解

二叉排序树

定义

二叉排序树,又称为二叉查找树。它或者是一颗空树,或者具有下列性质的二叉树。

  • 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 它的左、右子树也分别为二叉排序树。

二叉排序树插入

根据其定义,我们将插入节点的方法展示如下:

  1. 第一个输入的数据作为此二叉树的树根。
  2. 之后的数据以递归的方式与树根进行比较,小于数个置于左子树,大于树根置于右子树。

下面给出其递归实现过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//二叉排序树 插入
public void BinarySortTree(int ord,Node<Integer> currentNode,LinkBiTree<Integer> Tree){
//结束条件
if(currentNode!=null&&currentNode.getLchild()==null&&ord<currentNode.getData()){
Tree.insertL(ord,currentNode);
return;
}
else if(currentNode!=null
&&currentNode.getRchild()==null&&ord>=currentNode.getData()){
Tree.insertR(ord,currentNode);
return;
}
//递归条件
else if(ord<currentNode.getData()){
BinarySortTree(ord,currentNode.getLchild(),Tree);
}
else if(ord>=currentNode.getData()){
BinarySortTree(ord,currentNode.getRchild(),Tree);
}
}

建立二叉树后,我们仅需通过一次中序遍历(LDR,左下为最小值,右下为最大值)即可完成排序输出,当然,我们也可以将得到的结果放入队列中加以存储。

二叉排序树删除

对于二叉排序树中的节点A,对它的删除分为三种情况,目的就是不改变排序树的性质:

  1. 如果A为叶子节点,则直接删除节点A即可。

  2. 如果A只有一个子节点,就直接将A的子节点连至A的父节点上,并将A删除;

  3. 如果A有两个子节点,我们就以用A节点的直接前驱或者直接后继来替换A节点,调整直接前驱或者直接后继的位置。

    分析:

    下面分为三个情况进行讨论,对应上面的三类情况:

    情况一:叶子节点直接删除即可,但要注意删除其父节点的指针指向,也就是说,在搜索要删除节点的时候,要注意保存其父节点。

    情况二:也仅仅需要在搜索时注意找寻其父节点,然后进行该结点的父节点与该节点的子树(左右都可以)连接即可。

    情况三:当有两个子节点时,我们为了保持排序树本身的性质不变,需要找其直接前驱或者直接后继来顶替该位置,由上图我们可以看出,若寻找其直接前驱,应找其左子树的最大节点(上图为37节点);若找其直接后继,应找其右子树的最小节点(上图为48节点)。

    在这里,我们先按照找直接前驱进行讨论

    (1)如何寻找37节点呢?因为我们要删除47节点,所以我们寻找其直接前驱应在47的左子树上寻找最大值。问题相继就转变成了以35为根节点的一棵二叉排序树如何寻找最大值的问题。根据二叉排序树的定义和我们插入排序的一些经验来看,寻找一棵树的最大值仅需要不断的从根节点寻找其右孩子即可,直到当前结点的右孩子为空,那这个结点就是我们要寻找的节点。主要在寻找过程中保存其父节点,后续会用到。

    (2)找到之后,我们还需要考虑其替换节点本身可能造成的后果,由于我们寻找替换节点时的算法决定了用于替换的节点(上图37节点)只能够为两种情况:叶子节点和仅有一个左子树。这时我们可以分别加以处理:

    ​ 1)叶子节点时,我们仅需将其父节点的右子树置空即可;

    ​ 2)有左子树时,我们需要将其父节点的右孩子与其接待的左孩子进行连接。

    直接后继分析过程与上面类似,在此不再赘述。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------