一、简介

二叉排序树亦称二叉查找树，是树形数据结构的一种，在一般情况下，二叉排序树的查找效率要高于普通链表，它要么是一棵空树，要么具有以下性质：

  • 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树分别为二叉排序树。
  • 下面是一棵标准的二叉排序树

image-20210205180344323

二、二叉排序树的生成与节点插入

2.1、生成

1、创建Node类和Tree类

创建一个Node类作为二叉排序树的节点类，这里省略getter、setter和toString方法

1
2
3
4
5
6
7
8
public class Node {
    // 节点的值
    int data;
    // 当前节点的左子节点
    Node left;
    // 当前节点的右子节点
    Node right;
}

创建一个Tree类，这个类包含一个Node类型的root属性。

1
2
3
4
public class Tree {
    // 当前树的根节点
    Node root;
}

2、生成思路

既可以在创建二叉树对象时直接使用有参构造函数传入根节点对象，也可以在添加节点时才插入root节点

注：当一棵树root节点为空时，第一个插入该树的节点就是根节点。

2、节点插入

1、思路

在Tree类中添加一个addNode方法，如果当前树的根节点为空，那么将要添加到二叉排序树的节点设置为根节点，否则就调用root节点对象的add方法，在root对象的add方法中：

  • 如果传入要添加的节点node为空，那么直接返回，不做添加。
  • 如果传入要添加的节点node的数值小于当前节点的数值，那么进行判断，如果当前节点的左子树为空，那么直接让当前节点的左子树为要添加的节点node。否则向左进行递归添加，判断待添加节点node的数据与当前左子节点数据的关系，重复以上操作。
  • 如果传入要添加的节点node的数值大于等于当前节点的数值，这种情况需要尽量避免，这个时候进行判断，如果当前节点右子树为空，那么令当前节点右子树等于要添加的节点node。否则向右进行递归添加，判断待添加节点node的数据与当前右子节点数据的关系，重复以上操作。

2、插入节点–Tree

1
2
3
4
5
6
7
public void addNode(Node node) { 
    if(this.root == null) { 
        this.root = node; 
    } else { 
        this.root.add(node); 
    } 
}

3、节点的比较与插入–Node

比较节点树的静态方法如下

1
2
3
public static boolean compare(Node node1,Node node2) { 
    return node1.data > node2.data; 
}

Node类中插入节点的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void add(Node node) { 
    if(node == null) { 
        return; 
    } 
    if(compare(this,node)) { 
        if(this.left == null) { 
            this.left = node; 
        } else { 
            this.left.add(node); 
        } 
    } else { 
        if(this.right == null) { 
            this.right = node; 
        } else { 
            this.right.add(node); 
        } 
    } 
}

三、二叉树的前中后序遍历

前序遍历的顺序：根节点–左子节点–右子节点

中序遍历的顺序：左子节点–根节点–右子节点

后序遍历的顺序：左子节点–右子节点–根节点

3.1、递归实现

1、前序遍历

先输出当前节点，然后判断当前节点的左子树是否为空，如果不为空，就向左递归进行前序遍历。然后判断当前节点的右子树是否为空，若不为空，向右递归进行前序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Tree类 
public void preOrder() { 
    if(this.root != null) { 
        this.root.preOrder(); 
    } else { 
        System.out.println("二叉树为空，无法遍历！"); 
    } 
} 
 
//Node类 
public void preOrder() { 
    System.out.println(this); 
    if(this.getLeft() != null) { 
        this.getLeft().preOrder(); 
    } 
    if(this.getRight() != null) { 
        this.getRight().preOrder(); 
    } 
}

2、中序遍历

先判断当前节点左子树是否为空，若不为空，向左递归进行中序遍历，然后输出当前节点；最后判断当前节点的右子树是否为空，若不为空，向右递归进行中序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Tree类 
public void infixOrder() { 
    if(this.root != null) { 
        this.root.infixOrder(); 
    } else { 
        System.out.println("二叉树为空，无法遍历！"); 
    } 
} 
 
//Node类 
public void infixOrder() { 
    if(this.getLeft() != null) { 
        this.getLeft().infixOrder(); 
    } 
    System.out.println(this); 
    if(this.getRight() != null) { 
        this.getRight().infixOrder(); 
    } 
}

3、后序遍历

先判断当前节点左子树是否为空，若不为空，向左递归进行后序遍历；然后判断当前节点的右子树是否为空，若不为空，向右递归进行后序遍历。最后输出当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Tree类 
public void postOrder() { 
    if(this.root != null) { 
        this.root.postOrder(); 
    } else { 
        System.out.println("二叉树为空，无法遍历！"); 
    } 
} 
 
