【数据结构与算法】第二篇：二叉树

知识导航

• 一.二叉树预备知识
• • 1..树形结构
  • 2.树（Tree）的基本概念
  • 3.有序树、无序树
  • 4.二叉树（Binary Tree）的特点
  • 5.二叉树（Binary Tree）的性质
  • 6.真二叉树
  • 7.满二叉树
  • 8.完全二叉树（Complete Binary Tree)
  • 9.完全二叉树的性质（重点）
  • 10.基础面试题+1
• 二.遍历而二叉树
• • 1.前序遍历
  • 2.中序遍历
  • 3.后序遍历
  • 4.层序遍历(重点)
  • 5.四种遍历之间的应用比较
• 三.代码练习
• • 1.leetcode:翻转二叉树
• 四.前驱节点与后继节点
• • 1.前驱节点
  • 2.后继节点

---

一.二叉树预备知识 1…树形结构

树形结构

2.树（Tree）的基本概念

◼ 树包括：节点、根节点、父节点、子节点、兄弟节点等该概念
◼ 一棵树可以没有任何节点，称为空树
◼ 一棵树可以只有 1 个节点，也就是只有根节点
◼ 子树包括->左子树、右子树

◼ 节点的度（degree）：子树的个数
◼ 树的度：所有节点度中的最大值
◼ 叶子节点（leaf）：度为 0 的节点
◼ 非叶子节点：度不为 0 的节点

◼ 节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数(以走几步判定)
etc:Man节点的深度为2，因为从根节点(life)到该节点唯一路径需要走两步才能到达Man
◼ 节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数
etc:Man的高度为0，Animal的高度为2

◼ 树的深度：所有节点深度中的最大值
◼ 树的高度：所有节点高度中的最大值
◼ 树的深度 等于 树的高度（比如上图中树的高度=深度为3）

3.有序树、无序树

作为了解：有序，无序只是节点的排布顺序问题

◼ 有序树
树中任意节点的子节点之间有顺序关系
◼ 无序树
树中任意节点的子节点之间没有顺序关系

4.二叉树（Binary Tree）的特点

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

5.二叉树（Binary Tree）的性质

1.◼ 非空二叉树的第 i 层，最多有 2 ^i − 1 个节点（ i ≥ 1 ）
◼ 在高度为 h 的二叉树上最多有 2 ^h − 1 个结点（ h ≥ 1 ）

2.拾拾对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为 2 的节点个数为 n2，则有: n0 = n2 + 1

证明：
假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2
注：（角度一）度为1的节点对应一条边，度为二的节点对应两条边，度为0的节点不对应边---->边数：n1 + 2 * n2
（角度二）每一个节点上面都对应一条边，除了根节点所以边数：n0 + n1 + n2-1

(得出结论)二叉树的边数 T = n1 + 2 * n2 = n0 + n1 + n2 – 1
因此 n0 = n2 + 1（只要是一颗而二叉树它度为零的节点等于度为二的节点加1）

6.真二叉树

◼ 真二叉树：所有节点的度都要么为 0，要么为 2

7.满二叉树

满二叉树：所有节点的度都要么为 0，要么为 2。且所有的叶子节点都在最后一层

满二叉树=真二叉树+叶子节点都在最后一层

（1）在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
（2） 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

8.完全二叉树（Complete Binary Tree)

完全二叉树：叶子节点只会出现最后 2 层，且最后 1 层的叶子结点都靠左对齐

满二叉树也是完全二叉树的一种

（1）满二叉树一定是完全二叉树
（2）完全二叉树不一定是满二叉树
（3）完全二叉树从第一层到倒数第二层是一颗满二叉树

9.完全二叉树的性质（重点）

基本性质

度为 1 的节点只有左子树
度为 1 的节点要么是 1 个，要么是 0 个
同样节点数量的二叉树，完全二叉树的高度最小

算数性质

假设完全二叉树的高度为 h（ h ≥ 1 ），那么
至少2 ^h-1 个节点 （ 2 ⁰+ 2¹ + 2² + ⋯+ 2 ^h−2 + 1 ）
【注】：最少的情况就是树前h-2层的节点+一个左子树节点
最多有 2^h − 1 个节点（ 2 ⁰+ 2¹ + 2² + ⋯+ 2 ^h−1-1 ，满二叉树-1 ）
【注】：最多的情况就是前h层对应的满二叉树减去一个右子树节点

算数性质推导

设所有的节点数为n
有上面的结论得知2 ^h-1h-1 ,对其两边取对数，底为2
可得h-1n 所以log(2)ⁿ处于n-1到n之间距离等于1的区间
如下图所示可得出二叉树的高度=floor(log(2)ⁿ)+1;–>floor是向下取整

