06_二叉树

树的样子

Snip20200827_4.png

树的基本概念

以下的描述都以上面多叉树为例

节点

• 节点：树上的每个元素都可以称为节点
• 根节点：树最上面的节点，一棵树最多只有一个跟节点
• 父节点： 1是2、3、4、5、6的父节点，2是21、22的父节点，22是221、222、223的父节点。
• 子节点：2、3、4、5、6是1的子节点，21、22是2的子节点，221、222、223是22的子节点。
• 兄弟节点：拥有同一个父节点 的节点称为兄弟节点
• 空树： 一棵树可以没有任何节点，称为空树
• 一棵树可以只有一个节点，也就是只有跟节点
• 子树:2及2下面的节点是1的子树
• 左子树、右子树：51是5的左子树，52是5的右子树；21是2的左子树，22及下面的节点是2的右子树
• 节点的度：子树的个数，节点1的度是5，因为它有5个子树，节点61的度是0，节点2的度是2
• 树的度：所有节点度中的最大值，上面多叉树的度是5
• 叶子节点：度为0的节点，如221、21
• 非叶子节点：度不为0的节点

层数、深度、高度

• 层数：根节点在第一层，根节点的子节点在第二层，以此类推
• 节点的深度：从根节点到当前节点的唯一路径上的节点总数，如节点2的深度是2，节点221的深度是4
• 节点的高度：从当前节点到最远叶子节点的路径上的节点总数，节点1的高度是4，节点2的高度是3
• 树的深度：所有节点深度中的最大值
• 树的高度：所有节点高度中的最大值
• 树的深度等于树的高度

有序树、无序数、森林

• 有序树：树中任意节点的子节点之间有顺序关系
• 无序数：树中任意节点的子节点之间没有顺序关系，也称” 自由树“
• 森林：由m(m>=0)颗不相交的树组成的集合

二叉树（Binary Tree）

二叉树的特点

• 每个节点的度最大为2（最多拥有2颗子树）
• 左子树和右子树是有顺序的，因此二叉树是有序树
• 即使某节点只有一棵子树，也要区分左右子树

二叉树的性质

