Java 数据结构实战：二叉树与哈希表核心解析

二叉树的性质

1. 若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 $2^{i-1}$ (i>0) 个结点。
2. 若规定只有根结点的二叉树的深度为 1，则深度为 K 的二叉树的最大结点数是 $2^K - 1$ (k>=0)。
3. 对任何一棵二叉树，如果其叶结点个数为 n0，度为 2 的非叶结点个数为 n2，则有 n0＝n2＋1。
4. 具有 n 个结点的完全二叉树的深度 k 为 $ ext{floor}( ext{log}_2 n) + 1$ 上取整。
5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：
   • 若 i>0，双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点。
   • 若 2i+1 < n，左孩子序号：2i+1，否则无左孩子。
   • 若 2i+2 < n，右孩子序号：2i+2，否则无右孩子。

创建一个简单的二叉树

我们先定义一个简单的 TreeNode 类，然后构建一棵树。

public class Main {
    public static void main(String[] args) {
        TreeNode<Character> a = new TreeNode<>('A');
        TreeNode<Character> b = new TreeNode<>('B');
        TreeNode<Character> c = new TreeNode<>('C');
        TreeNode<Character> d = new TreeNode<>('D');
        TreeNode<Character> e = new TreeNode<>('E');
        
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        
        System.out.println(a.left.left.element);
    }

    public static class TreeNode<E> {
        public E element;
        public TreeNode<E> left, right;
        
        public TreeNode(E element) {
            this.element = element;
        }
    }
}
// 输出 D 

二叉树的遍历

所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。遍历是二叉树上最重要的操作之一，是进行其它运算的基础。

前序遍历

逻辑很简单：先打印根节点，再前序遍历左子树，最后前序遍历右子树。

public class Main {
    public static void main(String[] args) {
        TreeNode<Character> a = new TreeNode<>('A');
        TreeNode<Character> b = new TreeNode<>('B');
        TreeNode<Character> c = new TreeNode<>('C');
        TreeNode<Character> d = new TreeNode<>('D');
        TreeNode<Character> e = new TreeNode<>('E');
        TreeNode<Character> f = new TreeNode<>('F');
        TreeNode<Character> g = new TreeNode<>('G');
        TreeNode<Character> h = new TreeNode<>('H');
        
        a.left = b; a.right = c;
        b.left = d; b.right = e;
        e.left = h;
        c.left = f; c.right = g;
        
        preOrder(a);
    }

    public static void preOrder(TreeNode<Character> root) {
        if (root == null) return;
        System.out.print(root.element + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static class TreeNode<E> {
        public E element;
        public TreeNode<E> left, right;
        public TreeNode(E element) { this.element = element; }
    }
}
// 输出 A B D E H C F G

中序遍历

顺序变为：中序遍历左子树 -> 打印结点 -> 中序遍历右子树。

public static void inOrder(TreeNode<Character> root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.element + " ");
    inOrder(root.right);
}
// 输出 D B H E A F C G 

后序遍历

顺序变为：后序遍历左子树 -> 后序遍历右子树 -> 打印结点。

public static void postOrder(TreeNode<Character> root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.element + " ");
}
// 输出 D H E B F G C A 

层序遍历

利用队列来实现层序遍历。首先将根节点存入队列，接着循环执行以下步骤：

1. 出队操作，得到一个结点，并打印结点的值。
2. 将此结点的左右孩子结点依次入队。

这里我们使用 Java 标准库中的 ArrayDeque 来模拟队列行为。

import java.util.ArrayDeque;
import java.util.Queue;

public static void levelOrder(TreeNode<Character> root) {
    Queue<TreeNode<Character>> queue = new ArrayDeque<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode<Character> node = queue.poll();
        System.out.print(node.element + " ");
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}
// 输出 A B C D E F G H 

二叉查找树和平衡二叉树

二叉查找树

也叫二叉搜索树或二叉排序树，特性如下：

1. 左子树中所有结点的值，均小于其根结点的值。
2. 右子树中所有结点的值，均大于其根结点的值。
3. 二叉搜索树的子树也是二叉搜索树。

平衡二叉树

在插入结点时要尽可能避免一边倒的情况。引入平衡二叉树的概念，在插入时如果不维护二叉树的平衡，某一边只会无限制的延伸下去，出现极度不平衡的情况。

