08-二叉树

• 树形结构

在前面章节中介绍到的数据结构，都为线性结构，比如链表，数组，队列等，都属于线性结构，类似于通过一根线串在一起

1569326231986.png

树形结构示意图

二叉树 多叉树

现实生活中的树，如果将现实生活中的树倒过来，就类似于树形结构

• 生活中经常用到的树形结构

1.公司的组织架构

2.平时的文件夹组织

总结：1.使用树形结构可以大大提高效率

​ 2.树形结构是算法面试的重点

• 树(Tree)的基本概念

• 节点，根节点，父节点，子节点，兄弟节点
• 一棵树可以没有任何节点，称为空树
• 一棵树可以只有一个节点，也就是只有根节点
• 子树，左子树，右子树
• 节点的度(degree):子树的个数
• 树的度：所有节点度中的最大值
• 叶子节点(leaf):度为0的节点
• 非叶子节点：度不为0的节点
• 层数(level):根节点在第一层，根节点的子节点在第二层，以此类推(有些书籍也从第0层开始计算)
• 节点的深度(depth):从根节点到当前节点的唯一路径上的节点总数
• 节点的高度(height):当从前节点到最远叶子节点的路径上的节点总数
• 树的深度:所有节点深度中的最大值
• 树的高度:所有节点高度中的最大值(一般来讲，树的深度与树的高度相等)

多叉树

• 有序树

• 树中任意节点的子节点之间有顺序关系(如上面树中，节点2,3,4,5,6是完全按照顺序排列的，如果调换位置，就变成了另外一棵树)

• 无序树

• 树种的任意节点的子节点之间没有顺序关系，也称为自由树

• 森林

• 由m(m ≥ 0)棵互不相交的树组成的集合

• 二叉树(Binary Tree)

二叉树的特点

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

二叉树有以下几种形态

1.空树

2.只有一个节点

3.只有左子树

4.只有右子树

5.右左右子树

🤔二叉树是有序树还是无序树？

• 二叉树的性质

• 非空二叉树的第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

• 真二叉树(Proper Binary Tree)

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

下图不是真二叉树

• 满二叉树(Full Binary Tree)

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

在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多

满二叉树一定是真二叉树，真二叉树不一定是满二叉树

假设满二叉树的高度为h(h ≥ 1)，那么

第i层的节点数量：2^(i - 1)

叶子节点的数量:2(h - 1)

总节点数量n: n = 2^h - 1 = 2^0 + 2^1 +2^2 + …… + 2^(h - 1)

• 完全二叉树(Complete Binary Tree)

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

完全二叉树的记忆方法：所有节点从上往下，从左往右一次排布，就位完全二叉树，如下图

如果所有节点都排满了，就叫做满二叉树

完全二叉树从根节点至倒数第二层是一个满二叉树

满二叉树一定是一棵完全二叉树，完全二叉树不一定是满二叉树

• 完全二叉树的性质

度为1的节点只有左子树

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

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

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

至少有2^(h - 1)个节点(2^0 + 2^1 + …… + 2^(h - 2) +1)

最多有2^ - 1个节点(满二叉树)

如果此时，总节点数量为n，那么有结论 2^(h -1) ≤ n ＜ 2^h

对 2^(h -1) ≤ n ＜ 2^h取对数，则有h - 1 ≤ log2n ＜ h,可以得出，h与n之间的关系为 h = log2n (向下取整) +1，即 h = floor(log2n) +1

一棵有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 + 1＞ n，它没有右子节点

• 下面的二叉树不是完全二叉树

• 面试题

如果一棵完全二叉树有768个节点，求叶子节点的个数

解题思路：

1. 假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2
2. 总结点个数 n = n0 +n1 + n2 ,而且由前面的公式知道，n0 = n2 + 1

因此有 n = 2n0 + n1 - 1

由于题目告知二叉树为完全二叉树，那么我们知道度为1的节点数量，为1或者为0，所以

• 当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) = ceilling(n / 2)

非叶子节点的数量n1 + n2 = floor(n / 2) = ceilling((n - 1) / 2)

