树基础

特点

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每个非根节点有且仅有一个父节点；
• 除了根节点以外，每个子节点都可分为多个不相交的子树；

术语

• 节点的度：一个节点含有的子树的个数称为该节点的度，二叉树的度为2；
• 树的度：一棵树中，最大的节点的度称为树的度；
• 叶节点或终端节点：度为零的节点；
• 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次；
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；

分类

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
  • 二叉树：每个节点最多含有两个子树的树称为二叉树；
    • 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
    • 平衡二叉树（AVL树，红黑树是该树的一种）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树，SGI/STL的set/map底层都是用红黑树实现的；
    • 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
  • 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
  • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

二叉树的遍历

​ 二叉树的遍历分为广度优先遍历和深度优先遍历，广度优先遍历又叫层序遍历，从上往下每一层从左到右依次访问节点；深度优先遍历可细分为先序遍历、中序遍历、后续遍历；

public class TreeNode {
    int value;
    TreeNode leftNode;
    TreeNode rightNode;
}

前序遍历

对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。前序遍历的形式总是：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

public void preorder(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    System.out.println(treeNode);
    preorder(treeNode.leftNode);
    preorder(treeNode.rightNode);
}

public void preOrderDfs(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode tree = stack.pop();
        System.out.println(tree);
        if (tree.rightNode != null) {
            stack.push(tree.rightNode);
        }
        if (tree.leftNode != null) {
            stack.push(tree.leftNode);
        }
    }
}

中序遍历

对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。中序遍历的形式总是：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

public void inorder(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    inorder(treeNode.leftNode);
    System.out.println(treeNode);
    inorder(treeNode.rightNode);
}

public void inOrderDfs(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        System.out.print(root.val);
        root = root.right;
    }
}

后序遍历

对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

public void backorder(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    backorder(treeNode.leftNode);
    backorder(treeNode.rightNode);
    System.out.println(treeNode);
}

public void backOrderDfs(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        TreeNode right = null;
        while (root.right == null || root.right == right) {
            System.out.print(root.val);
            right = root;
            if (stack.isEmpty()) {
                return;
            }
            root = stack.pop();
        }
        stack.push(root);
        root = root.right;
    }
}

层序遍历|广度优先遍历

public List<Integer> bfs(TreeNode root) {
    List<Integer> lists = new ArrayList<Integer>();
    if (root == null) {
        return lists;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode tree = queue.poll();
        if (tree.leftNode != null) {
            queue.offer(tree.leftNode);
        }
        if (tree.rightNode != null) {
            queue.offer(tree.rightNode);
        }
        lists.add(tree.value);
    }
    return lists;
}

二叉树的深度

计算二叉树的深度可以通过后序遍历和层序遍历计算二叉树的深度。

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.leftNode), maxDepth(root.rightNode)) + 1;
}

public int maxDepthBfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    int maxDepth = 0;
    queue.add(root);
    while (!queue.isEmpty()) {
        maxDepth++;
        int len = queue.size();
        for (int i = 0; i < len; i++) {
            TreeNode treeNode = queue.poll();
            if (treeNode.leftNode != null) {
                queue.add(treeNode.leftNode);
            }
            if (treeNode.rightNode != null) {
                queue.add(treeNode.rightNode);
            }
        }
    }
    return maxDepth;
}

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    if (left == 0) {
        return right + 1;
    }
    if (right == 0) {
        return left + 1;
    }
    return Math.min(left, right) + 1;
}

public int minDepthBfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int minDepth = 0;
    while (!queue.isEmpty()) {
        int len = queue.size();
        for (int i = 0; i < len; i++) {
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) {
                return minDepth + 1;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        minDepth++;
    }
    return minDepth;
}

二叉树的直径

int diameter = 0;
public int diameter(TreeNode root) {
    depth(root);
    return diameter;
}

public int depth(TreeNode treeNode) {
    if (treeNode == null) {
        return 0;
    }
    int left = depth(treeNode.leftNode);
    int right = depth(treeNode.rightNode);
    diameter = Math.max(left + right, diameter);
    return Math.max(left, right) + 1;
}

镜像二叉树转换

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode tmp = root.left;
    root.left = mirrorTree(root.right);
    root.right = mirrorTree(tmp);
    return root;
}

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode treeNode = queue.poll();
        if (treeNode.right != null) {
            queue.offer(treeNode.right);
        }
        if (treeNode.left != null) {
            queue.offer(treeNode.left);
        }
        TreeNode tmp = treeNode.left;
        treeNode.left = treeNode.right;
        treeNode.right = tmp;
    }
    return root;
}

对称二叉树判断

public boolean isSymmetric(TreeNode root) {
    return check(root, root);
}

