二叉查找树

发表于   |  

二叉查找树代码实现，包括遍历的递归和非递归实现。

二叉查找树又叫二叉搜索树，它是一棵二叉树，它的根节点的左孩子的值小于其根节点的值，根节点的右孩子的值大于根节点的值，并且根节点的左孩子和由孩子也是二叉查找树。可见其定义具有递归性质，二叉搜索树的操作基本上可以使用递归来完成。

bst

这就是一棵二叉搜索树。

二叉搜索树的期望高度为$O(logN)$，所以它的搜索，插入，删除等操作的时间复杂度是$O(logN)$，但也可能会出现坏的情况，比如在构造二叉搜索树的时候依次插入1,2,3,4,5那么，二叉搜索树就退化成一个链表了。

二叉搜索树的构造

二叉搜索树的节点需要保存值，父节点指针，左孩子和由孩子的指针。值一般会是一个对象类型，该对象类型要实现比较的功能，在Java中，就是要实现Comparable接口。这里使用最简单的int整型。

1
2
3
4
5
6
7
8
9
10
private static class Node {
   private Node parent;
   private Node left;
   private Node right;
   private int value;

   public Node(int value) {
       this.value = value;
   }
}

插入节点：如果二叉搜索树为空，插入的节点就当做根节点，如果二叉搜索已经包含了要插入的节点那就直接返回，否则，就从根节点开始往下找，找到适合的位置插入。还有一种递归的方式就是如果根节点为空，就把要插入的节点返回，否则比较根节点和要插入的值，如果小于根节点的值，就插入根节点的左孩子，否则插入到右孩子。

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
public void insert(int value) {

   Node node = new Node(value);
   if (isEmpty()) {
       root = node;
       return;
   }

   if (contains(value)) {
       return;
   }

   Node p = null;
   Node cur = root;
   while (cur != null) {
       p = cur;
       if (cur.value < value) {
           cur = cur.right;
       } else {
           cur = cur.left;
       }
   }
   node.parent = p;
   if (p.value < value) {
       p.right = node;
   } else {
       p.left = node;
   }
}

节点的删除

节点的删除分三种情况：

  1. 该节点没有左子树和右子树
  2. 该节点只有左子树
  3. 该节点只有右子树

第一种情况，直接删除节点即可。

第二种情况，找到左子树的最大值节点，交换该最大值节点的值，然后删除最大值节点。

第三种情况，找到右子树的最小值节点，交换最小值节点的值，然后删除最小值节点。

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
public void remove(int value) {
   Node val = find(value);
   removeNode(val);
}

private void removeNode(Node val) {
   if (val == null) {
       throw new RuntimeException("SBT is not contain " + val.value);
   }
   if (val.left == null && val.right == null) {
       if (val.parent == root) {
           root = null;
       } else if (val.parent.left == val){
           val.parent.left = null;
       } else {
           val.parent.right = null;
       }
   } else if (val.left != null) {
       Node max = maxNode(val.left);
       swap(max, val);
       removeNode(max);
   } else {
       Node min = minNode(val.right);
       swap(min, val);
       removeNode(min);
   }
}

private void swap(Node n1, Node n2) {
   int tmp = n1.value;
   n1.value = n2.value;
   n2.value = tmp;
}

节点的查找

二叉搜索树的查找，即判断二叉搜索树是否包含给定的值，只要从根节点开始往下比较即可。递归的思路就是如果根节点不是要找的值就根据根节点和要找的值的大小来递归调用在子树中查找。

找最小值就是一直最左下方的那个值，最大值就是最右下方的那个值。

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
public boolean contains(int value) {
   Node cur = root;
   while (cur != null && cur.value != value) {
       if (cur.value < value) {
           cur = cur.right;
       } else {
           cur = cur.left;
       }
   }
   return cur != null;
}

public int max() {
   if (isEmpty()) {
       throw new RuntimeException("BST is empty.");
   }
   return maxNode(root).value;
}

private Node maxNode(Node root) {
   if (root == null) {
       return null;
   }
   Node cur = root;
   while (cur.right != null) {
       cur = cur.right;
   }
   return cur;
}

public int min() {
   if (isEmpty()) {
       throw new RuntimeException("BST is empty");
   }
   Node min = minNode(root);
   return min.value;
}

private Node minNode(Node root) {
   if (root == null) {
       return null;
   }
   Node cur = root;
   while (cur.left != null) {
       cur = cur.left;
   }
   return cur;
}

寻找节点的前驱节点和后继节点

前驱和后继节点就是在中序遍历序列中，与节点紧邻的前一个节点和后一个节点。

前驱：如果节点有左子树，那么前驱就是左子树中的最大节点，否则就要寻找离该节点最近的那个节点，使得该节点位于那个节点的左子树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int predecessor(int value) {
   if (!contains(value)) {
       throw new RuntimeException("BST not contains " + value);
   }
   Node val = find(value);
   if (val.left != null) {
       return maxNode(val.left).value;
   }

   Node p = val.parent;
   while (p != null && p.left == val) {
       val = p;
       p = val.parent;
   }
   if (p == null) {
       return Integer.MIN_VALUE; // 不存在 该如何处理 ？抛异常？
   } else {
       return p.value;
   }
}