因此最终结果为384

• 国外资料的说法

Full Binary Tree: 完满二叉树

• 所有非叶子节点的度都为2
• 也就是我们所说的"真二叉树“

Perfect Binary Tree:完美二叉树

• 所有非叶子节点的度都为2，且所有的叶子节点都在最后一层
• 也就是我们所说的"满二叉树“

Complete Binary Tree:完全二叉树

• 和我们说的一样

---

以下内容，建议阅读二叉搜索树部分后再来继续阅读

• 二叉树的遍历

遍历是数据结构中的常见操作

• 把所有元素都遍历一遍

在前面我们介绍的线性数据结构，它的遍历方法比较简单，一般是

• 正序遍历
• 逆序遍历

在二叉树遍历中，根据节点访问的顺序不同，常见的遍历方式有4种，分别为

• 前序遍历(Preorder Traversal)
• 中序遍历(Inorder Traversal)
• 后序遍历(Postorder Traversal)
• 层序遍历(Level Order Traversal)

• 前序遍历(Preorder Traversal)

例如现有如下的二叉树

访问顺序

1. 优先访问根节点，然后再前序遍历左子树，前序遍历右子树[访问顺序:下图]

• 前序遍历的代码实现

结合前面二叉搜索树的代码，我们可以在里面新增一个preorderTraversal(Node<E> node)的方法

通过递归的方式实现代码

