二叉查找树

﹏ヽ暗。殇╰゛Y 2021-09-22 09:40 519阅读 0赞

二叉查找树有这几个规则

1、若左子树不为空，那么左子树所有节点的值小于均小于他的根节点的值。

2、若右子树不为空，那么右子树的所有节点的值大于根节点的值。

3、左右子树也分别为二叉树排序树。

4、没有键值相等的节点。

注意：每个值都不能一样，如果有一样的，我们不需做考虑。

添加挺简单的，看下面的代码。

首先做准备

// 主要用来保存节点  
private Node<T> root ;  
// 用来操作节点的  
private Node<T> opRoot ;  
// 用来存放元素，准备遍历元素，放到list集合种  
private List<T> list = new ArrayList<>();

上面这些是准备数据

还需注意一下：Node里面除了左右节点外，还有指向父节点的parent

下面这些是真真的操作

public void insert(T t)\{  
if(opRoot == null)\{  
root.setT(t);  
opRoot = root;  
return ;  
\}  
opRoot = root ;  
Node<T> node = new Node<T>();  
node.setT(t);  
insert(opRoot , node) ;  
\}

// 这里使用的最简单递归方式，如果觉得这个简单你可以试试非递归的方式  
private void insert(Node<T> opRoot, Node<T> node) \{  
if(opRoot.getT().compareTo(node.getT()) > 0)\{  
if(opRoot.getLeft() != null)\{  
insert(opRoot.getLeft() , node ) ;  
\}else \{  
opRoot.setLeft(node);  
node.setParent(opRoot);  
\}  
\}  
if(opRoot.getT().compareTo(node.getT()) < 0)\{  
if(opRoot.getRight() != null)\{  
insert(opRoot.getRight() , node) ;  
\}else \{  
opRoot.setRight(node);  
node.setParent(opRoot);  
\}  
\}  
\}

现在重点来了：

请看下面这个图

假设，我们删除元素4

删除之后会变成这样。

我先提出一种，我做了两个小时写if else ，从第一个元素判断，先找出删除这个元素的parent(父节点)、left(左子树)、right(右子树)。先考虑的是父，父节点如果为空，按一般原则

我们需要考虑右子树，右子树是不是为空，如果为空了，我们需要判断左子树，左子树是不是为空，如果左子树为空了，我们返回null，如果不为空，我们返回左子树就行，如果

右子树不为null，我们把左子树放在右子树的最左边的下面。然后就这样if else 一直下去，做了两个小时，没做出来。

这个是我新想出来的，首先我们不考虑那么多，我只考虑那个结点下面的左子树和右子树，我们先把左子树放到右子树的最下的左子树，代码如下：

if(right == null )\{  
right = left ;  
\} else \{  
Node<T> rightLeft = findLeft(right.getLeft());  
if(rightLeft == null )\{  
right.setLeft(left);  
if(left != null)\{  
left.setParent(right);  
\}  
\}else\{  
rightLeft.setLeft(left);  
if(left != null ) \{  
left.setParent(rightLeft);  
\}  
\}  
\}

这里减少了很多需要考虑的东西，我们只需要考虑这个结点下的左子树和右子树，如果左子树为空，我们就把左子树放到右子树那，下面就不能考虑左子树了。

下面我们只需要判断结点的右子树和父结点

代码如下

if(parent == null) \{  
root = right ;  
\}else \{  
if ( right == null ) \{  
leftOrRightIsNull(parent , node) ;  
\}else \{  
leftOrRight(parent , right ) ;  
\}  
\}

下面是完整的删除代码

// 删除值  
public Node<T> delete(T t)\{  
Node<T> node = query(t);  
if(node == null )\{  
return null ;  
\}  
delete(node);  
return node ;  
\}  
private void delete(Node<T> node) \{  
Node<T> parent = node.getParent() ;  
Node<T> right = node.getRight() ;  
Node<T> left = node.getLeft() ;  
  
if(right == null )\{  
right = left ;  
\} else \{  
Node<T> rightLeft = findLeft(right.getLeft());  
if(rightLeft == null )\{  
right.setLeft(left);  
if(left != null)\{  
left.setParent(right);  
\}  
\}else\{  
rightLeft.setLeft(left);  
if(left != null ) \{  
left.setParent(rightLeft);  
\}  
\}  
\}  
// 这里如果是node=right，只是把node执行别的地方，并没有真的删除了  
if(parent == null) \{  
root = right ;  
\}else \{  
if ( right == null ) \{  
leftOrRightIsNull(parent , node) ;  
\}else \{  
leftOrRight(parent , right ) ;  
\}  
\}  
\}  
// 当父类元素不能空，右边没有元素，把这个元给清除了  
private void leftOrRightIsNull(Node<T> parent, Node<T> node) \{  
if(parent.getLeft().getT().compareTo(node.getT()) == 0)\{  
parent.setLeft(node.getLeft());  
\}else\{  
parent.setRight(node.getLeft());  
\}  
\}  
// 判断是删除父类左边还是父类右边，然后给删除了  
private void leftOrRight(Node<T> parent, Node<T> right) \{  
if(parent.getLeft().getT().compareTo(right.getParent().getT()) == 0)\{  
parent.setLeft(right);  
\}else\{  
parent.setRight(right);  
\}  
right.setParent(parent);  
\}  
private Node<T> findLeft(Node<T> left) \{  
if(left == null ) \{  
return null;  
\}  
if(left.getLeft() == null)\{  
return left ;  
\}else\{  
return findLeft(left.getLeft());  
\}  
\}

\# 如何觉得能帮助你，麻烦给作者一份信任，让作者能写下去的理由，不需要你给的太多，只需1块钱即可。  
!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20200328012323201.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg==,size\_16,color\_FFFFFF,t\_70)  
!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/2020032801220920.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg==,size\_16,color\_FFFFFF,t\_70)  
\# 如果作者写的有误或者想和作者分享更多，请添加作者微信，邀你进群需收10块钱群费。收钱的目的在于我们来着是学知识的，不是来着观望的  
!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20200328012545973.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg==,size\_16,color\_FFFFFF,t\_70)