一、预备知识

树叶：没有儿子节点的叫做树叶（leaf）。
深度：对任意节点n，n的深度（depth）为从根到n的唯一路径长。因此根的深度为0。
高度：对任意节点n，n的高度是从n到一片树叶的最长路径的长。

二、树的实现

相比顺序结构如：链表、数组。树的结构使其每一个节点除了数据以外还需要有一些指针，使得该节点的每一个儿子都有一个指针指向它。
以二叉树为例：

public class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;
    public int height;

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

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                '}';
    }
}

三、树的遍历及应用

树有很多应用。比如文件系统、省市区搜索框等。

3.1 先序遍历

对节点的处理在它的儿子之前叫做先序遍历。

/**
 * 先序打印
 * parent -> left -> right
 */
public static void printPreorder(TreeNode head) {
    if (head == null) return;
    System.out.print(head.value + ",");
    printPreorder(head.left);
    printPreorder(head.right);
}

3.2 中序遍历

/**
 * 中序打印
 * left -> parent -> right
 */
public static void printInorder(TreeNode head) {
    if (head == null) return;
    printInorder(head.left);
    System.out.print(head.value + ",");
    printInorder(head.right);
}

3.3 后序遍历

对节点的处理在它的儿子之后叫做后序遍历。

/**
 * 后序打印
 * left -> right -> parent
 */
public static void printPostorder(TreeNode head) {
    if (head == null) return;
    printPostorder(head.left);
    printPostorder(head.right);
    System.out.print(head.value + ",");
}

四、二叉树

定义：每一个节点最多拥有两个儿子。

4.1 二叉查找树

定义：对于任意一个节点X，它的左子树所有关键字都小于X的关键字，而它的右子树中所有的关键字都大于X的关键字

4.1.1 Find

查找非常的简单，相当于折半查找，只是用了递归。

public static TreeNode find(TreeNode node, int val) {
    if (node == null) {
        return null;
    }

    if (val < node.value) {
        return find(node.left, val);
    } else if (val > node.value) {
        return find(node.right, val);
    } else {
        return node;
    }
}

4.1.2 Insert

与Find差不多，只是Find是返回，Insert是创建。

public static TreeNode insert(TreeNode head, int k) {
    if (head == null) {
        head = new TreeNode(k);
    }
    if (k < head.value) {
        head.left = insert(head.left, k);
    } else if (k > head.value) {
        head.right = insert(head.right, k);
    }

    return head;
}

4.1.3 FindMin

以二叉查找树的定义，根节点最左边的儿子就是最小值。

public static TreeNode findMin(TreeNode node) {
    if (node.left == null) return node;
    return findMin(node.left);
}

4.1.4 Delete

一般删除策略只是替换删除的节点。

1.该节点为树叶节点
树叶节点可以直接删除。
2.该节点只有左/右儿子
使用左/右儿子进行替换。

3.该节点都存在左右儿子
删除策略是用其右字树的最左的节点的数据代替删除的节点

public static TreeNode delete(TreeNode node, int k) {
    if (k < node.value) {
        node.left = delete(node.left, k);
    } else if (k > node.value) {
        node.right = delete(node.right, k);
    } else if (node.left != null && node.right != null) {
        // 一般删除策略是用其右字树的最小的数据代替删除的那个节点
        TreeNode minNode = findMin(node.right);
        node.value = minNode.value;
        node.right = delete(node.right, node.value);
    } else if (node.left == null) {
        node = node.right;
    } else {
        node = node.left;
    }
    return node;
}

4.1.5 二叉树应用

如：4.99 * 1.06 + 5.99 + 6.99 * 1.06
现实中常用的表达式，称为中缀表达式。一般计算表达式使用中缀转后缀，有两种常用方法：

栈
二叉树

以二叉树为例

/**
 * @author JiHongYuan
 * @date 2021/6/18 14:34
 */
public class ExpressTree {
    public static void main(String[] args) {
        String expression = "4.99 * 1.06 + 5.99 + 6.99 * 1.06";
        List<String> stringList = SuffixCalc.infixTransformSuffix(expression);


        Stack<Node<String>> stack = new Stack<>();
        for (String str : stringList) {
            if (SuffixCalc.SymbolEnum.getSymbolEnumByString(str) != SuffixCalc.SymbolEnum.NONE) {
                Node<String> parent = new Node<>(str, stack.pop(), stack.pop());
                stack.push(parent);
            } else {
                stack.push(new Node<>(str, null, null));
            }
        }

        Node<String> root = stack.pop();
        printInorder(root);
        System.out.println();
        System.out.println(calc(root).toString());
    }

