二叉查找树 ﹏ヽ暗。殇╰゛Y 2021-09-22 09:40 449阅读 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)
还没有评论,来说两句吧...