1. 平衡二叉树一定是一颗二叉查找树。
2. 任意结点的左右子树也是一颗平衡二叉树。
3. 从根结点开始，左右子树高度差都不能超过 1，否则视为不平衡。

二叉树上结点的左子树高度减去右子树高度，得到的结果称为该节点的平衡因子。

失衡情况的调整：

1. LL 型调整（右旋）
2. RR 型调整（左旋）
3. RL 型调整（先右旋再左旋）
4. LR 型调整（先左旋再右旋）

红黑树

红黑树也是二叉查找树的一种，结点有红有黑，通过颜色约束保证大致平衡。

1. 规则 1：每个结点可以是黑色或红色。
2. 规则 2：根结点一定是黑色。
3. 规则 3：红色结点的父结点和子结点不能为红色（不能有两个连续的红色）。
4. 规则 4：所有的空结点都是黑色（空结点视为 null，红黑树中是将空结点视为叶子结点）。
5. 规则 5：每个结点到空结点路径上出现的黑色结点的个数都相等。

哈希表

散列表通过散列函数（哈希函数）将需要参与检索的数据与散列值关联起来，生成一种便于搜索的数据结构。

散列函数可以对一个目标计算出其对应的哈希值，只要是同一个目标，无论计算多少次，得到的哈希值都是一样的结果。不同的目标计算出的结果几乎都不同。哈希函数应用广泛，比如下载网站提供文件的 MD5 码校验。

我们可以利用哈希值的特性设计一张全新的表结构，保存的位置与其对应的哈希值有关。一般比较简单的哈希函数就是取模操作，哈希表长度最好是一个素数，模就是多少。

保存的数据是无序的，哈希表在查找时只需要进行一次哈希函数计算就能直接找到对应元素的存储位置，效率极高。

public class HashTable<E> {
    private final int TABLE_SIZE = 10;
    private final Object[] TABLE = new Object[TABLE_SIZE];

    // 插入
    public void insert(E obj) {
        int index = hash(obj);
        TABLE[index] = obj;
    }

    // 判断是否包含
    public boolean contains(E obj) {
        int index = hash(obj);
        return TABLE[index] == obj;
    }

    private int hash(E obj) {
        int hashCode = obj.hashCode();
        return hashCode % TABLE_SIZE;
    }
}

public static void main(String[] args) {
    HashTable<String> table = new HashTable<>();
    String str = "AAA";
    System.out.println(table.contains(str)); // false
    table.insert(str);
    System.out.println(table.contains(str)); // true
}

通过哈希函数计算得到一个目标的哈希值，但是在某些情况下哈希值可能会出现相同的情况，称为哈希碰撞（哈希冲突）。

常见的哈希冲突解决方案是链地址法。当出现哈希冲突时，依然将其保存在对应的位置上，连接为一个链表的形式。

package com.test.collection;

public class HashTable<E> {
    private final int TABLE_SIZE = 10;
    private final Node[] TABLE = new Node[TABLE_SIZE];

    // 放入头结点
    public HashTable() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            TABLE[i] = new Node<>(null);
        }
    }

    // 插入
    public void insert(E obj) {
        int index = hash(obj);
        Node<E> head = TABLE[index];
        Node<E> node = new Node<>(obj);
        node.next = head.next;
        head.next = node;
    }

    // 判断是否包含
    public boolean contains(E element) {
        int index = hash(element);
        Node<E> node = TABLE[index].next;
        while (node != null) {
            if (node.element == element) return true;
            node = node.next;
        }
        return false;
    }

    private int hash(E obj) {
        int hashCode = obj.hashCode();
        return hashCode % TABLE_SIZE;
    }

    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < TABLE_SIZE; i++) {
            Node<E> head = TABLE[i].next;
            while (head != null) {
                builder.append(head.element + "->");
                head = head.next;
            }
            builder.append("\n");
        }
        return builder.toString();
    }

    private static class Node<E> {
        private final E element;
        private Node<E> next;

        private Node(E element) {
            this.element = element;
        }
    }
}

public static void main(String[] args) {
    HashTable<Integer> table1 = new HashTable<>();
    for (int i = 0; i < 100; i++) table1.insert(i);
    System.out.println(table1);
}
/* 输出示例：
90->80->70->60->50->40->30->20->10->0-> 
91->81->71->61->51->41->31->21->11->1-> 
...
*/