二叉查找树

定义

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

二叉查找树的中序遍历按照升序进行排序。

定义节点类：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 结点类
 */
private class Node {
    int data;
    Node right;
    Node left;

    Node(int data) {
        this.data = data;
    }
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 查找结点
 *
 * @param data
 * @return
 */
public Node search(int data) {
    Node r = root;
    while (r != null) {
        if (r.data == data) {
            System.out.println("找到该节点");
            return r;
        } else if (r.data > data) {
            r = r.left;
        } else {
            r = r.right;
        }
    }
    System.out.println("未找到该节点");
    return null;
}

插入

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
/**
 * 插入结点
 *
 * @param data
 * @return
 */
public boolean insert(int data) {
    Node targetNode = new Node(data);
    if (root == null) {
        root = targetNode;
        return true;
    }
    Node r = root;
    Node t = r;
    while (r != null) {
        t = r;
        if (r.data == data) {
            System.out.println("二叉查找树中已存在此节点！");
            return false;
        } else if (r.data > data) {
            r = r.left;
        } else {
            r = r.right;
        }
    }
    if (t.data > data) {
        t.left = targetNode;
    } else {
        t.right = targetNode;
    }
    return true;
}

删除

删除二叉查找树中，值得注意的是，当目标节点有两个子节点时，可以选择左子树最大的节点代替，或者选择右子树最小的节点来代替，以保证二叉查找树的性质，这里选择右子树最小的节点代替。需要注意当目标节点的右子树没有左子树的情况。

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
/**
 * 删除结点
 *
 * @param data
 * @return
 */
public boolean delete(int data) {
    //判断该节点是否存在
    Node targetNode = root;
    Node parentNode = new Node(data);
    //判断待删除结点是否存在
    while (targetNode.data != data) {
        parentNode = targetNode;
        if (data > targetNode.data) {
            targetNode = targetNode.right;
        } else {
            targetNode = targetNode.left;
        }
        if (targetNode == null) {
            // 没有找到待删除结点
            return false;
        }
    }
    //待删除结点没有子节点
    if (targetNode.left == null && targetNode.right == null) {
        if (targetNode == root) {
            root = null;
            return true;
        } else {
            if (parentNode.left == targetNode) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
        }
    }
    //待删除结点有一个子结点（右）
    else if (targetNode.left == null) {
        if (targetNode == root) {
            root = root.right;
        } else {
            if (parentNode.left == targetNode) {
                parentNode.left = targetNode.right;
            } else {
                parentNode.right = targetNode.right;
            }
        }
    }
    //待删除结点有一个子结点（左）
    else if (targetNode.right == null) {
        if (targetNode == root) {
            root = root.left;
        } else {
            if (parentNode.left == targetNode) {
                parentNode.left = targetNode.left;
            } else {
                parentNode.right = targetNode.left;
            }
        }
    }
    //待删除结点有两个子结点
    else {
        //待删除结点的后继结点的父结点
        Node successParentNode = targetNode;
        //待删除结点的后继结点
        Node successNode = targetNode.right;
        while (successNode.left != null) {
            successParentNode = successNode;
            successNode = successNode.left;
        }
        //把后继结点复制到待删除结点位置
        targetNode.data = successNode.data;
        //删除后继结点
        if (successParentNode.right == successNode) {
            successParentNode.right = successNode.right;
        } else {
            successParentNode.left = successNode.right;
        }
    }
    //待删除结点有两个子结点
    return true;
}

参考文章：