//Node类 
public void postOrder() { 
    if(this.getLeft() != null) { 
        this.getLeft().postOrder(); 
    } 
    if(this.getRight() != null) { 
        this.getRight().postOrder(); 
    } 
    System.out.println(this); 
}

3.2、非递归实现

我们需要使用到栈这一数据结构来解决问题

1、前序遍历

如果当前节点不为空，先输出当前节点信息，然后将该节点压入栈，并将指针移动到当前节点的左子节点，此时如果该左子树为空，就退出循环，此时如果栈不为空，就弹出栈顶数据，将指针移动到当前结点右子树，循环，直到栈空或者当前节点为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void preOrder(Node node) { 
    Stack<Node> nodeStack = new Stack<>(); 
    while(node != null || !nodeStack.empty()) { 
        while(node != null) { 
            System.out.println(node); 
            nodeStack.push(node); 
            node = node.getLeft(); 
        } 
        if(!nodeStack.empty()) { 
            node = nodeStack.pop(); 
            node = node.getRight(); 
        } 
    } 
}

2、中序遍历

如果当前节点不为空，将当前节点压入栈中，然后将指针指向当前节点左子树，直到左子树为空，此时栈不为空，将栈顶元素弹出并输出后，将指针移动到当前结点右子树，循环，直到栈空或者当前节点为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void midOrder(Node node) { 
    Stack<Node> nodeStack = new Stack<>(); 
    while(node != null || !nodeStack.empty()) { 
        while(node != null) { 
            nodeStack.push(node); 
            node = node.getLeft(); 
        } 
        if(!nodeStack.empty()) { 
            node = nodeStack.pop(); 
            System.out.println(node); 
            node = node.getRight(); 
        } 
    } 
}

3、后序遍历

需要利用到一个辅助栈用于输出结果，由于栈具有先进后出的特点，而后序遍历的顺序是左右根，所以压入栈顺序为根、右、左。最后使用辅助栈输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void postOrder(Node node) { 
    if(node == null) { 
        System.out.println("要遍历的二叉树为空！"); 
        return; 
    } 
    Stack<Node> stack = new Stack<>(); 
    //辅助栈 
    Stack<Node> assistStack = new Stack<>(); 
    while(node != null || !stack.isEmpty()) { 
        while(node != null) { 
            stack.push(node); 
            assistStack.push(node); 
            node = node.getRight(); 
        } 
        if(!stack.isEmpty()) { 
            node = stack.pop(); 
            node = node.getLeft(); 
        } 
    } 
    while(!assistStack.isEmpty()) { 
        System.out.println(assistStack.pop()); 
    } 
}

四、二叉排序树节点的删除

二叉排序树中的节点可以分为以下三种：

  • 叶子节点
  • 有一棵子树的节点
  • 有两棵子树的节点

我们需要判断待删除节点为什么类型，然后根据节点类型进行删除操作。

4.1、编写用于搜索待删除节点和待删除节点父节点的方法

1、搜索待删除节点的方法

搜索待删除节点，首先判断当前二叉排序树是否为空，若为空，直接返回，否则调用当前二叉排序树根节点的search方法

  • 如果当前传入的数据data的值刚好等于当前节点的data值，那么当前节点就是待删除节点，直接返回即可

  • 如果当前传入的数据data的值小于当前节点的值且当前节点的左子树为空，证明当前二叉排序树中没有要删除的节点；如果当前传入数据data值小于当前节点值且当前节点左子树不为空，那么调用当前节点左子树的search方法，向左递归查询。

  • 同理，如果当前传入的数据data值大于当前节点值且当前节点右子树为空，证明当前二叉排序树没有要删除节点，此刻只能返回null；如果当前传入数据data值大于当前节点且当前节点右子树不为空，那么调用当前右子树的search方法，向右递归查询。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*** 
 * 根据节点的data数据搜索Node节点 
 * @param data 目标节点的data值 
 * @return 如果找到符合条件的node节点，那么返回该node节点 
 *         否则返回null 
 */ 
public Node search(int data) { 
    if(data == this.data) { 
        return this; 
    } else if(data < this.data) { 
        if(this.left == null) { 
            return null; 
        } 
        return this.left.search(data); 
    } else { 
        if(this.right == null) { 
            return null; 
        } 
        return this.right.search(data); 
    } 
}

