int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

graph TD
A(0)---B(1)---C(3)
A---a(2)---aa(5)
B---D(4)
a---ab(6)
C---E(7)
C---F(8)
D---G(9)
D---H(10)

public static Node toTree(int[] array) {
    Node root = new Node(array[0]);
    List<Node> list = new ArrayList<Node>();
    list.add(root);									// 数组下标为 0 的元素放在根节点。
    for (int i = 1; i < array.length; i++) {		// 按照前述方法，创建每个元素节点，并放在对应父节点下
        Node temp = new Node(array[i]);
        list.add(temp);
        Node parent = list.get((i - 1) / 2);
        if (i % 2 == 0) parent.right = temp;
        else parent.left = temp;
    }
    return root;
}

public static class Node {
    public int val;
    public Node left;
    public Node right;
    
    public Node(int val) {
        this.val = val;
    }
}

graph TD
A(NaN)---B(NaN)---C(14)
B---b(NaN)---c(5)
b---D(NaN)---E(1)
D---F(2)
A---a(NaN)---aa(16)
a---ab(20)

graph TD
A(10)---B(8)
B---D(4)---c(2)---d(1)
D---b(6)
B---E(9)
A---C(15)---e(12)
C---ee(23)

graph TB
Root(&#91&#49,9&#93)

Root---L(&#91&#49,5&#93)
style R fill: #BFFFFC
Root---R(&#91&#54,9&#93)

L---LL(&#91&#49,3&#93)
style LR fill: #BFFFFC
L---LR(&#91&#52,5&#93)
R---RL(&#91&#54,7&#93)
R---RR(&#91&#56,9&#93)

LL---LLL(&#91&#49,2&#93)
style LLR fill: #BFFFFC
LL---LLR(&#91&#51,3&#93)
LR---LRL(&#91&#52,4&#93)
LR---LRR(&#91&#53,5&#93)
RL---RLL(&#91&#54,6&#93)
RL---RLR(&#91&#55,7&#93)
RR---RRL(&#91&#56,8&#93)
RR---RRR(&#91&#57,9&#93)

LLL---LLLL(&#91&#49,1&#93)
style LLLR fill: #BFFFFC
LLL---LLLR(&#91&#50,2&#93)

graph TD
A(10)---B(6)
B---D(1, 3)
B---E(7)
A---C(15, 20)
C---F(11, 12)
C---G(19)
C---H(22, 32)

graph TD
ROOT(30, 60<br/>P1 - P2 - P3)
ROOT---R1(10, 20<br/>P1 - P2 - P3)
ROOT---R2(40, 50<br/>. - P2 - P3)
ROOT---R3(70, 80<br/>P1 - P2 - P3)
R1---R11(3, 6)
R1---R12(12, 13)
R1---R13(23, 24)
R2---R21( )
R2---R22(41, 48)
R2---R23(55, 57)
R3---R31(61, 62)
R3---R32(73, 74)
R3---R33(84, 86)

graph TD
ROOT(0, 32, 61<br/>A - B - C)
ROOT---R1(0, 12, 23<br/>A - B - C)
ROOT---R2(32, 40, 52<br/>A - B - C)
ROOT---R3(61, 73, 84<br/>A - B - C)
R1---R11(0<br/>4<br/>9)
R1---R12(12<br/>13<br/>17)
R1---R13(23<br/>24<br/>25)
R2---R21(32<br/>38<br/>39)
R2---R22(40<br/>41<br/>48)
R2---R23(52<br/>55<br/>57)
R3---R31(61<br/>62<br/>66)
R3---R32(73<br/>74<br/>79)
R3---R33(84<br/>86<br/>87)
subgraph 数据链表
R11
R12
R13
R21
R22
R23
R31
R32
R33
end

graph TD
ROOT(0, 32, 61<br/>A - B - C)
ROOT---R1(0, 12, 23<br/>A - B - C)
ROOT---R2(32, 40, 52<br/>A - B - C)
ROOT---R3(61, 73, 84<br/>A - B - C)
R1---R11(0<br/>4<br/>9)
R1---R12(12<br/>13<br/>17)
R1---R13(23<br/>24<br/>25)
R2---R21(32<br/>38<br/>39)
R2---R22(40<br/>41<br/>48)
R2---R23(52<br/>55<br/>57)
R3---R31(61<br/>62<br/>66)
R3---R32(73<br/>74<br/>79)
R3---R33(84<br/>86<br/>87)
subgraph 数据链表
R11
R12
R13
R21
R22
R23
R31
R32
R33
end
subgraph 索引相连
R1
R2
R3
end

graph TB
R[ ]
style a fill: #C0F0E0
R --- a((a))
R --- c[c]
R --- r[r]
a --- ac[c]
a --- ar[r]
style act fill: #C0F0E0
ac --- act((t))
style art fill: #C0F0E0
ar --- art((t))
c --- ca[a]
style cat fill: #C0F0E0
ca --- cat((t))
style can fill: #C0F0E0
ca --- can((n))
style cant fill: #C0F0E0
can --- cant((t))
r --- ro[o]
ro --- roi[i]
style roin fill: #C0F0E0
roi --- roin((n))

class TrimTree {
    /* 节点类 */
    private static class Node {
        Map<Character, Node> next = null;
        int count = 0;
        Node() {
            this.next = new HashMap<>();
            this.count = 0;
        }
    }

    private Node root = null;		// 根节点

    /* 构造器 */
    public TrimTree(String... strings) {
        this.root = new Node();
        for (String s : strings) add(s);
    }
	
    /* 添加字符串 */
    public void add(String s) {
        Node p = root;
        for (char c : s.toCharArray()) {
            if (!p.next.containsKey(c)) p.next.put(c, new Node());
            p = p.next.get(c);
        }
        p.count++;
    }
	
    /* 查找字符串 */
    public int search(String s) {
        Node p = root;
        for (char c : s.toCharArray()) {
            if (!p.next.containsKey(c)) return 0;
            p = p.next.get(c);
        }
        return p.count;
    }
}

graph TD
A(1)---B(0)
A---C(2)
B---C
B---D(3)
B---E(4)

   0  1  2  3  4
0 ┌0, 1, 1, 1, 1┐
1 |1, 0, 1, 0, 0|
2 |1, 1, 0, 0, 0|
3 |1, 0, 0, 0, 0|
4 └1, 0, 0, 0, 0┘

0 [1]→[2]→[3]→[4]→
1 [0]→[2]→
2 [0]→[1]→
3 [0]→
4 [0]→

/* 压缩数据包 */
class DataBox {
    public byte[] data;				// 压缩信息主体
    public Map<Byte, String> key;	// 赫夫曼表
    public int step;				// 补位数
}


class Huff {
    /* 将数据压缩，返回一个压缩包 */
    public static DataBox huff(byte[] data) {
        DataBox dataBox = new DataBox();
        dataBox.key = getHuffMap(data);						// 在压缩包内记录编码表
        dataBox.data = toHuff(data, dataBox);				// 在压缩包内记录压缩后数据，也会记录补位数
        return dataBox;
    }
	
    /* 根据要压缩的数据，计算那个赫夫曼表 */
    private static Map<Byte, String> getHuffMap(byte[] val) {
        if (val == null || val.length == 0) return new HashMap<>();
        Map<Byte, Node> huff = new HashMap<>();
        for (byte c : val) {								// 记录每个字符出现的次数
            if (huff.containsKey(c)) huff.get(c).times++;
            else huff.put(c, new Node(c, 1));
        }
        PriorityQueue<Node> pq = new PriorityQueue<>(huff.values());
        while (pq.size() > 1) {								// 生成赫夫曼树
            Node temp = new Node(pq.remove(), pq.remove());
            pq.add(temp);
        }
        Map<Byte, String> ret = new HashMap<>();
        update(ret, pq.remove(), "");						// 根据那个赫夫曼树，生成赫夫曼编码
        if (ret.size() == 1) ret.put(val[0], "0");			// 特别地，只有唯一字符从场合这样处理
        return ret;
    }
	
    /* 根据赫夫曼表，将数据压缩 */
    private static byte[] toHuff(byte[] val, DataBox d) {
        StringBuilder sb = new StringBuilder();
        for (byte c : val) {								// 得到压缩后的 bit 字符串
            sb.append(d.key.get(c));
        }
        byte[] ret = new byte[(sb.length() + 7) / 8];		// 压缩后的数据放在 byte 数组中
        d.step = sb.length() % 8;							// 记录那个补位数
        for (int i = 0; i < ret.length; i ++) {
            if (i >= ret.length - 1 && d.step != 0) {		// 最后一位可能有补位。那个场合，让有效数字在最左侧
                ret[i] = (byte) (Integer.parseInt(sb.substring(8 * i), 2) << (8 - d.step));
            } else ret[i] = (byte) Integer.parseInt(sb.substring(8 * i, 8 * i + 8), 2);
        }
        return ret;
    }
	
    /* 该方法能遍历赫夫曼树，以获取赫夫曼表 */
    private static void update(Map<Byte, String> ss, Node root, String s) {
        if (root == null) return;
        else if (root.right == null && root.left == null) {
            ss.put(root.val, s);									// 是叶节点的场合，记录这个编码值
        }
        if (root.left != null) update(ss, root.left, s + "0");		// 向左路径记为 0
        if (root.right != null) update(ss, root.right, s + "1");	// 向右路径记为 1
    }
    
    /* 解压压缩包 */
    public static byte[] antiHuff(DataBox d) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < d.data.length; i++) {					// 获取那个压缩数据的编码
            String temp = null;
            if (i >= d.data.length - 1 && d.step != 0) sb.append((temp = Integer.toBinaryString(d.data[i] | 256)), temp.length() - 8, temp.length() - 8 + d.step);				// 遍历到最后，要处理那个补位
            else sb.append((temp = Integer.toBinaryString(d.data[i] | 256)).substring(temp.length() - 8));
        }
        Map<String, Byte> anti = new HashMap<>();
        for (Byte aByte : d.key.keySet()) {							// 将编码表转化为解码表
            anti.put(d.key.get(aByte), aByte);
        }
        List<Byte> ret = new ArrayList<>();
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < sb.length(); i++) {						// 按照解码表，把压缩编码转化为未解压编码
            s.append(sb.charAt(i));
            if (anti.containsKey(s.toString())) {
                ret.add(anti.get(s.toString()));
                s = new StringBuilder();
            }
        }
        byte[] bt = new byte[ret.size()];							// 将 Byte 数组转化为 byte 数组
        for (int i = 0; i < bt.length; i++) {
            bt[i] = ret.get(i);
        }
        return bt;
    }

	/* 节点类，是构建赫夫曼树时用到的类 */
    static class Node implements Comparable<Node> {
        public byte val;			// 代表的 byte 值
        public int times;			// 出现的次数
        public Node left;
        public Node right;

        public Node(Node l, Node r) {
            this.left = l;
            this.right = r;
            this.times = l.times + r.times;
        }

        public Node(byte val, int pow) {
            this.val = val;
            this.times = pow;
        }


        public Node(byte val) {
            this.val = val;
            this.times = 0;
        }

        @Override
        public int compareTo(Node o) {
            return this.times - o.times;
        }
    }
}

class AVL{
    public Node root = null;				// 根节点
    
    /* 添加一个值（添加一个节点）
    	val：要添加的值 */
    public void add(int val) {
        Node toAdd = new Node(val);
        if (root == null) root = toAdd;
        else {
            Node par = root;
            Node temp = root;
            while (temp != null) {			// 确定其插入位置
                par = temp;
                if (val > temp.val) {
                    temp = temp.right;
                    toAdd.way = true;
                } else {
                    temp = temp.left;
                    toAdd.way = false;
                }
            }
            if (toAdd.way) {				// 将其插入到指定位置
                par.right = toAdd;
                par.right.parent = par;
            } else {
                par.left = toAdd;
                par.left.parent = par;
            }
            while (true) {					// 维护该平衡二叉树
                par = toAVL(par);
                if (par.parent == null) {
                    root = par;
                    break;
                } else {
                    if (par.way) par.parent.right = par;
                    else par.parent.left = par;
                    par = par.parent;
                }
            }
        }
    }
	
    /* 维护平衡二叉树
    	root: 待检查节点 */
    private static Node toAVL(Node root) {
        if (root == null) return null;
        int gap = root.rightHeight() - root.leftHeight();
        if (Math.abs(gap) > 1) {			// |gap| > 1 时，需要旋转
            if (gap > 0) {					// gap > 0 需要左旋，否则右旋
                if (root.right.leftHeight() > root.right.rightHeight()) root.right = roll(root.right, true);
                return roll(root, false);
            } else {
                if (root.left.rightHeight() > root.left.leftHeight()) root.left = roll(root.left, false);
                return roll(root, true);
            }
        } else return root;
    }

    /* 对该节点进行旋转。
    	root：待旋转节点
    	dirR：true 的场合右旋，否则左旋 */
    private static Node roll(Node root, boolean dirR) {
        Node temp = null;
        if (dirR) {
            temp = root.left;
            root.left = temp.right;
            if (temp.right != null) {
                temp.right.way = false;
                temp.right.parent = root;
            }
            temp.right = root;
        } else {
            temp = root.right;
            root.right = temp.left;
            if (temp.left != null) {
                temp.left.way = true;
                temp.left.parent = root;
            }
            temp.left = root;
        }
        temp.way = root.way;
        temp.parent = root.parent;
        root.way = dirR;
        root.parent = temp;
        return temp;
    }
    
    /* 一个展示树的方法。供 debug 用 */
    public static void show(Node root) {
        LinkedList<Node> a = new LinkedList<>();
        LinkedList<Node> b = new LinkedList<>();
        a.add(root);
        while (!a.isEmpty()) {
            Node temp = a.removeFirst();
            System.out.print(temp.val + " ");
            if (temp.left != null) b.add(temp.left);
            if (temp.right != null) b.add(temp.right);
            if (a.isEmpty()) {
                System.out.println();
                a = b;
                b = new LinkedList<>();
            }
        }
        System.out.println("共 " + count(root) + " 个节点");
    }
    
    /* 一个清点树中节点的方法 */
    public static int count(Node root) {
        if (root == null) return 0;
        return 1 + count(root.left) + count(root.right);
    }

    public static class Node {
        public int val;				// 值
        public Node left;			// 左节点
        public Node right;			// 右节点
        public Node parent;			// 父节点
        boolean way = false;        // false：该节点是左节点；true：是右节点

        public Node(int val) {
            this.val = val;
        }

        public int leftHeight() {	// 左子树高度
            return (left == null ? 0 : left.height());
        }

        public int rightHeight() {	// 右子树高度
            return (right == null ? 0 : right.height());
        }

        public int height() {		// 该节点树高度
            return Math.max(leftHeight(), rightHeight()) + 1;
        }
    }
}