后继：后继和前驱类似，如果节点有右子树，那么前驱就是右子树中的最小节点，否则就要寻找离该节点最近的那个节点，使得该节点位于那个节点的右子树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int successor(int value) {
   if (!contains(value)) {
       throw new RuntimeException("BST is not contain " + value);
   }
   Node val = find(value);
   if (val.right != null) {
       return minNode(val.right).value;
   }

   Node p = val.parent;
   while (p != null && p.right == val) {
       val = p;
       p = val.parent;
   }
   if (p == null) {
       return Integer.MAX_VALUE; // 不存在 该如何处理 ？抛异常？
   } else {
       return p.value;
   }
}

二叉搜索树的遍历

前序遍历

前序遍历：就是先处理根节点，再分别递归处理左子树中的节点和右子树中的节点。

递归的方式很简单，这里主要讲一下如何实现非递归方式。

非递归这里有两种方式：

  • 首先一直向左下方遍历，即先一直处理左孩子并添加到栈中，直到左孩子为空，然后查看栈顶元素（就算当前节点的父节点）的右孩子是否就是当前节点，如果是就弹出栈顶元素作为当前节点，继续判断栈顶元素的右孩子是否就是当前节点，直到栈为空，或者当前节点不是栈顶元素的右孩子，那么就开始处理栈顶元素的右孩子。
  • 先将根节点添加到栈中，然后不断弹出栈顶元素，处理该元素，然后分别将栈的右孩子和左孩子压人栈中，这样之后弹出的就先是左孩子然后才是右孩子。

显然，第二种方式更加的简单。

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
public List<Integer> preorder() {
// return preOrder(root);
   return preOrderNonRecursive();
}

private List<Integer> preOrder(Node root) {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   order.add(root.value);
   order.addAll(preOrder(root.left));
   order.addAll(preOrder(root.right));
   return order;
}

private List<Integer> preOrderNonRecursive() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   order.add(root.value);
   Node cur = root.left;
   Node p;
   while (!stack.isEmpty()) {
       while (cur != null) {
           order.add(cur.value);
           stack.push(cur);
           cur = cur.left;
       }
       while (!stack.isEmpty()) {
           p = cur;
           cur = stack.peek().right;
           if (p == cur) {
               cur = stack.pop();
           } else {
               break;
           }
       }
   }
   return order;
}

private List<Integer> preOrderNonRecursive1() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   Node cur;
   while (!stack.isEmpty()) {
       cur = stack.pop();
       order.add(cur.value);
       if (cur.right != null) {
           stack.push(cur.right);
       }
       if (cur.left != null) {
           stack.push(cur.left);
       }
   }
   return order;
}

中序遍历

中序遍历：就是先递归处理左子树，再分处理根节点，最后递归处理右子树中的节点。

递归的方式很简单，这里主要讲一下如何实现非递归方式。

非递归的方式就是先一直将节点的左孩子压入栈中知道左孩子为空，这时候弹出栈顶元素，处理该元素，然后如果其有右孩子就将其右孩子压入栈，然后继续处理左孩子，如果没有右孩子，则弹出栈顶元素。以此往复。

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
public List<Integer> inorder() {
   return inOrder(root);
}

private List<Integer> inOrder(Node root) {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   order.addAll(inOrder(root.left));
   order.add(root.value);
   order.addAll(inOrder(root.right));
   return order;
}

private List<Integer> inOrderNonRecursive() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   Node cur = root;
   while (cur != null || !stack.isEmpty()) {
       while (cur != null) {
           stack.push(cur);
           cur = cur.left;
       }
       if (!stack.isEmpty()) {
           cur = stack.pop();
           order.add(cur.value);
           cur = cur.right;
       }
   }
   return order;
}

后序遍历

后序遍历：就是先分别递归处理左子树中的节点和右子树中的节点，再处理根节点。

递归的方式很简单，这里主要讲一下如何实现非递归方式。

非递归的方式主要难点是在判断节点的右孩子是否已经处理过了。这里在处理完一个节点时，先判断该节点是否是父节点的右孩子，如果是，就不再处理父节点的右孩子，直接处理父节点，如果不是，再处理父节点的右孩子。

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
public List<Integer> postorder() {
   return postOrder(root);
}

private List<Integer> postOrder(Node root) {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   order.addAll(postOrder(root.left));
   order.addAll(postOrder(root.right));
   order.add(root.value);
   return order;
}

private List<Integer> postOrderNonRecursive() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   Node cur = root;
   stack.push(cur);
   cur = root.left;
   Node p;
   while (!stack.isEmpty()) {
       while (cur != null) {
           stack.add(cur);
           cur = cur.left;
       }
       while (!stack.isEmpty()) {
           p = cur;
           cur = stack.peek().right;
           if (p == cur) {
               cur = stack.pop();
               order.add(cur.value);
           } else {
               break;
           }
       }
   }

   return order;
}

完成代码见Githug