public boolean check(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null || p.val != q.val) {
        return false;
    }
    return check(p.left, q.right) && check(p.right, q.left);
}

合并二叉树

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null) {
        return t2;
    }
    if (t2 == null) {
        return t1;
    }
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
}

最长相同直径

public int longest = 0;
public int longestUnivaluePath(TreeNode root) {
    traversal(root);
    return longest;
}

public int traversal(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = traversal(root.left);
    int right = traversal(root.right);
    int arrowLeft = 0, arrowRight = 0;
    if (root.left != null && root.left.val == root.val) {
        arrowLeft += left + 1;
    }
    if (root.right != null && root.right.val == root.val) {
        arrowRight += right + 1;
    }
    longest = Math.max(longest, arrowLeft + arrowRight);
    return Math.max(arrowLeft, arrowRight);
}

最近公共祖先

根据 left 和 right ，可展开为四种情况；

• 当left和right同时为空 ：说明root的左 / 右子树中都不包含 p,q，返回 null；

• 当left和right同时不为空 ：说明 p, q分列在root的 异侧 ，因此 root为最近公共祖先，返回 root；

• 当left为空 ，right 不为空 ：p,q都不在 root的左子树中，直接返回 right。具体可分为两种情况：

  • p,q其中一个在root的 右子树中，此时right指向p；
  • p,q两节点都在 root的 右子树中，此时的 right指向最近公共祖先节点 ；

• 当 left不为空 ， right为空 同理；

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null || root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if(left == null) {
        return right;
    }
    if(right == null) {
        return left;
    }
    return root;
}

通过前序中序创建树

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) {
        return null;
    }
    Map<Integer, Integer> indexMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        indexMap.put(inorder[i], i);
    }
    return buildTrav(preorder, 0, preorder.length - 1, 0, indexMap);
}

public TreeNode buildTrav(int[] preorder, int preLeft, int preRight, int inLeft, Map<Integer, Integer> indexMap) {
    if (preLeft > preRight) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[preLeft]);
    if (preLeft == preRight) {
        return root;
    }
    int rootIndex = indexMap.get(preorder[preLeft]);
    int leftNodes = rootIndex - inLeft;
    root.left = buildTrav(preorder, preLeft + 1, leftNodes + preLeft, inLeft, indexMap);
    root.right = buildTrav(preorder, preLeft + leftNodes + 1, preRight, rootIndex + 1, indexMap);
    return root;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[0]);
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    int inorderIndex = 0;
    for (int i = 1; i < preorder.length; i++) {
        int preorderVal = preorder[i];
        TreeNode node = stack.peek();
        if (node.val != inorder[inorderIndex]) {
            node.left = new TreeNode(preorderVal);
            stack.push(node.left);
        } else {
            while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                node = stack.pop();
                inorderIndex++;
            }
            node.right = new TreeNode(preorderVal);
            stack.push(node.right);
        }
    }
    return root;
}

通过中序后序创建树

public int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null || postorder == null || inorder.length == 0 || inorder.length != postorder.length) {
        return null;
    }
    postIndex = inorder.length - 1;
    Map<Integer, Integer> indexMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        indexMap.put(inorder[i], i);
    }
    return buildTreeTrav(postorder, 0, postIndex, indexMap);
}

public TreeNode buildTreeTrav(int[] postorder, int inLeft, int inRight, Map<Integer, Integer> indexMap) {
    if (inLeft > inRight) {
        return null;
    }
    TreeNode root = new TreeNode(postorder[postIndex]);
    postIndex--;
    int rootIndex = indexMap.get(root.val);
    root.right = buildTreeTrav(postorder, rootIndex + 1, inRight, indexMap);
    root.left = buildTreeTrav(postorder, inLeft, rootIndex - 1, indexMap);
    return root;
}

通过前序后序创建树

public TreeNode constructFromPrePost(int[] pre, int[] post) {
    return constructFromPrePostTrav(pre, post, 0, 0, pre.length);
}

public TreeNode constructFromPrePostTrav(int[] pre, int[] post, int preLeft, int preRight, int N) {
    if (N == 0) {
        return null;
    }
    TreeNode root = new TreeNode(pre[preLeft]);
    if (N == 1) {
        return root;
    }
    int L = 1;
    for (; L < N; ++L) {
        if (post[preRight + L - 1] == pre[preLeft + 1]) {
            break;
        }
    }
    root.left = constructFromPrePostTrav(pre, post, preLeft + 1, preRight, L);
    root.right = constructFromPrePostTrav(pre, post, preLeft + L + 1, preRight + L, N-L-1);
    return root;
}

完全二叉树