    public static <E> void printInorder(Node<E> head) {
        if (head == null) return;
        System.out.print("( ");
        printInorder(head.left);
        System.out.print(head.item + " ");
        printInorder(head.right);
        System.out.print(" ) ");
    }

    public static <E> E calc(Node<E> node) {
        if (node == null) return null;

        SuffixCalc.SymbolEnum symbol = SuffixCalc.SymbolEnum.getSymbolEnumByString(node.item.toString());

        if (symbol != SuffixCalc.SymbolEnum.NONE) {
            BigDecimal n1 = new BigDecimal(calc(node.left).toString());
            BigDecimal n2 = new BigDecimal(calc(node.right).toString());

            BigDecimal result;
            switch (symbol) {
                case ADD:
                    result = n1.add(n2);
                    break;
                case SUB:
                    result = n1.subtract(n2);
                    break;
                case MUL:
                    result = n1.multiply(n2);
                    break;
                case DIV:
                    result = n1.divide(n2);
                    break;
                default:
                    result = BigDecimal.ZERO;
            }
            node.item = (E) result.toString();
        }

        return node.item;
    }

    private static class Node<E> {
        E item;
        Node<E> left;
        Node<E> right;


        public Node(E item, Node<E> left, Node<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }


        @Override
        public String toString() {
            return "Node{" +
                    "item=" + item +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }

    }

}

4.2 AVL树

定义：AVL树是带有平衡条件的二叉查找树，每个节点的左子树和右子树的高度最多差1。
我们把必须重新平衡的节点叫做a。由于任意节点最多有两个儿子，英雌高度不平衡是，a点的两个字数的高度差2。这种不平衡的可能出现下面四种：

对a的左儿子的左树进行一次插入。
对a的左儿子的右树进行一次插入。
对a的右儿子的左树进行一次插入。
对a的右儿子的右树进行一次插入。

情形1和4是关于a点的镜像对称，而2和3是关于a点的镜像对象。因此理论上只有两个情况。

第一种情况：插入在外侧（左左、右右）使用单旋转（single rotation）。
第二种情况：插入在内侧（左右、右左）使用双旋转（double rotation）。

4.2.1 单旋转

单旋转由于查找树的特性，非常易懂。

4.2.1.1 左旋转

            5            
         /     \         
      4           8      
    /                    
  3                      
 /                       
2         

            |
            v

          5      
        /   \    
      3       8  
     / \         
    2   4

public static TreeNode singleRotateWithLeft(TreeNode k2) {
    TreeNode k1;
    k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;

    k1.height = Math.max(TreeUtil.height(k1.left), TreeUtil.height(k1.right)) + 1;
    k2.height = Math.max(TreeUtil.height(k2.left), TreeUtil.height(k2.right)) + 1;
    return k1;
}

4.2.1.2 右旋转

          5            
       /     \         
    4           8      
                  \    
                    9  
                     \ 
                      10

          |
          v

    5      
  /   \    
4       9  
       / \ 
      8   10

public static TreeNode singleRotateWithRight(TreeNode k2) {
    TreeNode k1;

    k1 = k2.right;
    k2.right = k1.left;
    k1.left = k2;

    k1.height = Math.max(TreeUtil.height(k1.left), TreeUtil.height(k1.right)) + 1;
    k2.height = Math.max(TreeUtil.height(k2.left), TreeUtil.height(k2.right)) + 1;
    return k1;
}

4.2.2 双旋转

双旋转略微复杂一点，只需要将左右、右左类型转化为情况1（即左左、右右）。

4.2.2.1 左右

            8            
         /     \         
      4           9      
    /   \                
  3       5              
           \             
            6            

            |
            v

            8            
         /     \         
      5           9      
    /   \                
  4       6              
 /                       
3                        
            |
            v

      5      
    /   \    
  4       8  
 /       / \ 
3       6   9

public static TreeNode doubleRotateWithLeft(TreeNode k3) {
     k3.left = singleRotateWithRight(k3.left);
     return singleRotateWithLeft(k3);
 }

4.2.2.2 右左

            5            
         /     \         
      4           8      
                /   \    
              6       9  
               \         
                7        
            
            |
            v

            5            
         /     \         
      4           6      
                    \    
                      8  
                     / \ 
                    7   9

            |
            v
      6      
    /   \    
  5       8  
 /       / \ 
