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

二叉树的性质

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

创建一个简单的二叉树

先搭建一个简单的二叉树结构来辅助理解：

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

二叉树的遍历

所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题，比如打印节点内容、节点内容加 1。遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

前序遍历

1. 打印根节点
2. 前序遍历左子树
3. 前序遍历右子树

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

中序遍历

1. 中序遍历左子树
2. 打印结点
3. 中序遍历右子树

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

后序遍历

1. 后序遍历左子树
2. 后序遍历右子树
3. 打印结点

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 标准库中的 LinkedList 作为队列实现：

import java.util.LinkedList;
import java.util.Queue;

public static void levelOrder(TreeNode<Character> root) {
    Queue<TreeNode<Character>> queue = new LinkedList<>();
    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 码校验，可以用来判别文件是否完整。目前应用最为广泛的是 SHA-1 和 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();
        // 每一个对象都有一个独一无二的哈希值，可以通过 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));
    table.insert(str);
    System.out.println(table.contains(str));
}
// 输出 false
// 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();
        // 每一个对象都有一个独一无二的哈希值，可以通过 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-> 
...
*/