public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int k = 0;
    while (!queue.isEmpty()) {
        int len = queue.size();
        for (int i = 0; i < len; i++) {
            TreeNode node = queue.poll();
            if (node == null) {
                k = 1;
                continue;
            }
            if (k == 1 && node != null) {
                return false;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    return true;
}

哈夫曼树

哈夫曼树的核心思想其实就是贪心算法，即利用局部最优推出全局最优，把频率出现多的用短码表示，频率出现少的就用长码表示。且任何一个字符编码都不是其他任务编码的前缀，在解压缩时，每次会读取尽可能长的可解压的二进制串，故在解压缩时也不会产生歧义。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近，给定N个权值作为N个叶子结点，构造一棵二叉树，若该树带权路径长度最小，称这样的二叉树为最优二叉树，也称为Huffman Tree哈夫曼树。若想要得到二进制编码，可将二叉分左节点的边设置为0，右节点的边设置为1。

• 每次取数值最小的两个节点，将之组成为一颗子树，可规定权值小的为左节点，权值大的为右节点
• 移除原来的两个点
• 然后将组成的子树放入原来的序列中
• 重复执行上面的步骤直到只剩最后一个点

public class HfmNode implements Comparable<HfmNode>{ // 优先队列,小的我把你优先级调高
    String chars;		//节点里面的字符
    int fre;			//表示是频率
    HfmNode left;
    HfmNode right;
    HfmNode parent;		//用来找上层的
    @Override
    public int compareTo(HfmNode o) {
        return this.fre - o.fre;
    }
}

public class HuffmenTree {
    HfmNode root;
    List<HfmNode> leafs;                // 叶子节点
    Map<Character, Integer> weights;    // 叶子节点的权重, a,b,c,d,e
    public HuffmenTree(Map<Character, Integer> weights) {
        this.weights = weights;
        leafs = new ArrayList<HfmNode>();
    }
    // 叶子节点进行编码
    public Map<Character, String> code() {
        Map<Character, String> map = new HashMap<>();
        for (HfmNode node : leafs) {
            String code = "";
            Character c = new Character(node.chars.charAt(0)); // 叶子节点肯定只有一个字符
            HfmNode current = node; // 只有一个点
            do {
                if (current.parent != null && current == current.parent.left) { // 说明当前点是左边
                    code = "0" + code;
                } else {
                    code = "1" + code;
                }
                current = current.parent;
            } while (current.parent != null); // parent == null就表示到了根节点
            map.put(c, code);
            System.out.println(c + ":" + code);
        }
        return map;
    }

    public void creatTree() {
        Character keys[] = weights.keySet().toArray(new Character[0]);            // 拿出所有的点
        PriorityQueue<HfmNode> priorityQueue = new PriorityQueue<HfmNode>();    // jdk底层的优先队列
        for (Character c : keys) {
            HfmNode hfmNode = new HfmNode();
            hfmNode.chars = c.toString();
            hfmNode.fre = weights.get(c);    // 权重
            priorityQueue.add(hfmNode);    // 首先把优先队列初始化进去
            leafs.add(hfmNode);
        }
        int len = priorityQueue.size();
        for (int i = 1; i <= len - 1; i++) {    // 每次找最小的两个点合并
            HfmNode n1 = priorityQueue.poll();
            HfmNode n2 = priorityQueue.poll();    // 每次取优先队列的前面两个 就一定是两个最小的

            HfmNode newNode = new HfmNode();
            newNode.chars = n1.chars + n2.chars;    // 把值赋值一下，也可以不复制
            newNode.fre = n1.fre + n2.fre;            // 把权重相加
            // 维护出树的结构
            newNode.left = n1;
            newNode.right = n2;
            n1.parent = newNode;
            n2.parent = newNode;
            priorityQueue.add(newNode);
        }
        root = priorityQueue.poll();    // 最后这个点就是根节点
    }

    public static void main(String[] args) {
        Map<Character, Integer> weights = new HashMap<Character, Integer>();
        weights.put('a', 3);
        weights.put('b', 24);
        weights.put('c', 6);
        weights.put('d', 1);
        weights.put('e', 34);
        weights.put('f', 4);
        weights.put('g', 12);
        HuffmenTree huffmenTree = new HuffmenTree(weights);
        huffmenTree.creatTree();
        Map<Character, String> codeMap = huffmenTree.code();
        String str = "aceg";
        System.out.println("编码后的：");
        char[] tests = str.toCharArray();
        for (char test : tests) {
            System.out.print(codeMap.get(test));
        }
    }
}

堆树

public class HeapTree {
    private int size;
    private Integer[] data;
    public HeapTree(Integer[] arr) {
        size = arr.length;
        data = new Integer[size];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == null) {
                throw new IllegalArgumentException();
            }
            data[i] = arr[i];
        }
        int len = data.length;
        // len / 2 - 1表示的是从完全二叉数中最后一个元素的父节点开始堆化
        for (int i = (len >> 1) - 1; i >= 0; i--) {    // o(nlgn)
            maxHeapDown(i, len);  // 将树中最大的元素排到堆顶
        }
    }
    public void add(Integer element) {
        if (size + 1 >= data.length) {
            grow();
        }
        int index = size++;
        if (index != 0) {
            while (index > 0) {
                int parent = index - 1 >> 1;
                Integer e = data[parent];
                if (e >= element) {
                    break;
                }
                data[index] = e;
                index = parent;
            }
            data[index] = element;
        }
    }
    public void deleteByIndex(int index) {
        if (index > size) {
            throw new IllegalArgumentException();
        }
        int last = --size;
        data[index] = data[last];
        data[last] = null;
        if (index < last) {
            maxHeapDown(index, size);
        }
    }
    private void grow() {
        int oldCapacity = data.length;
        int newCapacity = oldCapacity << 1;
        data = Arrays.copyOf(data, newCapacity);
    }
    /**
     * 将完全二叉树中最大的元素放到堆顶，end表示最多建到的点
     */
    public void maxHeapDown(int start, int end) {
        int parent = start;
        int left = (parent << 1) + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int max = left; // max表示左右节点大的那一个在数组中的位置
            if (left + 1 < end && data[left] < data[left + 1]) { // 比较左右节点和父节点的大小
                max = left + 1; // 若右节点比左节点大，则将父节点和右节点交换
            }
            // 若左节点比右节点大，则将父节点和左节点交换
            if (data[parent] > data[max]) { // 若父节点大于子节点中最大的那一个，则退出
                return;
            } else { // 若父节点小于子节点中最大的那一个，则交换
                int tmp = data[parent];
                data[parent] = data[max];
                data[max] = tmp;
                parent = max;   // 还原指针，交换数据后，max指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
                left = (parent << 1) + 1;  // 找到之前左右节点大的节点的左子节点在数组中的索引位置
            }
        }
    }
    public void minHeapDown(Integer[] arr, int start, int end) {
        int parent = start;
        int left = (start << 1) + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int min = left; // min表示左右节点小的那一个在数组中的位置
            if (left + 1 < end && arr[left] > arr[left + 1]) {
                min = left + 1;
            }
            if (arr[min] > arr[parent]) {  // 比较左右节点中小的那一个和父节点的大小
                break;  // 若小的那个节点都比父节点大，说明不需要再遍历了
            }
            int tmp = arr[min];
            arr[min] = arr[parent];
            arr[parent] = tmp;
            parent = min;   // 还原指针，交换数据后，min指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
            left = (parent << 1) + 1;  // 找到之前左右节点小的节点的左子节点在数组中的索引位置
        }
    }
}

