二叉搜索树的Java递归实现

╰半橙微兮° 2023-09-28 13:42 156阅读 0赞

#### 目录 ####

*  **前言**
 *  **二叉搜索树**
 *  **代码实现**
 *   *  **add**
     *   *  **add代码**
     *  **remove**
     *   *  **被删除节点的两种类型**
         *   *  **删除节点的2种方式**
         *  **remove代码**

## **前言** ##

打算从二叉搜索树开始，然后AVL树，最后写红黑树和B+树；话说为什么要写这系列文章呢？可能是在网上白嫖太多好文章以及视频，希望通过这几篇文章能够帮助大家更好理解红黑树和B+树吧。

红黑树是比较重要的结构HashMap，ConcurrentHashMap中就使用到了这种数据结构。不理解红黑树就很难说完全理解了HashMap，ConcurrentHashMap；如果直接写红黑树的add，remove过程又会引出二叉搜索树以及AVL树中的节点旋转的知识，直接写红黑树就很难写；因此从二叉搜索树开始，这是红黑树的基础。

## **二叉搜索树** ##

二叉树是一种简单的数据结构，每一个节点都最多只能有2个分支；

![在这里插入图片描述][b9c1572375f3486c8a734220f05c0437.png_pic_center]

现在有一个问题，如何快速的找出存在于二叉树的某一个数字？如果对二叉树不做任何限制，那么二叉树是无序的没有规则的；因此就必须搜索整颗二叉树才能找到；这样效率就不高浪费时间；要提高搜索效率就要对加入二叉树的节点做限制，让节点之间有规律；二叉搜索树就是给二叉树加了一条规则：**当前节点值大于左节点，小于右节点**；依据这个性质来做搜索，就会快很多；可以根据当前节点与搜索值作比较，比当前值大，就搜索右分支，比当前值小就搜索左分支；

![在这里插入图片描述][79ca1e4eb90b4e489e98f61dbe75366d.png_pic_center]

## **代码实现** ##

### **add** ###

![c42539d170904431b85a4c5623c1b04e.png_pic_center][]

#### **add代码** ####

Node root;
        class Node {
        
            int data ;
            Node left;
            Node right;
            Node parent;
            Node(int data ,Node left,Node right,Node parent){
        
                this.data = data;
                this.left = left;
                this.right = right;
                this.parent = parent;
            }
            Node (int data){
        
                this(data,null,null,null);
            }
        }
    
    
        public void addVal(int val){
        
            Node node  = new Node(val);
            if(root != null)
                add(node,root);
            else
                root =  node;
        }
    
         void add(Node node,Node temp){
        
    
            if(temp.data == node.data)return ;
            else if(temp.data  > node.data){
        
                if(temp.left == null){
        
                    temp.left = node;
                    node.parent = temp;
                }else
                    add(node,temp.left);
            }else{
        
                if(temp.right == null){
        
                    temp.right = node;
                    node.parent = temp;
                }else
                    add(node,temp.right);
            }
        }

### **remove** ###

#### **被删除节点的两种类型** ####

remove节点时，有2大类情况：删除叶子节点，删除非叶子节点；

*  对于叶子节点可以直接删除，不会破坏二叉搜索树的规则；

![在这里插入图片描述][4088cf1604a64950a466dc8dbe37e620.png_pic_center]

*  非叶子节点的删除，必须要找一个替代节点顶替被删除节点的位置；
    
     *  被删除的节点有左右子节点；这种情况，可以选择左边节点最大值或者右边节点最小值来填补被删除的节点  
        ![在这里插入图片描述][4dc3c335d56d4268ad6742e7a017d68d.png_pic_center]  
          
        
     *  只有一个节点，用子节点代替被删除节点；

##### **删除节点的2种方式** #####

删除目标节的2种方式：

*  1.直接删除目标节点，再将替代节点放到被删除节点的位置；

![85ef935338e347efbc99a7934702d20b.png_pic_center][]

*  2.用代替节点的值覆盖被删除节点的值，然后将代替节点删除；

![0ac91f08a6fb4518a78a66cd429eb895.png_pic_center][]

使用第一种方式直接删除节点相较于第二种方式比较麻烦，直接删除目标节点 (A) 之后:

*  顶替的节点（B）还需要重新设置属性parent，left，right信息；
 *  A节点的parent节点需要重新设置left / right;
 *  A节点的left，right节点需要重新设置parent节点；将parent指向B节点；