10.基础面试题+1

如果一棵完全二叉树有 768 个节点，求叶子节点的个数
设度为0,1,2的节点分别为n0,n1,n2
768=n0+n1+n2
n0=n2+1
所以：768=2n0+n1-1
因为是完全二叉树，所以n1为1或者0
当为1时。n0也就是叶子节点为384
当为0时。n0也就是叶子节点为384.5->显然不成立
所以叶子节点数为384

二.遍历而二叉树 1.前序遍历

前序遍历就是按照->根节点、前序遍历左子树、前序遍历右子树的顺序对二叉树进行遍历

二叉树的前序遍历题目链接

class Solution {

    public void preorderTraversal1(TreeNode root,List list){
        if(root==null) 
          return ;
        list.add(root.val);
        preorderTraversal1(root.left,list);
        preorderTraversal1(root.right,list);

    }
    public List preorderTraversal(TreeNode root) {
       List list=new ArrayList<>();
          preorderTraversal1(root,list);
          return list;
    }
}

2.中序遍历

访问顺序->后序遍历左子树、根节点、后序遍历右子树
题目链接

class Solution {
private void inorderTraversal1(TreeNode node,List list){
    if(node==null){
        return;
    }
    inorderTraversal1(node.left,list);
    list.add(node.val);
    inorderTraversal1(node.right,list);
    }
    public List inorderTraversal(TreeNode root) {
        Listlist =new LinkedList<>();
        inorderTraversal1(root,list);
        return list;
    }
}

3.后序遍历

访问顺序->后序遍历左子树、后序遍历右子树、根节点
后序遍历题目链接

class Solution {

private void postorderTraversal1(TreeNode node,List list){
if(node==null)
  {
    return;
  }
  postorderTraversal1(node.left,list);
  postorderTraversal1(node.right,list);
list.add(node.val);
}
    public List postorderTraversal(TreeNode root) {
        List list=new LinkedList<>();
        postorderTraversal1(root,list);
        return list;
    }
}

4.层序遍历(重点)

一层一层的遍历
思想：运用队列，先将根节点入队，然后只要队列列不为空则弹出对头元素，然后入队左右子树。这样可以保证队列里的恰好是每一层的元素。
题意描述

class Solution {
    public List> levelOrder(TreeNode root) {
        List> ret = new ArrayList>();
        if (root == null) {
            return ret;
        }

        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List level = new ArrayList();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

5.四种遍历之间的应用比较

◼ 前序遍历
树状结构展示（注意左右子树的顺序）
◼ 中序遍历
二叉搜索树的中序遍历按升序或者降序处理节点
◼ 后序遍历
适用于一些先子后父的操作
◼ 层序遍历
计算二叉树的高度
判断一棵树是否为完全二叉树

三.代码练习 1.leetcode:翻转二叉树

题目链接
通过层序遍历，遍历树的每一个节点，每遍历到一个节点，就将其左右子树翻转。

class Solution {
    public TreeNode invertTree(TreeNode root) {
    if(root==null){
         return null;
    }
    Queue queue=new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
            TreeNode  node=queue.poll();
            TreeNode temp=node.left;
            node.left=node.right;
            node.right=temp;
            if (node.left!=null) {
                queue.offer(node.left);
            }
            if (node.right!=null){
                queue.offer(node.right);
            }
        }
        return root;
}
}

四.前驱节点与后继节点 1.前驱节点

目标节点在中序遍历中的前一个节点
因为中序遍历是按照左子树，根节点，右子树的顺序遍历。所以目标节点的前一个节点就是左子树最后一个节点，也就是左子树最右边的节点。

ublic Node preTarget(Node node){
    if (node==null){
        return null;
    }
    Node p=node.left;
    //该节点有左子树的情况，直接找左子树的最右节点
    if (p!=null) {
        while (p.right != null) {
            //遍历左子树找到最右边的最后一个节点
            p = p.right;
        }
        return p;
    }

2.后继节点

因为中序遍历是按照左子树，根节点，右子树的顺序遍历。所以目标节点的后一个节点就是右子树最先一个节点，也就是右子树最左边的节点。
前驱节点更换左右就是后继节点的代码。

 public Node postTarget(Node node) {
        if (node==null){
            return null;
        }
        Node ps=node.right;
        //该节点有左子树的情况，直接找左子树的最右节点
        if (ps!=null) {
            while (ps.left != null) {
                //遍历左子树找到最右边的最后一个节点
                ps = ps.left;
            }
            return ps;
        }