树和二分查找树

树的基本定义

在树中，每个节点都含有自己的数值，以及与之相连的子节点，连接子节点的线叫相连线（edge）。如下图所示，A是根节点（root），也是B和C的父节点（parent node），也就是说B、C都是A的子节点（child node）。在树中，没有子节点的节点叫做叶子节点（leaf node），下图中的H、I、J、F、G都是叶子节点。

节点的高度（height）和深度（depth）

节点的高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。若规定根节点的深度和叶子节点的高度都是0：

• 节点的高度：此节点到与之相连的叶子节点之间edge的数量，以上图为例，B的高度为2（B到叶子节点H和I的edge数量都是2），C的高度为1。
• 节点的深度：此节点到根节点的edge的数量，以上图为例，B和C的深度都是1。

节点的度

• 度的定义：节点所拥有的子树的数目称为该节点的度。
• 注意： 叶子节点的度为0。
• 二叉树中度为0的节点=度为2的节点 1。也就是说，二叉树中叶子节点的数量总是等于拥有两个孩子的节点的数量 1。

树的种类

• 二叉树（Binary Tree）：每个节点最多含有两个子节点，上面图示中的树就是二叉树。
• 完全二叉树（Complete Binary Tree）：假设一个二叉树深度（depth）为d（d > 1），除了第d层外，其它各层的节点数量均已达到最大值，且第d层所有节点从左向右紧密排列，这样的二叉树就是完全二叉树。上图的树就是一个完全二叉树。
• 满二叉树（Full Binary Tee）：
  • 国内：除最后一层无任何子节点，每一层上的所有结点都有两个子结点的二叉树。
  • 国外：二叉树的结点要么是叶子结点，要么有两个子结点。
• 二分查找树（Binary Search Tree）：在此树中，每个节点的数值比左子树上的每个节点都大，比所有右子树上的节点都小。
• 平衡二叉树（AVL Tree）：
  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1；
  • 平衡二叉树的左右两个子树都是一棵平衡二叉树。
• B树（B-Tree）：B树和平衡二叉树一样，只不过它是一种多叉树（一个节点的子节点数量可以超过二）。
• 红黑树（Red—Black Tree）：是一种自平衡二叉寻找树。

二叉树的性质

1. 二叉树的第i层至多有2^(i-1) 个节点(i>=1)。满二叉树的第i层为2^(i-1)个节点；
2. 深度为k的二叉树至多有2^k-1个节点(k>=1)；
3. 对任何一颗二叉树T，如果其叶子节点数量为n，则度为2的节点数量为n-1；
4. 具有n个节点的完全二叉树的深度为[logn] 1（[x]表示不大于x的最大整数）。
5. 对于n个节点的完全二叉树，对任意节点i（0<=i<n）具有如下性质：
   • 如果i存在父节点，则父节点为 (i-1)/2；
   • 如果i存在左孩子，则左孩子为 2*i 1；
   • 如果i存在右孩子，则右孩子为 2*i 2。

二分查找树（Binary Search Tree）的实现

在二分查找树（很多地方也叫二叉搜索树）中，每个节点的数值比它的左子树的数值都大，比它的右子树的数值都小，因此如果我们要查找特定的数值，只需要从根节点出发，根据二分查找树的特性，顺着特定的路径就能找到目标。

在二分查找树中，插入、删除、搜索的复杂度都等于树高，平均复杂度为O(logn)。

注意：本文不讨论树的平衡，插入和删除时不做平衡处理。