2、搜索待删除节点父节点的方法

搜索待删除节点的父节点的方法，同理先判断当前二叉排序树的根节点是否为空，若为空，返回null，否则调用当前二叉排序树的根节点的搜索待删除节点父节点（searchParent）的方法。

  • 如果当前节点的左子树不为空且当前节点左子树的data值等于用户传入的要检索的data值或者当前节点右子树不为空且当前节点右子树的data值等于用户传入的要检索的data值，那么证明当前节点就是待检索节点，返回当前节点。

  • 如果传入的data值小于当前节点值且当前左子树不为空，那么调用当前左子节点的searchParent的方法。

  • 同理，如果传入data值大于等于当前节点的data值且当前节点右子树不为空，那么调用当前节点右子节点的searchParent方法。

  • 如果程序走到此处，证明没有找到待删除数据的父节点，此时返回null。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*** 
 * 查找要删除节点的父节点 
 * @param data 要删除的节点的数据 
 * @return 待删除节点的父节点 
 */ 
public Node searchParent(int data) { 
    if((this.left != null && this.left.data == data) || (this.right != null && this.right.data == data)) { 
        return this; 
    } else { 
        //如果要查找的值小于当前节点值，且当前节点左子节点不为空 
        //递归向左 
        if(data < this.data && this.left != null) { 
            return this.left.searchParent(data); 
        } else if(data >= this.data && this.right != null) { 
            return this.right.searchParent(data); 
        } else { 
            return null; 
        } 
    } 
}

4.2、删除叶子节点

对于叶子节点，我们需要先找到待删除节点target和待删除节点的父节点parent，然后判断待删除叶子节点是其父节点的左子树还是右子树，如果为左子树，那么令parent.left = null，否则让parent.right = null。

  • 二叉排序树中判断待删除节点是否为叶子节点的静态方法与Node类中判断传入节点为当前左子树/右子树的方法
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
/*** 
 * 判断node节点是否为叶子节点 
 * @param node 
 * @return 
 */ 
public static boolean isLeaf(Node node) { 
    return node.left == null && node.right == null; 
} 

/*** 
 * 判断传入节点是否为当前节点左子节点的方法 
 * @param target 
 * @return 
 */ 
public boolean isLeft(Node target) { 
    return this.left != null && this.left.data == target.data; 
} 

/*** 
 * 判断传入节点是否为当前节点右子节点的方法 
 * @param target 
 * @return 
 */ 
public boolean isRight(Node target) { 
    return this.right != null && this.right.data == target.data; 
}

4.3、删除有一棵子树的节点

对于有一棵子树的节点的删除，我们需要找到待删除节点和待删除节点的父节点，然后判断两个条件：1（待删除节点是其父节点的左子树还是右子树）、2（待删除节点有左子树还是右子树）

  • 如果待删除节点有左子树且为其父节点的左子树：此时让待删除节点的父节点的左子树等于待删除节点的左子树，即parent.left = target.left。

  • 如果待删除节点有左子树且为其父节点的右子树：此时根据二叉排序树的性质，待删除节点的左子树的数据要全部大于（等于）其父节点的数据，所以令待删除节点父节点的右子树等于待删除节点的左子树，即parent.right = target.left。

  • 如果待删除节点有右子树且为其父节点的左子树：此时让parent.left = target.right

  • 如果待删除节点有右子树且为其父节点的右子树，此时让parent.right = target.right

  • Node类中判断传入节点是否为当前节点左/右子树的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** 
 * 判断传入节点是否为当前节点左子节点的方法 
 * @param target 
 * @return 
 */ 
public boolean isLeft(Node target) { 
    return this.left != null && this.left.data == target.data; 
} 

/*** 
 * 判断传入节点是否为当前节点右子节点的方法 
 * @param target 
 * @return 
 */ 
public boolean isRight(Node target) { 
    return this.right != null && this.right.data == target.data; 
}

4.4、删除有两棵树的节点

对于有两棵子树的节点的删除：需要先取到待删除节点的右子树的最小节点的值，然后将数值最小的节点删除，最后将前面取到的最小节点的值赋值给待删除节点。

  • 获取待删除节点右子树中最小节点的值并删除最小节点的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** 
 * 1 返回以node为根节点的二叉排序树的最小节点的值 
 * 2 删除以node为根节点的二叉排序树的最小节点 
 * @param node 传入的节点（二叉排序树的根节点） 
 * @return 返回的以Node为根节点的二叉排序树的根节点的值 
 */ 