正因为第一种方式删除比较麻烦，所以一般选用第二种方式删除；

#### **remove代码** ####

public boolean removeVal(int val){
        
          Node target = findNode(val,root);
          if(target == null)return false;
          remove(target);
          return true;
        }
        
        Node  findNode(int val,Node node){
        
            if(node == null)return null;
            if(node.data == val)return node;
            else if(node.data > val)return findNode(val,node.left);
            else return findNode(val,node.right);
        }
        
        void remove(Node node){
        
            if(node.left == null && node.right == null){
        //叶子节点
                if(node == root)
                    root = null;
                else
                    removeLeaf(node);
            }else{
        //非叶子节点
                 if( node.right == null){
        //存在左节点
                     if(node.parent.left == node)node.parent.left = node.left;
                     else node.parent.right = node.left;
                     node.left.parent = node.parent;
                }else if(node.left == null ){
        //存在右节点
                    if(node.parent.left == node) node.parent.left = node.right;
                    else node.parent.right = node.right;
                    node.right.parent = node.parent;
                }else{
        //存在左右子节点
                     Node replaceNode = leftMaxNode(node.left);//找左边最大值
    //                 Node replaceNode = rightMinNode(node.right);//找右边最小值
                     node.data = replaceNode.data;
                     remove(replaceNode);
                }
            }
        }
    
        void removeLeaf(Node node){
        
            Node parent   = node.parent;
            if(node == parent.left)
                parent.left = null;
            else
                parent.right = null;
        }
    
    
        Node  leftMaxNode(Node node){
        
            if(node.right == null)return node;
            return leftMaxNode(node.right);
        }
    
        Node rightMinNode(Node node){
        
            if(node.left == null) return node;
            return rightMinNode(node.left);
        }

测试：

public void addList(int[] a){
        
            for (int i = 0; i < a.length; i++) {
        
                addVal(a[i]);
            }
        }
    
    
        void print(List<Node> nodes){
        
            if(nodes.size() == 0)return;
            List<Node> children = new ArrayList<>();
            System.out.println("\n");
            for (Node node : nodes) {
        
                if(node.left != null)children.add(node.left);
                if(node.right != null)children.add(node.right);
                System.out.print(node.data+"[parent="+(node.parent == null ? null : node.parent.data)+"],");
            }
            print(children);
        }
    
        public void print(){
        
            List<Node> nodes = new ArrayList<>();
            nodes.add(root);
            print(nodes);
        }
    
        @Test
        public void test(){
        
            System.out.println("+++++++++++++++ADD TEST+++++++++++++");
            addList(new int[]{
        5,2,7,1,4,6,9,3,11});
            print();
            System.out.println("\n+++++++++++++++REMOVE TEST+++++++++++++");
            removeVal(5);//root 节点
            print();
        }

可以很明显的看到这种结构是有缺陷的，如果按顺序添加：1 -> 10；那么二叉搜索树会退化成链表；1 -> 2 -> 3 …->10;这个时候的搜索效率明显不行了，因此为了使二叉搜索树的结构更稳定，就要求二叉树必须维持平衡。下篇文章主要讲AVL树，这是一种自平衡树.

[b9c1572375f3486c8a734220f05c0437.png_pic_center]: https://img-blog.csdnimg.cn/b9c1572375f3486c8a734220f05c0437.png#pic_center
[79ca1e4eb90b4e489e98f61dbe75366d.png_pic_center]: https://img-blog.csdnimg.cn/79ca1e4eb90b4e489e98f61dbe75366d.png#pic_center
[c42539d170904431b85a4c5623c1b04e.png_pic_center]: https://img-blog.csdnimg.cn/c42539d170904431b85a4c5623c1b04e.png#pic_center
[4088cf1604a64950a466dc8dbe37e620.png_pic_center]: https://img-blog.csdnimg.cn/4088cf1604a64950a466dc8dbe37e620.png#pic_center
[4dc3c335d56d4268ad6742e7a017d68d.png_pic_center]: https://img-blog.csdnimg.cn/4dc3c335d56d4268ad6742e7a017d68d.png#pic_center
[85ef935338e347efbc99a7934702d20b.png_pic_center]: https://img-blog.csdnimg.cn/85ef935338e347efbc99a7934702d20b.png#pic_center
[0ac91f08a6fb4518a78a66cd429eb895.png_pic_center]: https://img-blog.csdnimg.cn/0ac91f08a6fb4518a78a66cd429eb895.png#pic_center