public void  preorderTraversal(Node<E> node) {
    if (node == null) {
        return;
    }
    System.out.println(node.element);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

另外，读者可以尝试使用其他的方式进行实现。如迭代

• 中序遍历(Inorder Traversal)

访问顺序

1. 先中序遍历左子树，然后访问根节点，最后中序遍历右子树

最终的访问逻辑

由于我们当前的二叉树是一棵二叉搜索树，因此我们可以看到，如果我们使用中序遍历的方法进行遍历的话，最红遍历的结果为1,2,3,4,5,6,7,8,9,10,11,12。它们的顺序是从小到大的顺序进行遍历的

如果我们的访问顺序是：

先中序遍历右子树，然后访问根节点，最后中序遍历左子树

我们不难发现，最终的访问结果为12,11,10,9,8,7,6,5,4,3,2,1。它们的顺序是中大到小的顺序进行遍历的

因此:二叉搜索树的中序遍历结果是升序或者降序的

• 中序遍历的代码实现

我们新增一个inorderTraversal(Node<E> node)的方法

通过递归实现中序遍历的代码

public void inorderTraversal(Node<E> node) {
    if (node == null) return;
    inorderTraversal(node.left);
    System.out.println(node.element);
    inorderTraversal(node.right);
}

同样的，读者可以使用其他方式来实现

• 后序遍历(Postorder Traversal)

访问顺序

1. 先后续遍历左子树，然后后续遍历右子树，最后访问根节点

最终的访问逻辑

• 后续遍历的代码实现

我们新增一个postorderTraversal(Node<E> node)的方法

public void postorderTraversal(Node<E> node) {
    if (node == null) return;
    inorderTraversal(node.left);
    inorderTraversal(node.right);
    System.out.println(node.element);
}

• 层序遍历(Level Order Traversal)

一层一层的往下进行访问

访问顺序

1. 从上到下，从左到右依次访问每个节点

也就意味着，我们最终的访问顺序为

实现思路：使用队列

1. 将根节点入队
2. 循环执行下面的操作，直到队列为空

• 将队列头节点A出队，进行访问
• 将A的左子节点入队
• 将A的右子节点入队

• 后续遍历的代码实现

我们新增一个levelorderTraversal(Node<E> node)的方法

层序遍历的实现代码

public void levelorderTraversal() {
    if (root == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        System.out.println(node.element);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

🤔如果允许外界遍历二叉树的元素，你会如何设计接口？

因此我们可以设计一个Visitor接口，定义一个方法，让调用者自己定义元素被访问后，需要做的操作

因此4中遍历方法，改造完成后的代码是这样的

public void preOrder(Visitor<E> visitor) {}
private void preOrder(Node<E> node , Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    visitor.visit(node.element);
    preOrder(node.left,visitor);
    preOrder(node.right,visitor);
}

public void inOrder(Visitor<E> visitor) {}
private void inOrder(Node<E> node , Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    preOrder(node.left,visitor);
    visitor.visit(node.element);
    preOrder(node.right,visitor);
}

public void postOrder(Visitor<E> visitor) {}
private void postOrder(Node<E> node ,Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    preOrder(node.left,visitor);
    visitor.visit(node.element);
    preOrder(node.right,visitor);
}

public void levelOrder(Visitor<E> visitor) {
    if (root == null || visitor == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        visitor.visit(node.element);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

• 遍历的应用

前序遍历

树状结构展示(注意左右子树的顺序)

练习-利用前序遍历树状打印二叉树

中序遍历

二叉搜索树的中序遍历按照升序或者降序处理节点

后序遍历

适用于一些先子后父的操作

层序遍历

计算二叉树的高度

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

练习1:计算二叉树的高度

建议使用递归和迭代的方式实现。

递归实现方式

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

使用迭代的方式实现

public int height() {
        if (root == null) return 0;
        int height = 0;//树的高度
        int levelSize = 1;//存储着每一层元素的数量
        Queue<Node<E>> 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(root);
    }

练习2:判断一棵树是否为完全二叉树

解题思路

1. 如果树为空，返回false
2. 如果树不为空，开始层序遍历二叉树(使用队列)
   • 如果node.left != null && node.right != null ，将node.left, node.right按顺序入队
   • 如果node.left == null && node.right != null，返回false
   • 如果node.left != null && node.right == null 或者node.left == null && node.right == null
     • 那么后序遍历的节点应该都为叶子节点，才是完全二叉树
     • 否则返回false

解题源码

public boolean isComplete() {
    if (root == null) return false;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    boolean leaf = false;
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (leaf && !node.isLeaf()) return false;
        if (node.hasTwoChildren()) {
            queue.offer(node.left);
            queue.offer(node.right);
        } else if (node.left == null && node.right != null) {
            return false;
        } else {
            //意味着后遍历的节点，都必须是叶子节点
            leaf = true;
        }
    }
    return true;
}

练习3:翻转二叉树 题目来自[Leetcode]

将所有节点的左右子树都交换

由于使用了多种解题方法，因此解题源码在这里

• 根据遍历结果重构二叉树

即：根据遍历的结果，推导出该结果是哪种二叉树

通过以下结果可以保证重构出唯一的一棵二叉树

• 前序遍历结果 + 中序遍历结果
• 后序遍历结果 + 中序遍历结果

为什么根据前序遍历和中序遍历的结果，就能推导出一棵二叉树的结果

假设下图为前序遍历的结果示意图，其中红色为根节点

其中left(左子树)和right(右子树)结果，同样也是采用前序遍历

下图为中序遍历的结果示意图，其中红色为根节点

其中left(左子树)和right(右子树)结果，同样也是采用中序遍历

通过以上两个结果，我们可以知道

1. 根据前序遍历的结果，我们可以知道结果中的第一个节点为根节点
2. 找到根节点后，根据中序遍历的结果，可以找到左子树和右子树的边界，根节点左边的为左子树，根节点右边的为右子树，也就知道了哪些元素属于左子树，哪些元素属于右子树
3. 通过中序遍历的结果，已经知道了哪些元素属于左子树，哪些元素属于右子树，因此，我们在前序遍历中，就知道了哪些元素为左子树，哪些元素属于右子树
4. 已经知道了哪些节点属于哪个子树，因此前序遍历的左子树中的第一个元素，为左子树的根节点
5. 通过前序遍历中找到的左子树根节点，可以在中序遍历的左子树中，找到左子树的左子树和右子树，因为中序遍历的特点是通过根节点，将左右区分开来
6. 通过这种拆分，又可以拆分为一个规模更小的遍历结果，以此类推，谁是谁的左节点，谁是谁的右节点，谁是谁的父节点，都能拆分出来

因此通过后序遍历的结果 + 中序遍历的结果，也是同理

通过这个结论，可以尝试以下练习

通过前序遍历结果 + 中序遍历结果重构二叉树

• 前序遍历结果：4 2 1 3 6 5
• 中序遍历结果：1 2 3 4 5 6

利用前面的结论，我们知道

1. 当前二叉树的根节点为 4

   
   

2. 通过中序遍历的结果知道，该二叉树的左子树为 1 2 3 ，右子树为 5 6

3. 在通过前序遍历，就可以知道，左子树的根节点为 2，右子树的根节点为 6
4. 由于已经知道了2为左子树的根节点,那么通过中序遍历的结果,2位1 3 的父节点,1为2的左子树,3为2的右子树
5. 前面知道6位右子树的根节点,那么通过中序遍历的结果,6为 5的父节点,5在6的左边,因此5为6的左子树

🤔根据前序遍历的结果 + 后序遍历的结果,能重构出唯一的一棵二叉树吗?

• 如果是一个真二叉树,它的结果是唯一的
• 否则结果不唯一

因为有以下的情况

如果两个的遍历结果如上图所示,并且其中一个子树为空的话,就没法知道该结果为左子树的结果还是右子树的结果

如果二叉树的左右节点都不为空,遍历结果如下图

我们可以通过该结果得到以下信息

1. 首先我们可以马上确认根节点,前序遍历的结果,最前面的节点为根节点，根节点的下一个节点为左子树的根节点
2. 通过前序遍历中找到的左子树根节点，可以在后序遍历的左子树结果中找到，并且在后序遍历结果中，左子树根节点在左子树结果中的最后一位
3. 在后序遍历中，通过左子树根节点的位置，就可以知道左子树和右子树的范围，然后再通过上面的结论，就可以重构出二叉树

• 前驱节点(predecessor)

前驱节点：中序遍历时的前一个节点

• 如果是二叉搜索树，前驱节点就是前一个比它小的节点

例如有下列的二叉树

它的中序遍历结果为

节点8的前驱节点为7

因此有以下情况:

情况1

如果左子树不为空 node.left != null

例如上图二叉树中的6 13 8均符合这种情况

前驱节点predecessor = node.left.right.right.right...

终止条件为:right 为null

情况2：

node.left == null && node.parent != null

例如上图二叉树中的7 11 9 1 均符合这种情况

前驱节点predecessor = node.parent.parent.parent....

终止条件为:node的parent在右子树当中

情况3：

node.left == null && node.parent == null

这种情况的假设上图二叉树的左子树不存在，即满足以上条件

在这种情况下，是没有前驱节点的

因此查找前驱节点的实现代码是这样的

private Node<E> predecessor(Node<E> node) {
    if (node == null) return null;
    Node<E> p = node.left;
    if (node.left != null) {
        //从左子树中找前驱
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    //从父节点，祖父节点中寻找前驱节点
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }
    //node.parent == null
    //node == node.parent.right
    return node.parent;
}

• 后继节点(successor)

后继节点：中序遍历是的后一个节点

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

因此，如果有以下的一棵二叉树

通过中序遍历后的结果为

同样的，也有以下几种情况

情况1：

node.right != null

例如上图二叉树中的1 8 4均符合这种情况

successor = node.right.left.left.left....

终止条件：left == null

情况2：

node.right == null && node.parent != null

例如上图二叉树中的7 6 3 11均符合这种情况

successor = node.parent.parent.parent....

终止条件：node在parent的左子树中

情况3：

node.right = null && node.parent == null

那就没有前驱节点

例如：没有右子树的根节点

因此查找后继节点的代码是这样的

private Node<E> successor(Node<E> node) {
    if (node == null) return null;
    Node<E> p = node.right;
    if (p != null) {
        //从右子树中找前驱
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    //从父节点，祖父节点中寻找前驱节点
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }
    //node.parent == null
    //node == node.parent.right
    return node.parent;
}

GitHub地址
本节完！