定义节点的结构体

    /**
     * 定义节点
     */
    static class TreeNode {
        int value;
        // 左子树
        TreeNode left;
        // 右子树
        TreeNode right;

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

    /**
     * 定义二叉树的根节点
     */
    TreeNode root = null;

insert方法

在insert方法中，我们首先判断树的根节点是否为空，如果为空，就把当前插入的节点设为根节点。如果根节点不为空，我们需要根据当前节点的value值，从根节点出发，从左或者向右遍历，找到一个符合当前节点插入的位置。

    /**
     * 核心方法 insert：插入节点到二分查找树
     *
     * @param value
     */
    public void insert(int value) {
        TreeNode newNode = new TreeNode(value);
        // 插入到根节点
        if (root == null) {
            root = newNode;
            return;
        }
        // 遍历，找到符合插入的位置
        TreeNode current = root;
        TreeNode currentParent = null;
        while (current != null) {
            // parent要在current走之前走
            currentParent = current;
            // 插入的节点已经存在的情况下，直接返回
            if (value == current.value) {
                return;
            } else if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        if (value < currentParent.value) {
            currentParent.left = newNode;
        } else if (value > currentParent.value) {
            currentParent.right = newNode;
        }
    }

get方法

get方法用于根据节点值返回节点，如果找到了就返回节点信息，没找到就返回null。

    /**
     * 核心方法 get：根据节点值返回节点
     *
     * @param value
     * @return
     */
    public TreeNode get(int value) {
        TreeNode current = root;
        while (current != null) {
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }

delete方法

删除节点的方法比较复杂，假设我们找到的删除节点为current，我们需要从以下三种情况去讨论如何删除：

• current是叶子节点：直接删除就好了；
• current只有一个孩子：直接把节点删除，然后被删除节点的孩子替代删除节点；
• current有两个孩子：需要从左子树找到一个最大的节点，或者从右子树找到一个最小的节点替代删除节点的位置，本文采用的是从左子树找到一个最大的节点（取名为successor）代替被删除节点。

对current有两个孩子的情况，我们获取的successor可能会有以下三种情况：

1. 是叶子节点；
2. 是被删除节点的直接左孩子；
3. 只有左孩子（不可能有右孩子，如果有右孩子就不可能是successor）。

对于情况1和情况3，successor替代current要走以下三步：

1. current的左子树挂载到successor的左子树；
2. current的右子树挂载到successor的右子树；
3. successor代替current位置挂到parent的对应位置。

而对于情况2，只需要走上面的步骤2和步骤三。

情况3的删除步骤如下所示：

情况2删除步骤如下所示：

情况1删除步骤如下所示：

    /**
     * 核心方法 delete：将节点从二分查找树中删除。这里需要分三种情况去删除：
     * 1.删除的节点是叶子节点，那么直接删除就好了；
     * 2.删除的节点只有一个孩子，那么直接把节点删除，然后删除节点的孩子替代删除节点；
     * 3.删除的节点有两个孩子，那么就需要从左子树找到一个最大的节点，或者从右子树找到一个最小的节点替代删除节点的位置。
     *
     * @param value
     */
    public boolean delete(int value) {
        if (root == null) {
            return false;
        }
        // 要删除的节点
        TreeNode current = root;
        // 要删除节点的父节点
        TreeNode currentParent = null;
        // 要删除节点是否是左孩子
        boolean isLeftChild = false;
        while (current != null && current.value != value) {
            currentParent = current;
            if (value < current.value) {
                current = current.left;
                isLeftChild = true;
            } else if (value > current.value) {
                current = current.right;
                isLeftChild = false;
            }
        }
        // current为null说明没找到要删除的节点
        if (current == null) {
            return false;
        }
        // 情况1：删除叶子节点
        if (current.left == null && current.right == null) {
            // 删除根节点
            if (currentParent == null) {
                root = null;
            } else if (isLeftChild) {
                currentParent.left = null;
            } else {
                currentParent.right = null;
            }
        }
        // 情况2：只有一个孩子为左孩子，需要把它的左孩子替代掉上去
        else if (current.right == null) {
            // 删除根节点
            if (currentParent == null) {
                root = current.left;
            } else if (isLeftChild) {
                currentParent.left = current.left;
            } else {
                currentParent.right = current.left;
            }
        }
        // 情况3：只有一个孩子为右孩子，需要把它的右孩子替代上去
        else if (current.left == null) {
            // 删除根节点
            if (currentParent == null) {
                root = current.right;
            } else if (isLeftChild) {
                currentParent.left = current.right;
            } else {
                currentParent.right = current.right;
            }
        }
        // 情况4：被删除的节点有两个子节点
        else {
            // 首先需要从左子树找到值最大的节点，这里把这个节点命名为successor
            TreeNode successor = getSuccessor(current);
            // successor替代删除节点
            // 如果successor是叶子节点/只有左孩子的非current.left节点，需要走以下三步：
            //  1.把current的左子树挂载到successor的左子树；
            //  2.把current的右子树挂载到successor的右子树；
            //  3.successor代替current位置挂到parent对应位置。
            // 如果successor是current.left，不能直接把current的左子树直接挂到successor的左子树下面，只需要走两步：
            //  1. 把current的右子树挂载到successor的右子树；
            //  2. successor代替current位置挂到parent对应位置。
            successor.right = current.right;
            if (currentParent == null) {
                root = successor;
            } else if (isLeftChild) {
                currentParent.left = successor;
            } else {
                currentParent.right = successor;
            }
        }
        return true;
    }

    /**
     * 从左子树中找到值最大的节点。
     * successor有三种情况：
     * 1.是叶子节点；
     * 2.是node.left；
     * 3.不是node.left，有孩子，但是只有左孩子
     *
     * @param node
     * @return
     */
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode current = node.left;
        TreeNode successor = node;
        TreeNode successorParent = null;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.right;
        }
        // 对于第1和第3种情况，要先把successor从二叉树移除
        // 如果有左孩子，还要吧successor的左子孩子替代successor位置
        // 由于第1和第3种情况会比第二种情况多走一步：把node的左子树挂载到successor的左子树，因此要在返回之前先做
        if (successor != node.left) {
            successorParent.right = successor.left;
            successor.left = node.left;
        }
        return successor;
    }

树的遍历

树的遍历有三种，我们根据根节点的访问顺序分为以下三种遍历方式：

• 前序遍历 (Pre-order Traversal)：节点访问顺序：根节点->左孩子->右孩子；
• 中序遍历 (In-order Traversal)：节点访问顺序：左孩子->根节点->右孩子；
• 后序遍历 (Post-order Traversal)：节点访问顺序：左孩子->->右孩子->根节点。

对于下面的一颗二叉树：

• 前序遍历的结果为：2, 1, 7, 3, 26, 25, 19, 17, 90, 36
• 中序遍历结果为：1, 2, 3, 7, 17, 19, 25, 26, 36, 90
• 后续遍历结果为：1, 3, 17, 19, 25, 36, 90, 26, 7, 2

前序遍历

下面是前序遍历的递归实现方式，当遍历节点为空时结束递归。

    public List<Integer> preorderTraversal(BinarySearchTree.TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    private void preorder(BinarySearchTree.TreeNode current, List<Integer> result) {
        if (current == null) {
            return;
        }
        result.add(current.value);
        preorder(current.left, result);
        preorder(current.right, result);
    }

中序遍历

    public List<Integer> inorderTraversal(BinarySearchTree.TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(BinarySearchTree.TreeNode current, List<Integer> result) {
        if (current == null) {
            return;
        }
        inorder(current.left, result);
        result.add(current.value);
        inorder(current.right, result);
    }

后序遍历

    public List<Integer> postorderTraversal(BinarySearchTree.TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }

    private void postorder(BinarySearchTree.TreeNode current, List<Integer> result) {
        if (current == null) {
            return;
        }
        postorder(current.left, result);
        postorder(current.right, result);
        result.add(current.value);
    }

附录

TreeOperation：打印树的工具类

from：https://www.cnblogs.com/liulaolaiu/p/11744409.html

public class TreeOperation {
        /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

    // 用于获得树的层数
    public static int getTreeDepth(BinarySearchTree.TreeNode root) {
        return root == null ? 0 : (1   Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }


    private static void writeArray(BinarySearchTree.TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.value);

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex   1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex   1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex   2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex   1][columnIndex   gap] = "\\";
            writeArray(currNode.right, rowIndex   2, columnIndex   gap * 2, res, treeDepth);
        }
    }


    public static void show(BinarySearchTree.TreeNode root) {
        if (root == null) System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3   1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i   ) {
            for (int j = 0; j < arrayWidth; j   ) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth   1)/ 2] = (char)(root.val   '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i   ) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i  = line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

二分查找树完整代码 测试代码

public class BinarySearchTree {
    /**
     * 定义节点
     */
    static class TreeNode {
        int value;
        // 左子树
        TreeNode left;
        // 右子树
        TreeNode right;

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

    /**
     * 定义二叉树的根节点
     */
    TreeNode root = null;

    /**
     * 核心方法 insert：插入节点到二分查找树
     *
     * @param value
     */
    public void insert(int value) {
        TreeNode newNode = new TreeNode(value);
        // 插入到根节点
        if (root == null) {
            root = newNode;
            return;
        }
        // 遍历，找到符合插入的位置
        TreeNode current = root;
        TreeNode currentParent = null;
        while (current != null) {
            // parent要在current走之前走
            currentParent = current;
            // 插入的节点已经存在的情况下，直接返回
            if (value == current.value) {
                return;
            } else if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        if (value < currentParent.value) {
            currentParent.left = newNode;
        } else if (value > currentParent.value) {
            currentParent.right = newNode;
        }
    }

    /**
     * 核心方法 get：根据节点值返回节点
     *
     * @param value
     * @return
     */
    public TreeNode get(int value) {
        TreeNode current = root;
        while (current != null) {
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }

    /**
     * 核心方法 delete：将节点从二分查找树中删除。这里需要分三种情况去删除：
     * 1.删除的节点是叶子节点，那么直接删除就好了；
     * 2.删除的节点只有一个孩子，那么直接把节点删除，然后删除节点的孩子替代删除节点；
     * 3.删除的节点有两个孩子，那么就需要从左子树找到一个最大的节点，或者从右子树找到一个最小的节点替代删除节点的位置。
     *
     * @param value
     */
    public boolean delete(int value) {
        if (root == null) {
            return false;
        }
        // 要删除的节点
        TreeNode current = root;
        // 要删除节点的父节点
        TreeNode currentParent = null;
        // 要删除节点是否是左孩子
        boolean isLeftChild = false;
        while (current != null && current.value != value) {
            currentParent = current;
            if (value < current.value) {
                current = current.left;
                isLeftChild = true;
            } else if (value > current.value) {
                current = current.right;
                isLeftChild = false;
            }
        }
        // current为null说明没找到要删除的节点
        if (current == null) {
            return false;
        }
        // 情况1：删除叶子节点
        if (current.left == null && current.right == null) {
            // 删除根节点
            if (currentParent == null) {
                root = null;
            } else if (isLeftChild) {
                currentParent.left = null;
            } else {
                currentParent.right = null;
            }
        }
        // 情况2：只有一个孩子为左孩子，需要把它的左孩子替代掉上去
        else if (current.right == null) {
            // 删除根节点
            if (currentParent == null) {
                root = current.left;
            } else if (isLeftChild) {
                currentParent.left = current.left;
            } else {
                currentParent.right = current.left;
            }
        }
        // 情况3：只有一个孩子为右孩子，需要把它的右孩子替代上去
        else if (current.left == null) {
            // 删除根节点
            if (currentParent == null) {
                root = current.right;
            } else if (isLeftChild) {
                currentParent.left = current.right;
            } else {
                currentParent.right = current.right;
            }
        }
        // 情况4：被删除的节点有两个子节点
        else {
            // 首先需要从左子树找到值最大的节点，这里把这个节点命名为successor
            TreeNode successor = getSuccessor(current);
            // successor替代删除节点
            // 如果successor是叶子节点/只有左孩子的非current.left节点，需要走以下三步：
            //  1.把current的左子树挂载到successor的左子树；
            //  2.把current的右子树挂载到successor的右子树；
            //  3.successor代替current位置挂到parent对应位置。
            // 如果successor是current.left，不能直接把current的左子树直接挂到successor的左子树下面，只需要走两步：
            //  1. 把current的右子树挂载到successor的右子树；
            //  2. successor代替current位置挂到parent对应位置。
            successor.right = current.right;
            if (currentParent == null) {
                root = successor;
            } else if (isLeftChild) {
                currentParent.left = successor;
            } else {
                currentParent.right = successor;
            }
        }
        return true;
    }

    /**
     * 从左子树中找到值最大的节点。
     * successor有三种情况：
     * 1.是叶子节点；
     * 2.是node.left；
     * 3.不是node.left，有孩子，但是只有左孩子
     *
     * @param node
     * @return
     */
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode current = node.left;
        TreeNode successor = node;
        TreeNode successorParent = null;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.right;
        }
        // 对于第1和第3种情况，要先把successor从二叉树移除
        // 如果有左孩子，还要吧successor的左子孩子替代successor位置
        // 由于第1和第3种情况会比第二种情况多走一步：把node的左子树挂载到successor的左子树，因此要在返回之前先做
        if (successor != node.left) {
            successorParent.right = successor.left;
            successor.left = node.left;
        }
        return successor;
    }


    public static void main(String[] args) {
        int[] ints = new int[]{2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i : ints) {
            binarySearchTree.insert(i);
        }
        TreeOperation.show(binarySearchTree.root);
        binarySearchTree.delete(2);
        TreeOperation.show(binarySearchTree.root);
    }
}

参考

图灵星球——树和二分查找树

这篇好文章是转载于：学新通技术网