• 非空二叉树的第i层，最多有2^(i-1）个节点（i >= 1）
• 在高度为h的二叉树上最多有2^h-1个节点（h >= 1）
• 对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有：n0 = n2 + 1;
  • 假设度为1的节点个数为n1,那么二叉树的节点总数 n = n0 + n1 + n2;
  • 二叉树的边树 T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1
  • 因此 n0 = n2 + 1;

真二叉树（Proper Binary Tree）

Snip20200827_10.png

所有节点的度要么为0，要么为2，也就是所有非叶子节点的度都为2

满二叉树（Full Binary Tree）

Snip20200827_7.png

• 最后一层节点的度都为0，其他节点的度都为2，也就是所有非叶子节点的度都为2，且所有的叶子节点都在最后一层
• 在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
• 假设二叉树的高度为h(h>=1),那么
  • 第 i 层的节点数量：2^(i-1)
  • 叶子节点数量：（2^(h-1)）
  • 总节点数量 n = 2^h - 1;
  • h = log2(n+1)

完全二叉树（Complete Binary Tree）

Snip20200827_9.png

• 完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应
• 叶子节点只会出现最后2层，最后1层的叶子节点都靠左对齐
• 完全二叉树从根节点至倒数第2层是一棵满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

完全二叉树的性质

• 度为1的节点只有左子树

• 度为1的节点要么是1个，要么是0个

• 同样节点数量的二叉树，完全二叉树的高度最小

• 假设完全二叉树的高度为h(h>=1)，那么

  • 至少有2^(h-1)个节点
  • 最多有2^h - 1 个节点
  • 假设总节点数量为n
    2^(h-1) <= n < 2^h
    h-1 <= log2(n) < h
    那么 h = floor(log2(n)) + 1 (floor是向下取整，另外ceiling是向上取整)

• 一棵有n个节点的完全二叉树（n > 0 ），从上到下、从左到右对节点从1开始进行编号，对任意第i个节点

  • 如果 i = 1 ，它是根节点
  • 如果 i > 1，它的父节点编号为 floor( i/2 )
  • 如果 2i <= n，它的左子节点编号为2i
  • 如果 2i > n ，它无左子节点
  • 如果 2i + 1 <= n， 它的右子节点编号为 2i + 1
  • 如果 2i + 1 > n ，它无右子节点

• 一棵有n个节点的完全二叉树（n > 0 ），从上到下、从左到右对节点从0开始进行编号，对任意第i个节点

  • 如果 i = 0 ，它是根节点
  • 如果 i > 0，它的父节点编号为 floor( (i-1)/2 )
  • 如果 2i + 1 <= n-1，它的左子节点编号为2i+ 1
  • 如果 2i + 1 > n - 1 ，它无左子节点
  • 如果 2i + 2 <= n - 1， 它的右子节点编号为 2i + 2
  • 如果 2i + 2 > n - 1，它无右子节点

完全二叉树面试题

如果一颗完全二叉树有768个节点，求叶子节点的个数。
解题思路：

1. 假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2
2. 总节点个数n = n0 + n1 + n2 ，而且n0 = n2 + 1，得出n = 2n0 + n1 -1
3. 又已知完全二叉树的n1要么为0，要么为1
   • n1为1时，n = 2n0，n必然是偶数，叶子节点个数n0 = n/2，非叶子节点个数 n1 + n2 = n/2
   • n1为0时，n = 2n0 - 1，n必然是奇数，叶子节点个数n0 = （n + 1）/2，非叶子节点个数 n1 + n2 = （n - 1） /2

总结：
叶子节点个数 n0 = floor((n+1)/2) = ceiling(n/2)
非叶子节点个数 n1+ n2 = floor(n/2) = ceiling( (n-1)/2)

因此叶子节点个数为384

国外教材的说法

1. Full Binary Tree ：完满二叉树，所有非叶子节点的度都为2，就是国内说的“真二叉树”
2. Perfact Binary Tree：完美二叉树，所有非叶子节点的度都为2，且所有的叶子节点都在最后一层，就是国内说的“满二叉树”
3. Complete Binary Tree：完全二叉树，跟国内的定义一样

二叉树的遍历

根据节点访问顺序的不同，二叉树的常见遍历方式有四种：

• 前序遍历
  访问顺序：根节点、前序遍历左子树、前序遍历右子树
  应用：树状结构展示

  
  Snip20200901_2.png

• 中序遍历
  访问顺序：中序遍历左子树、根节点、中序遍历右子树，二叉搜索树的中序遍历结果是生序或者是降序的
  应用：二叉搜索树的中序遍历按升序或者降序处理节点

  
  Snip20200901_8.png

• 后序遍历
  访问顺序：后序遍历左子树、后序遍历右子树、根节点
  应用：适用于一些先子后父的操作

  
  Snip20200901_11.png

• 层序遍历
  访问顺序：从上到下、从左到右依次访问每一个节点
  应用：计算二叉树的高度，判断一棵树是否为完全二叉树

  
  Snip20200901_12.png

前序遍历

    /**
     * 前序遍历_递归
     */
    public void preorderTraversal(){
        preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node){
        if (node == null) return;
        System.out.print(node.element+" ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    /**
     * 前序遍历_非递归
     */
    public void preorder(){
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node<E> node = stack.pop();
            System.out.print(node.element+" ");
            if(node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
    }

中序遍历

    /**
     * 中序遍历_递归
     */
    public void inorderTraversal(){
        inorderTraversal(root);
    }

    private void inorderTraversal(Node<E> node){
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.print(node.element+" ");
        inorderTraversal(node.right);
    }

    /**
     * 中序遍历_非递归
     */
    public void inorder(){
        if (root == null) return;
        Node<E> node = root;
        Stack<Node> stack = new Stack<>();;
        while (!stack.isEmpty() || node != null){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                Node<E> topNode = stack.pop();
                System.out.print(topNode.element+" ");
                node = topNode.right;
            }
        }
    }

后序遍历

    /**
     * 后序遍历_递归
     */
    public void postorderTraversal(){
        postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node){
        if (node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.element+" ");
    }

    /**
     * 后序遍历_非递归
     */
    public void postorder(){
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node<E> node = root;
        while (!stack.isEmpty()){
           Node<E> topNode = stack.peek();
           if ((topNode.left == null && topNode.right == null) || node.parent == topNode){
               System.out.print(stack.pop().element+" ");
               node = topNode;
           }else {
               if (topNode.right != null){
                   stack.push(topNode.right);
               }
               if (topNode.left != null){
                   stack.push(topNode.left);
               }
           }
        }
    }

层序遍历

 /**
     * 层序遍历
     */
    public void levelOrderTraversal(){
        if (root == null) return;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            System.out.print(node.element+" ");
            if (node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }

二叉树的高度

    /**
     * 树的高度
     */
    public int treeHeight(){
        if (root == null) return 0;
        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            if (levelSize == 0){
                levelSize  = queue.size();
                height++;
            }
        }
        return height;
    }

    /**
     * 树的高度_递归实现
     */
    public int treeHeight_Recurs(){
        return treeHeight_Recurs(root);
    }

    private int treeHeight_Recurs(Node<E> node){
        if (node == null) return 0;
        return 1 + Math.max(treeHeight_Recurs(node.left),treeHeight_Recurs(node.right));
    }

判断一棵树是否为完全二叉树

  /**
     * 是否是完全二叉树
     */
    public boolean isCompleteTree(){
        if (root == null) return false;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            if (leaf && (node.left != null || node.right != null)) return false;
            if (node.left != null){
                queue.offer(node.left);
            }else if(node.right != null){
                return false;
            }
            if (node.right != null){
                queue.offer(node.right);
            }else {
                leaf = true;
            }
        }
        return true;
    }

前驱节点

中序遍历时的前一个节点，如果是二叉搜索树，前驱节点就是前一个比它小的节点

Snip20200901_14.png

    /**
     * 找到前驱节点
     */
    public Node<E> predecessor(Node<E> node){
        if(node == null) return null;
        if (node.left != null){
            Node<E> leftNode = node.left;
            while (leftNode.right != null){
                leftNode = leftNode.right;
            }
            return leftNode;
        }

        while (node.parent != null && node == node.parent.left){
            node = node.parent;
        }
        return node.parent;
    }

后继节点

中序遍历时的后一个节点，如果是二叉搜索树，后继节点就是后一个比它大的节点

Snip20200901_15.png

 /**
     * 找到后继节点
     */
    public Node<E> successor(Node<E> node){
        if(node == null) return null;
        if (node.right != null){
            Node<E> rightNode = node.right;
            while (rightNode.left != null){
                rightNode = rightNode.left;
            }
            return rightNode;
        }

        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

表达式树

四则运算的表达式可以分为3种

• 前缀表达式（prefix expression），又称为波兰表达式
• 中缀表达式（infix expression）
• 后缀表达式（postfix expression），又称为逆波兰表达式

Snip20200911_6.png

如果将表达式的操作数作为叶子节点，运算符作为父节点（假设只是四则运算），这些节点刚好可以组成一棵二叉树

比如表达式：A / B + C * D - E，组成的二叉树如下：

Snip20200911_7.png

如果对这棵二叉树进行遍历

• 前序遍历，刚好就是前缀表达式
  -+/AB*CDE
• 中序遍历，刚好就是中缀表达式
  A/B+C*D-E
• 后序遍历，刚好就是后缀表达式
  AB/CD*+E-