数据结构之二叉树

kinglyjn 2021-01-15 阅读次

二叉树的起源

说起二叉树，我们不能直接从 “树” 开始，而是要回到数据结构的两大 “原始部落”：数组和链表。二叉树（尤其是二叉搜索树 BST）的出现，本质上是一场为了终结 “性能偏科” 而发起的架构革命。

原始部落的“偏科”困境

在二叉树诞生前，程序员只能在两种极端的存储方式中挣扎：

数组的痛：如果你在 100 万长度数组开头插入一个数，你得把后面 99.9 万个数往后挪一位。这实在是不可接受的。
链表的痛：即便链表是排好序的，你也无法跳跃。想找中间的数？对不起，请从头开始数。

二叉树的起源

二叉搜索树（BST）的灵感来源极其天才：如果我们将二分查找的 “逻辑过程” 直接变成数据的 “存储物理结构” 呢？

二分查找的逻辑：先看中间的数，比它小往左看，比它大往右看。
二叉树的结构：把中间那个数作为根节点，左边连小的，右边连大的。

二叉树 = 具有二分查找能力的链表：它通过增加一个维度的指针（从 next 变成 left / right），成功实现了到二维的跨越。

解决的问题

二叉树存在的终极任务只有四个字：动态平衡，即在数据不断变动（动态插入/删除）的情况下，依然保持极高的查找速度。

它既像链表，节点分散存储，插入时只需改动几个指针，不需要挪动整块内存。
它又像数组：通过父子节点的逻辑关系，每次比较都能砍掉一半的搜索范围。

从理想到现实的修补

虽然二叉树（BST）理论上解决了数组和链表的矛盾，但它在现实中遇到了一个致命伤：退化。如果数据是有序存入的（比如 1, 2, 3, 4, 5），二叉树会 “长歪”，变成一根长长的棍子（链表），这时它所有的优势都荡然无存。于是从二叉树在20世纪60年代被正式提出，到后续几十年的算法史，其实都是在为二叉树做 “整形手术”：

AVL 树：为了解决退化，发明了“旋转”，强迫树必须长得左右对称。
红黑树：觉得 AVL 旋转太频繁浪费性能，于是发明了 “颜色规则”，在平衡和效率间找平衡（用于 Java HashMap）。
B/B+ 树：觉得内存太小，要把树存到硬盘里，于是把 “二叉” 变成了 “多叉”，减少翻页次数（用于数据库索引）。

代码实现

下面是 BST 核心代码及其效果演示。你可看到它是如何通过递归实现 “自动导航” 的。

🔍 准备就绪。尝试搜索 15 或 35。

/**
 * @author KJ
 * @description 最基本的二叉树
 */
public class MyBST {

    private TreeNode root;
    public static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

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

    /**
     * 插入
     */
    public void insert(int data) {
        // 必须接收并设置root，否则 root 永远是空
        this.root = insert(this.root, data);
    }

    private TreeNode insert(TreeNode curRoot, int data) {
        if (curRoot == null) {
            return new TreeNode(data);
        }
        if (data < curRoot.data) {
            curRoot.left = insert(curRoot.left, data);
        } else if (data > curRoot.data) {
            curRoot.right = insert(curRoot.right, data);
        }
        return curRoot;
    }

    public void remove(int data) {
        this.root = remove(this.root, data);
    }

    private TreeNode remove(TreeNode curRoot, int data) {
        // ===== 情况 0：没找到，直接返回 =====
        if (curRoot == null) {
            return null;
        }

        // ===== 第一步：找到要删的节点 =====
        if (data < curRoot.data) {
            curRoot.left = remove(curRoot.left, data);
        } else if (data > curRoot.data) {
            curRoot.right = remove(curRoot.right, data);
        }
        // ===== 第二步：找到了！开始处理后事 =====
        else {
            // ---- 情况 1 & 2：最多只有一个孩子 ----
            if (curRoot.left == null) {
                return curRoot.right; // 左空，右孩子上位（右也可能为null，那就是情况1）
            }
            if (curRoot.right == null) {
                return curRoot.left;  // 右空，左孩子上位
            }

            // ---- 情况 3：左右都有，找接班人 ----
            TreeNode successor = findMin(curRoot.right); // 右子树最小节点
            curRoot.data = successor.data;               // 值拷贝（把接班人值换过来）
            curRoot.right = remove(curRoot.right, successor.data); // 删掉那个接班人原来的位置
        }
        return curRoot;
    }

