一、树

树是一种非线性的数据结构。它是由 n (n >= 0)个有限结点组成的具有层级关系的集合。

xQ4WfcfI_1.png

树的概念

  1. 结点的度：一个结点含有子树的个数称为该结点的度
  2. 树的度：一棵树中，所有结点度的最大值称为树的度
  3. 叶子结点：度为 0 的结点称为叶结点
  4. 双亲结点/父节点：若一个字节含有子结点，则称这个结点为子结点的父结点
  5. 孩子结点/子结点：一个结点含有子树的根结点成为该节点的子结点
  6. 根结点：没有双亲结点的结点
  7. 结点的层次：根为第一层，根的子结点为第二层，以此类推
  8. 树的高度：树中结点的最大层次

二、二叉树

满足一下两个条件的树就是二叉树：

  1. 本身是有序树；
  2. 树中包含的各个节点的度不能超过 2

两种特殊的二叉树

  1. 满二叉树：除了叶子结点，每个结点的度都为2

xQ4WfcfI_2.gif

  1. 完全二叉树：除去最后一层结点为满二叉树，且最后一层的结点从左到右分布

xQ4WfcfI_3.gif

二叉树的性质

  1. 一棵非空二叉树的第 i 层最多有 2 ^ (i - 1) 个结点
  2. 深度为 k 的二叉树最多有 2 ^ k - 1 个结点
  3. 若二叉树结点数为奇数，则 n0 = n2 + 1；偶数则 n0 = n2
  4. 具有 n 个结点的完全二叉树深度为 log(n + 1) 向上取整
  5. 对于具有 n 个结点的完全二叉树，若按从上至下从左至右的顺序对所有结点从 0 开始编号，则对于序号为 i 的结点：
条件i = 0i > 02i + 1 < n2i + 2 < n
序号无双亲结点双亲序号：(i - 1) / 2左孩子序号：2i + 1右孩子序号：2i + 2

二叉树的遍历

  1. 前序遍历：根结点>>左子树>>右子树
  2. 中序遍历：左子树>>根结点>>右子树
  3. 后序遍历：左子树>>右子树>>根结点

递归实现：

public void preOrder(TreeNode root) { // 前序遍历
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(TreeNode root) { // 中序遍历
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public void postOrder(TreeNode root) { // 后序遍历
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

迭代实现：

二叉树的常用方法

public int size(TreeNode root) { // 获取结点个数
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    public int getLeafNodeCount(TreeNode root) { // 获取叶子结点的个数
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    
    public int getHeight(TreeNode root) { // 求二叉树高度
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
    
    public TreeNode find(TreeNode root, int val) { // 判断值是否存在
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode tmp = find(root.left, val);
        if (tmp != null) {
            return tmp;
        }
        tmp = find(root.right, val);
        if (tmp != null) {
            return tmp;
        }
        return null;
    }