数据结构-二叉搜索树

二叉搜索树详细讲解

二叉搜索树

二叉搜索树概论

二叉搜索树特点如下:

  • 可以为空集合,但若不是空集合则节点上一定要有一个键值。
  • 每一个树根的值需大于左子树的值
  • 每一个树根的值需小于右子树的值
  • 左右子树也是二叉搜索树
  • 树的每个节点值都不同

事实上,二叉搜索树是在二叉排序树的基础上的进一步延伸,所以,只要懂得二叉树的排序就可以理解二叉排序树的搜索。这样的结构有一个好处是很容易获得最大值(Maximum)、最小值(minimum)、某元素的前驱(Precursor)、某元素的后继(Successor)。

  1. 最大值:树的最右节点。
  2. 最小值:树的最左节点。
  3. 某元素前驱:左子树的最右。
  4. 某元素的后继:右子树的最左。

其基本操作有:(1)搜索 (2)遍历 (3)插入 (4)删除

二叉搜索树搜索

算法:

  1. 从根结点开始查找,把根结点设置为当前结点;

  2. 若当前结点为空,返回null;

  3. 若当前结点不为空,用当前结点的value跟查找value作比较;

  4. 若当前结点value等于查找value,那么该value就是查找目标,返回当前结点;

  5. 若当前结点value大于查找value,把当前结点的左子结点设置为当前结点,跳转步骤2;

  6. 若当前结点value小于查找value,把当前结点的右子结点设置为当前结点,跳转步骤2;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public  Node<Integer> searchInBinarySortTree(Node<Integer> root,int value){
if(root==null){
return null;
}
else if(root.getData().equals(value)){
return root;
}
else if(root.getData()>value){
return searchInBinarySortTree(root.getLchild(),value);
}
else if(root.getData()<value){
return searchInBinarySortTree(root.getRchild(),value);
}
return null;
}

二叉搜索树遍历

由于二叉搜索树的特性,如使用中序遍历则可输出一个排好序的二叉树,这里就不细讲了,若不了解请点击这里数据结构-LeetCode树相关题目进行了解。

二叉搜索树插入

这也可以运用递归,将二叉搜索树的结点与要插入的结点进行比较,若比当前节点大,则与当前节点右子树进行比较;否则,则与当前节点的左子树进行比较,知道找到其叶子节点,然后根据逻辑插入到左边还是右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
}
}

二叉搜索树删除

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

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

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

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

    分析:

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

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

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

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

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

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

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

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

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

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

线索二叉树

所谓”线索二叉树“,就是把那些二叉树中指向空的链接加以利用,再指向树的其他节点,而这些链接就称为“线索”,这棵树就被称为线索二叉树。

将二叉树转换成线索二叉树的步骤如下

  • 先将二叉树通过中序遍历方式按序排出,并将所有的空链接改成线索。
  • 如果线索链接指向该节点的左链接,则将该线索指到中序遍历顺序下前一个节点。
  • 如果线索链接指向该节点的右链接,则将该线索指到中序遍历顺序下后一个节点。
  • 指向一个空结点,并将此空结点的右链接指向自己,而空结点的左子树是此线索二叉树。

优点

  • 在二叉树做中序遍历时,不需要使用堆栈处理,但一般二叉树需要。
  • 由于充分使用空链表,所以避免了链表闲置浪费的情形。另外中序遍历时的速度也较快,节省不少时间。
  • 任一个节点都容易找出它的中序后继者和中序前行者,在中序遍历时可以不需使用堆栈或递归。

缺点

  • 在加入或删除节点时的速度比一般二叉树慢。
  • 线索子树间不能共享。
您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------