public int delTreeMin(Node node) { 
    Node target = node; 
    //循环的查找左节点，就能找到最小值 
    while(target.left != null) { 
        target = target.left; 
    } 
    //此时循环结束后，target指向最小节点 
    //删除最小节点 
    delNode(target.data); 
    return target.data; 
}
  • 判断当前节点是否有两棵子树的方法
1
2
3
4
5
6
7
8
/*** 
 * 判断传入节点是否有左右子树的方法 
 * @param node 
 * @return 
 */ 
public static boolean hasTwoSon(Node node) { 
    return node.left != null && node.right != null; 
}

4.5、二叉排序树中根据节点数据删除节点的方法

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
/*** 
 * 根据data删除节点 
 * @param data 要删除的节点的data 
 */ 
public void delNode(int data) { 
    if(root == null) { 
        return; 
    } else { 
        //1 先找到要删除的节点target 
        Node target = search(data); 
        //1.1 如果要删除的节点不存在，直接返回 
        if(target == null) { 
            return; 
        } 
        //1.2 如果当前树只有一个节点，且为待删除节点，那么直接置空 
        if(root.left == null && root.right == null) { 
            root = null; 
            return; 
        } 
        //2 去找到target的父节点 
        Node parent = searchParent(data); 
        //2.1 如果要删除的节点是叶子节点 
        if(isLeaf(target)) { 
            //a 判断target是父节点的左子节点还是有子节点 
            if(parent.isLeft(target)) { 
                //如果是左子节点 
                parent.left = null; 
            } else if(parent.isRight(target)) { 
                //如果是右子节点 
                parent.right = null; 
            } 
        } else if(hasTwoSon(target)) { 
            //2.2 如果要删除的节点有左右子树 
            //删除右子树最小节点，同时将最小节点的值取出来 
            int minData = delTreeMin(target.right); 
            target.data = minData; 
        } else { 
            //2.3 删除只有一棵子树的节点 
            //如果待删除节点有左子节点 
            if(target.left != null) { 
                //如果target是parent的左子节点 
                if(parent.isLeft(target)) { 
                    parent.left = target.left; 
                } else { 
                    //说明target是parent的右子节点 
                    parent.right = target.left; 
                } 
            } else { 
                //待删除节点有右子节点 
                //如果target是parent的左节点 
                if(parent.isLeft(target)) { 
                    parent.left = target.right; 
                } else { 
                    parent.right = target.right; 
                } 
            } 
        } 
    } 
}

五、使用递归获取二叉树深度

1
2
3
4
5
6
7
8
9
10
/*** 
 * 递归获取二叉树深度的方法 
 * 如果根为空：返回0 
 * 否则分别递归深入左右节点，返回深度 
 * @param root 二叉树的根节点 
 * @return 二叉树深度 
 */ 
public static int getTreeDepth(Node root) { 
    return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right))); 
}

六、测试

6.1、测试二叉排序树的生成和插入

1
2
3
4
5
6
7
8
9
Tree tree = new Tree(null);
int[] arr = {7,8,19,-1,26,100,777,-1012,222,18};
for (int i = 0; i < arr.length; i++) {
    int data = arr[i];
    Node node = new Node(data);
    tree.addNode(node);
}
System.out.println("tree:");
Tree.show(tree.root);

结果

image-20210205232120723

6.2、测试二叉排序树的删除

1、删除叶子节点

1
2
3
4
5
System.out.println("---------------------------------删除叶子节点-1012，删除前："); 
Tree.show(tree.root); 
tree.delNode(-1012); 
System.out.println("---------------------------------删除叶子节点-1012，删除后："); 
Tree.show(tree.root);

删除前：

image-20210205232357649

删除后：

image-20210205232417944

2、删除有一棵子树的节点

1
2
3
4
5
System.out.println("---------------------------------删除有一棵树的节点-1，删除前："); 
Tree.show(tree.root); 
tree.delNode(-1); 
System.out.println("---------------------------------删除有一棵树的节点-1，删除后："); 
Tree.show(tree.root);

删除前：

image-20210205232621385

删除后：

image-20210205232635923

3、删除有两棵子树的节点

1
2
3
4
5
System.out.println("---------------------------------删除有两棵子树的节点7，删除前："); 
Tree.show(tree.root); 
tree.delNode(7); 
System.out.println("---------------------------------删除有两棵子树的节点7，删除后："); 
Tree.show(tree.root);

删除前：

image-20210205232820859

删除后：

image-20210205232834775