树

1 概念

1.1 什么是树？

树是一种数据结构，树里面的每一个节点都有一个对应的value和包含所有子节点的列表Child。

一个典型的二叉树的节点可以用如下的java代码来表示：

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

基础概念：

• 树叶：没有儿子节点，例如4567
• 根节点：没有父亲节点，例如1
• 兄弟节点：例如(2,3)，(4,5)，(6,7)
• 树的高度：根节点到树叶节点的最大值，注意一颗完全二叉树其平均深度为

1.2 二叉树的种类

1.2.1 满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。 也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

1.2.2 完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

除此之外还有二叉搜索树、AVL树、B+树等；将在后续的文章中阐述。

2 基本操作

2.1 构建树

public void buildTree(int[] tree) {
    if (tree.length == 0) throw new IllegalArgumentException();
    //用来辅助构建树
    List<Node> lists = new ArrayList<>();
    for (int i = 0; i < tree.length; ++i) {
        lists.add(new Node(tree[i]));
    }
    //只遍历到tree.length/2 - 2是因为tree.length/2 - 1在节点数量为偶数的时候没有右子节点
    for (int i = 0; i < tree.length / 2 - 1; ++i) {
        lists.get(i).left = lists.get(i * 2 + 1);
        lists.get(i).right = lists.get(i * 2 + 2);
    }
    int lastIndex = tree.length / 2 - 1;
    lists.get(lastIndex).left = lists.get(lastIndex * 2 + 1);
    if (tree.length % 2 != 0) {
        lists.get(lastIndex).right = lists.get(lastIndex * 2 + 2);
    }
    root = lists.get(0);
    System.out.println("buildTree success!!!");
}

2.2 树的遍历

树的遍历方式可以大体分为前序遍历、中序遍历、后序遍历以及层序遍历。

2.2.1 前序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。即**[根节点，左子树，右子树]**的遍历方式。

可视化请参考：图的可视化遍历

public void preOrder(Node node) {
    if (node == null) return;
    //根节点
    System.out.println(node.val);
    //左子树
    preOrder(node.left);
    //右子树
    preOrder(node.right);
}

2.2.2 中序遍历

中序遍历首先遍历左子树然后访问根节点，最后遍历右子树。即**[左子树，根节点，右子树]**的遍历方式。

可视化请参考：图的可视化遍历

public void inOrder(Node node) {
    if (node == null) return;
    //左子树
    preOrder(node.left);
    //根节点
    System.out.println(node.val);
    //右子树
    preOrder(node.right);
}

2.2.3 后序遍历

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。即**[左子树，右子树，根节点]**的遍历方式。

可视化请参考：图的可视化遍历

public void postOrder(Node node) {
    if (node == null) return;
    //左子树
    preOrder(node.left);
    //右子树
    preOrder(node.right);
    //根节点
    System.out.println(node.val);
}

2.2.4 层序遍历

前序、中序、后序遍历都是一种深度优先的遍历方式。层序遍历则作为一种广度优先遍历方式逐层的遍历树的节点。

以下图所示的完全二叉树为例，其层序遍历结果为[1,2,3,4,5,6]

核心思想：

• 首先根元素入队
• 当队列不为空的时候
  • 求当前队列的长度size
  • 依次从队列中取size个元素进行拓展，然后进入下一次迭代

public List<List<Integer>> levelOrder(Node root) {
    Deque<Node> queue = new LinkedList<>();
    queue.add(root);
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) return res;
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        while(size > 0){
            size--;
            Node node = queue.poll();
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
            list.add(node.val);
        }
        res.add(list);
    }
    return res;
}

3 应用

3.1 如何判断一棵树是否是平衡的

平衡：如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return testIsBalanced(root) != -1;
    }
    //首先获取左子树的高度，然后获取右子树的高度
    //如果相差大于1，或者说已经不满足平衡的要求了
    public int testIsBalanced(TreeNode node){
        if(node == null) return 0;
        int leftDeepth = testIsBalanced(node.left);
        int rightDeepth = testIsBalanced(node.right);
        if(Math.abs(leftDeepth - rightDeepth) > 1 || leftDeepth == -1 || rightDeepth == -1){
            return -1;
        }
        return Math.max(leftDeepth,rightDeepth) + 1;
    }
}

3.2 如何求一棵树的深度

深度：左子树的深度与右子树深度中的较大值再加一。就是以当前节点为根节点的树的深度。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

3.3 找出以xml结尾的文件

实际上操作系统以树的形式存储了文件，因此遍历文件的实质就是遍历这棵树。

/** * File file = new File("."); * 列出所有以xml结尾的文件 */public static void doListFile(File file) {    File[] files = file.listFiles();    for (File file1 : files) {        if (file1.isDirectory()) {            doListFile(file1);        } else {            if (file1.getName().split("\\.").length > 1 && file1.getName().split("\\.")[1].equals("xml")) {                System.out.println(file1.getName());            }        }    }}

3.4 判断一颗二叉树是否是对称的

class Solution {    public boolean isSymmetric(TreeNode root) {        return solve(root,root);    }    public boolean solveByRecur(TreeNode node1,TreeNode node2){        if(node1 == null && node2 == null) return true;        if(node1 == null || node2 == null) return false;        if(node1.val != node2.val) return false;        return solve(node1.left, node2.right) && solve(node1.right,node2.left);     }}

class Solution {    public boolean isSymmetric(TreeNode root) {        return check(root, root);    }    public boolean check(TreeNode u, TreeNode v) {        Queue<TreeNode> q = new LinkedList<TreeNode>();        q.offer(u);        q.offer(v);        while (!q.isEmpty()) {            u = q.poll();            v = q.poll();            if (u == null && v == null) {                continue;            }            if ((u == null || v == null) || (u.val != v.val)) {                return false;            }            q.offer(u.left);            q.offer(v.right);            q.offer(u.right);            q.offer(v.left);        }        return true;    }}