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

数据结构基础

树

**树是一种非线性的数据结构，**它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。之所以叫树，是因为它看起来像一棵倒挂的树，根朝上，叶朝下。

它具有以下特点：

1. 有一个特殊的结点，称为根结点，根结点没有前驱结点。
2. 除根结点外，其余结点被分成 M(M > 0) 个互不相交的集合 T1、T2、......、Tm，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。
3. 树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。

树的概念

• **结点的度：**一个结点含有子树的个数称为该结点的度；如上图：A 的度为 6
• **树的度：**一棵树中，所有结点度的最大值称为树的度；如上图：树的度为 6
• **叶子结点或终端结点：**度为 0 的结点称为叶结点；如上图：B、C、H、I...等节点为叶结点
• **双亲结点或父结点：**若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A 是 B 的父结点
• **孩子结点或子结点：**一个结点含有的子树的根结点称为该结点的子结点；如上图：B 是 A 的孩子结点
• **根结点：**一棵树中，没有双亲结点的结点；如上图：A
• **结点的层次：**从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推
• **树的高度或深度：**树中结点的最大层次；如上图：树的高度为 4

树的以下概念只需了解，在看书时只要知道是什么意思即可：

• **非终端结点或分支结点：**度不为 0 的结点；如上图：D、E、F、G...等节点为分支结点
• **兄弟结点：**具有相同父结点的结点互称为兄弟结点；如上图：B、C 是兄弟结点
• **堂兄弟结点：**双亲在同一层的结点互为堂兄弟；如上图：H、I 互为兄弟结点
• **结点的祖先：**从根到该结点所经分支上的所有结点；如上图：A 是所有结点的祖先
• **子孙：**以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是 A 的子孙
• **森林：**由 m（m>=0）棵互不相交的树组成的集合称为森林

二叉树

概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树不存在度大于 2 的结点。二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

对于任意的二叉树都是由以下几种情况复合而成的：

两种特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为 K，且结点总数是 2 的 k 次方 -1，则它就是满二叉树。
2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 0 至 n-1 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质

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-> 
...
*/