堆树可以解决Top K问题

public class TopK {
    private final int topK = 10;
    private final int[] data = new int[topK];
    public void topK() {
        Random r = new Random();
        long time = System.currentTimeMillis();
        int size = 0;
        boolean init = false;
        for (int i = 0; i < 100000000; i++) {
            int num = r.nextInt(1000000000);
            if (size < topK) {
                data[size] = num;
                size++;
            } else {
                if (!init) { // 初始化堆，这里我们只需要初始化一次就可以了
                    for (int j = topK / 2 - 1; j >= 0; j--) {
                        minHeap(0, topK);
                    }
                    init = true;
                }
                if (num > data[0]) { // 小顶堆那么堆顶是最小的，如果当前的数比堆顶大，则替换堆顶，然后做一次堆化
                    data[0] = num;
                    minHeap(0, topK);
                }
            }
        }
        System.out.println("耗时：" + (System.currentTimeMillis() - time) + "ms");
        System.out.println(Arrays.toString(data));
    }
    public void minHeap(int start, int end) { // 构建一个小顶堆 从上往下构建
        int parent = start;
        int left = (start << 1) + 1; // 找到当前节点的左子节点位置
        while (left < end) {
            int min = left; // min表示左右节点小的那一个在数组中的位置
            if (left + 1 < end && data[left] > data[left + 1]) {
                min = left + 1;
            }
            if (data[min] > data[parent]) {  // 比较左右节点中小的那一个和父节点的大小
                break;  // 若小的那个节点都比父节点大，说明不需要再遍历了
            }
            int tmp = data[min];
            data[min] = data[parent];
            data[parent] = tmp;
            parent = min;   // 还原指针，交换数据后，min指向的是被交换下来的父节点，还需要往下遍历，故需要将parent指向需要遍历的数据
            left = (parent << 1) + 1;  // 找到之前左右节点小的节点的左子节点在数组中的索引位置
        }
    }
    public static void main(String[] args) {
        TopK topK = new TopK();
        topK.topK();
    }
}