树

[yifanzheng]

树基础

• 二叉树遍历
• 二分查找树

[yifanzheng]

二叉树遍历

前序遍历

private void preOrder(Node root) {
    if (root == null) return;
    System.out.println(root);// 此处为伪代码，表示打印 root 节点
    preOrder(root -> left);
    preOrder(root -> right);
}

中序遍历

private void inOrder(Node root) {
    if (root == null) return;
    preOrder(root -> left);
    System.out.println(root);// 此处为伪代码，表示打印 root 节点
    preOrder(root -> right);
}

后序遍历

private void postOrder(Node root) {
    if (root == null) return;
    preOrder(root -> left);
    preOrder(root -> right);
    System.out.println(root);// 此处为伪代码，表示打印 root 节点
}

[yifanzheng]

二分查找树

二分查找树规定，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树是为了实现快速查找而生的，并且它还支持快速插入、删除一个数据。

实现二分查找树

public class BinarySearchTree {

    private Node root;
    private int count;

    public BinarySearchTree() {
        this.root = null;
        this.count = 0;
    }

    /**
     * 查找树中指定值的节点
     *
     * @param data data
     * @return Node
     */
    public Node search(int data) {
        Node temp = root;
        while (temp != null) {
            if (temp.data == data) {
                return temp;
            } else if (temp.data > data) {
                temp = temp.left;
            } else {// temp.data < data
                temp = temp.right;
            }
        }
        return null;
    }

    /**
     * 向树中添加节点
     *
     * @param data data
     */
    public void add(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }
        Node temp = root;
        while (true) {
            if (temp.data > data) {
                if (temp.left == null) {
                    temp.left = new Node(data);
                    return;
                }
                temp = temp.left;
            } else { // temp.data <= data
                if (temp.right == null) {
                    temp.right = new Node(data);
                    return;
                }
                temp = temp.right;
            }
        }
    }

    public void remove(int data) {
        if (root == null) {
            return;
        }
        root = remove(root, data);
    }

    /**
     * 移除树中最大值的节点
     */
    public void removeMax() {
        if (root == null) {
            return;
        }
        root = removeMax(root);
    }

    /**
     * 移除树中最小值的节点
     */
    public void removeMin() {
        if (root == null) {
            return;
        }
        root = removeMin(root);
    }

    /**
     * 查找树中值最大的节点
     *
     * @return Node
     */
    public Node maximum() {
        Node temp = root;
        while (temp != null) {
            if (temp.right == null) {
                return temp;
            }
            temp = temp.right;
        }
        return null;
    }

    /**
     * 查找树中值最小的节点
     *
     * @return Node
     */
    public Node minimum() {
        return min(root);
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.println(node.data);
            inOrder(node.right);
        }
    }

    /**
     * 移除以node为根的树中值为data的节点
     *
     * @param node 树的根节点
     * @param data data
     * @return 返回移除节点后新的树的根
     */
    private Node remove(Node node, int data) {
        if (node == null) {
            return null;
        }
        if (node.data > data) {
            node.left = remove(node.left, data);
            return node;
        } else if (node.data < data) {
            node.right = remove(node.right, data);
            return node;
        } else { // node.data == data
            // 如果待删除节点的左节点为空
            if (node.left == null) {
                Node right = node.right;
                node.right = null;
                return right;
            }
            // 如果待删除节点的右节点为空
            if (node.right == null) {
                Node left = node.left;
                node.left = null;
                return left;
            }
            // 如果待删除节点的左右节点都不为空
            Node left = node.left;
            Node right = node.right;
            // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点；
            // 用此节点替换待删除节点
            Node substitute = min(right);
            assert substitute != null;
            substitute.right = removeMin(right);
            substitute.left = left;

            // 清除无效节点
            node.left = null;
            node.right = null;
            return substitute;
        }
    }

    /**
     * 查找以node为根节点的树中的最小节点
     *
     * @param node
     * @return
     */
    private Node min(Node node) {
        Node temp = node;
        while (temp != null) {
            if (temp.left == null) {
                return temp;
            }
            temp = temp.left;
        }
        return null;
    }

    /**
     * 移除以node为根的树的最大节点
     *
     * @param node 树的根节点
     * @return 返回移除节点后新的根节点
     */
    private Node removeMax(Node node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            Node left = node.left;
            node.left = null;
            return left;
        }
        node.right = removeMax(node.right);

        return node;
    }

    /**
     * 移除以node为根的树的最小节点
     *
     * @param node 树的根节点
     * @return 返回移除节点后新的根节点
     */
    private Node removeMin(Node node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            Node right = node.right;
            node.right = null;
            return right;
        }
        node.left = removeMin(node.left);

        return node;
    }

    /**
     * 定义二分查找树的节点
     */
    private class Node {
        private final int data;
        private Node left;
        private Node right;

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

二分查找树特点分析

1. 二分查找树在平衡的状态下，插入、查找、删除操作的时间复杂度是O(logn)，与树的高度成正比；在极端情况下，会退化成链表，此时的时间复杂度为O(n)。
2. 二分查找树可以使用中序遍历，进行有序输出，这个是散列表没有的特性（无序存储）。
3. 在工程中，使用的平衡二分查找树性能比较稳定；而散列表存在扩容耗时，散列冲突等问题，性能相对不稳定。
4. 散列表的构造比二分查找树要复杂，需要考虑的东西很多，比如散列函数的设计、冲突解决办法、扩容、缩容等；平衡二叉查找树只需要考虑平衡性这一问题，而且这个问题的解决方案比较成熟、固定。