4       7   9

public static TreeNode doubleRotateWithRight(TreeNode k3) {
    k3.right = singleRotateWithLeft(k3.right);
    return singleRotateWithRight(k3);
}

4.2.3 Insert

递归到插入的节点时，从下往下重新计算高度。
主要难点在这里，有点难理解。

public static TreeNode insert(TreeNode T, int val) {
    if (T == null) {
        T = new TreeNode(val);
    } else if (val < T.value) {
        // 插入在左边
        T.left = insert(T.left, val);

        // 找到破坏平衡的节点
        if (height(T.left) - height(T.right) == 2) {
            if (val < T.left.value) {
                // 左左条件 单旋转
                T = singleRotateWithLeft(T);
            } else {
                // 左右条件 双旋转
                T = doubleRotateWithLeft(T);
            }
        }
    } else if (val > T.value) {
        T.right = insert(T.right, val);
        if (height(T.right) - height(T.left) == 2) {
            if (val > T.right.value) {
                T = singleRotateWithRight(T);
            } else {
                T = doubleRotateWithRight(T);
            }
        }
    }
    // 重新计算节点高度
    T.height = Math.max(height(T.left), height(T.right)) + 1;
    return T;
}

4.2.4 样例

/**
 * @author JiHongYuan
 * @date 2021/6/17 17:51
 */
public class AvlTree<E extends Comparable<E>> {
    Node<E> root;

    private static class Node<E> {
        E item;
        int height;
        Node<E> left;
        Node<E> right;


        public Node(E item, Node<E> left, Node<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }


        @Override
        public String toString() {
            return "Node{" +
                    "item=" + item +
                    ", height=" + height +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public int height(Node<E> node) {
        if (node == null) {
            return -1;
        }
        return node.height;
    }

    public boolean add(E e) {
        root = insert(root, e);
        return true;
    }

    public Node<E> get(E item) {
        return node(root, item);
    }

    /**
     * return specified element item.
     */
    Node<E> node(Node<E> node, E item) {
        if (item.compareTo(node.item) < 0) {
            return node(node.left, item);
        } else if (item.compareTo(node.item) > 0) {
            return node(node.right, item);
        } else {
            return node;
        }
    }

    private Node<E> singleRotateWithLeft(Node<E> k2) {
        Node<E> k1;
        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        return k1;
    }

    private Node<E> singleRotateWithRight(Node<E> k2) {
        Node<E> k1;

        k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;

        k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        return k1;
    }

    private Node<E> doubleRotateWithLeft(Node<E> k3) {
        k3.left = singleRotateWithRight(k3.left);
        return singleRotateWithLeft(k3);
    }

    private Node<E> doubleRotateWithRight(Node<E> k3) {
        k3.right = singleRotateWithLeft(k3.right);
        return singleRotateWithRight(k3);
    }

    private Node<E> insert(Node<E> node, E item) {
        if (node == null) {
            node = new Node<>(item, null, null);
        } else if (item.compareTo(node.item) < 0) {
            // 插入在左边
            node.left = insert(node.left, item);

            // 找到破坏平衡的节点
            if (height(node.left) - height(node.right) == 2) {
                if (item.compareTo(node.left.item) < 0) {
                    // 左左条件 单旋转
                    node = singleRotateWithLeft(node);
                } else {
                    // 左右条件 双旋转
                    node = doubleRotateWithLeft(node);
                }
            }
        } else if (item.compareTo(node.item) > 0) {
            node.right = insert(node.right, item);
            if (height(node.right) - height(node.left) == 2) {
                if (item.compareTo(node.right.item) > 0) {
                    node = singleRotateWithRight(node);
                } else {
                    node = doubleRotateWithRight(node);
                }
            }
        }
        // 重新计算节点高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        return node;
    }

    private static void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.item);

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }

    // 用于获得树的层数
    private int getTreeDepth(Node<E> root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }

    public void show() {
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
            
        }
    }
}


/**
 * @author JiHongYuan
 * @date 2021/6/17 18:24
 */
public class AvlTreeTest {
  public static void main(String[] args) {
    AvlTree<Integer> avlTree = new AvlTree<>();

    Integer[] integers = {5, 4, 6, 7, 8, 11};
    for (Integer integer : integers) {
      avlTree.add(integer);
    }
    avlTree.show();

    System.out.println(avlTree.get(5));
    avlTree.show();

  }
}

天不错啊

数据结构与算法树.md