JavaSE_Java复习基本搜索树的实现

C++实现及思路

class Node{
    public Node left;
    public Node right;
    public int val;
    public Node(int _val){
        this.val=_val;
    }
}

class BinarySearchTree {
    public Node root;

    private  void _inorder(Node node){
        if(node==null){
            return;
        }
        _inorder(node.left);
        System.out.print(node.val+" ");
        _inorder(node.right);
    }
    public void inorder(){
        _inorder(root);
    }
    public Node searchNode(int val){
        //二叉搜索树查找
        Node node=root;
        while(node!=null){
            if(node.val<val){
                node=node.right;
            }
            else if(node.val>val){
                node=node.left;
            }
            else{
                return node;
            }
        }
        return null;
    }

    public boolean insertNode(int val){
        Node prev=null; Node node=root;
        while(node!=null){
            prev=node;
            if(node.val>val){
                node=node.left;
            }
            else if(node.val<val){
                node=node.right;
            }
            else{
                //重复元素
                return false;
            }
        }
        node=new Node(val);
        if(prev==null){
            //开始树为空
            root=node;
        }
        else{
            //树不为空
            if(prev.val>val){
                prev.left=node;
            }
            else{
                prev.right=node;
            }
        }
        return true;
    }

    //二叉搜索树的删除
    private void removeNode(Node node,Node parent){
        if(node.left==null){
            if(node==root){
                root=node.right;
            }
            else if(node==parent.left){
                parent.left=node.right;
            }
            else{
                parent.right=node.right;
            }
        }
        else if(node.right==null){
            if(node==root){
                root=node.left;
            }
            else if(node==parent.left){
                parent.left=node.left;
            }
            else{
                parent.right=node.left;
            }
        }
        else{
            //左右都有节点，找左树最大值或找右树最小值
            //这里选择找左树的最大
            Node targetParent=node;
            Node target=node.right;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            node.val=target.val;
            removeNode(target,targetParent);
            /*
              if(targetParent.left==target){
                  targetParent.left=target.right;
              }
              else if(targetParent==target){
                  targetParent.right=target.right;
              }
             */
        }
    }

    public boolean remove(int val){
        Node node=root;
        Node parent=null;
        while(node!=null){
            parent=node;
            if(node.val<val){
                node=node.right;
            }
            else if(node.val>val){
                node=node.left;
            }
            else{
                removeNode(node,parent);
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

测试：

public class TestBinarySearchTree {
    public static void main(String[] args) {
        int[]array={9,8,7,5,4,2,1};
        BinarySearchTree binarySearchTree=new BinarySearchTree();
        for(int num:array){
            binarySearchTree.insertNode(num);
        }
        binarySearchTree.inorder();
        System.out.println();
        for(int num:array){
            binarySearchTree.remove(num);
            binarySearchTree.inorder();
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16