    // 找以 node 为根的子树中的最小值
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 查找
     */
    public boolean search(int value) {
        TreeNode curRoot = this.root;
        while (curRoot != null) {
            if (value == curRoot.data) return true;
            curRoot = value < curRoot.data ? curRoot.left : curRoot.right;
        }
        return false;
    }

    /**
     * 中序遍历打印树结构
     */
    public void printTree() {
        printTree(root, 0);
    }

    private void printTree(TreeNode node, int level) {
        // 如果需要分别对左右子树做分别处理，可以增加入参标识
        if (node == null) return;

        // 1. 先打印右子树（因为在视觉上右子树在上方）
        printTree(node.right, level + 1);

        // 2. 打印当前节点：根据层级进行缩进
        if (level == 0) {
            System.out.println(node.data);
        } else {
            String subPrefix = "|    ".repeat(level - 1);
            System.out.println(subPrefix + "|----" + node.data);
        }

        // 3. 最后打印左子树
        printTree(node.left, level + 1);
    }

    public static void main(String[] args) {
        MyBST bst = new MyBST();

        // 1. 模拟数据存入
        int[] nodes = {25, 15, 35, 10, 20, 30, 40};
        Arrays.stream(nodes).forEach(bst::insert);

        // 2. 遍历展示树的结构
        bst.printTree();
        System.out.println();

        // 3. 测试删除
        bst.remove(35);
        bst.printTree();
        System.out.println();

        // 4. 测试搜索功能
        System.out.println(bst.search(20) ? "存在" : "不存在");
        System.out.println(bst.search(99) ? "存在" : "不存在");
    }
}

测试效果：

|    |----40
|----35
|    |----30
25
|    |----20
|----15
|    |----10

|----40
|    |----30
25
|    |----20
|----15
|    |----10

存在
不存在

二叉树和堆的关系

简单来说，堆（Heap）就是一个非常有 “纪律” 的完全二叉树。完全满足两个条件就可以称之为“堆”：

条件 A：结构必须是 “完全二叉树”：普通的二叉树可以长得歪七拧八，左边一长串，右边空荡荡。但堆要求树的每一层必须是满的。如果最后一层不满，也必须从左到右依次排开，不能跳着长。就像排队报数，必须先站满第一排，再站第二排，且第二排的人必须靠左站齐，不能中间留位子。
条件 B：必须满足 “堆序性”：在二叉树里，节点之间可能没啥大小逻辑。但在堆里，必须满足 父节点 > 子节点（大顶堆）或 父节点 < 子节点（小顶堆）。

有了树，为什么要搞出个 “堆” 来？主要还是为了解决 “找极值” 的问题。

效率极高：如果你想从100万个数字里不停地找出最大的那个，用普通数组你得翻遍全身；但用大顶堆，最大值就在最顶端，一眼就能看到。
动态调整：当你拿走最大的数，或者新进来一个数，堆能通过一套简单的 “比武招亲” 规则（上浮或下沉），快速重新排好顺序。

说白了，堆的最大用处就是 “动态管理最值”。只要你的需求符合以下描述，选堆那就准没错：

数据一直在变动（新元素加入或旧元素删除）。
你永远只想关注这群数据里最大、最小或排在最前面的那几个。

标题：

数据结构之二叉树

作者：

kinglyjn

声明：

引用本文请务必注明出处，原创不易，感谢尊重。

K-空间

koo-hub, cool-code.

数据结构之二叉树

二叉树的起源

代码实现

二叉树和堆的关系