如何使用中序和后序来恢复一颗二叉树

一.什么是树

1.概念:

参考上面的结构,可以很方便的理解树的如下概念:

度:

**节点的度:**一个节点含有的子节点的个数称为该节点的度; 例如该数的度为

**树的度:**一棵树中,最大的节点的度称为树的度,

例如上图中是二叉树,因此该树的度是2,叶节点的度为0,叶节点或终端节点:度为0的节点称为叶节点;

  • 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;
  • 节点的祖先:从根到该节点所经分支上的所有节点;
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
  • 森林:由m(m>=0)棵互不相交的树的集合称为森林;
  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
  • 二叉树:每个节点最多含有两个子树的树称为二叉树;

二.树的性质

  • 性质1: 在二叉树的第i层上至多有2^(i-1)个结点(i>0)

  • 性质2: 深度为k的二叉树至多有2^k - 1个结点(k>0)

利用等比数列推出

  • 性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

  • 性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)

  • 性质5:对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)

完全二叉树

image-20231031140254652

三.树的存储与定义

链式存储

image-20231031140721578

链式存储是二叉树最直观的存储方式。
一个节点最多可以指向左右两个孩子节点,所以二叉树的每一个节点包含3部分。

  • 存储数据的data变量
  • 指向左孩子的left指针
  • 指向右孩子的right指针

N叉树存储:

其实就是每个节点最多可以有N个指针指向其他地方,这是不用left和right,使用一个List就可以了,也就是:

public class TreeNode {
    int val;
    List<TreeNode> nodes;
}

数组存储

已知父节点求子节点:

  • 左子节点:2*parent+1
  • 右子节点:2*parent+2

已知子节点求父节点:

  • 左节点求:child-1 / 2
  • 右节点求:child-2 / 2

image-20231031141051079

使用数组存储的最大不足是可能存在大量的空间浪费。例如上图中如果b分支没有,那么数组种1 3 4 位置都要空着,但是整个数组的大小仍然是7,因此很少使用数组来存储树。

四.树的遍历方式:

二叉树的遍历方式有层次遍历和深度优先遍历两种:

  • 深度优先遍历:先往深走,遇到叶子节点再往回走,深度优先又分为:
  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  • 广度优先遍历:一层一层的去遍历,一层访问完再访问下一层。

深度优先:

记住一点:前指的是中间的父节点在遍历中的顺序,只要记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序,就可以发现,访问中间节点的顺序就是所谓的遍历方式
前序遍历:中左右
中序遍历:左中右
后序遍历:左右中

image-20231031142443088

五. 通过序列构造二叉树

看三个序列:

  • 前序:1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
  • 中序:3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
  • 后序:8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

前中序列复原二叉树

第一轮:

我们知道前序第一个访问的就是根节点,所以根节点就是1。
中序遍历的特点是根节点的左子树的元素都在根节点的左侧,右子树的元素都在根节点的右侧

从中序遍历序列我们可以划分成如下结构:

中序序列划分:
[3 4 8 6 7 5 2] 1[ 10 9 11 15 13 14 12]
前序序列划分为:
1 [2 3 4 5 6 8 7 ] [9 10 11 12 13 15 14]

那这里怎么知道两个括号从哪里分开呢?是参照中序的两个数组划分的。

前序划分:

我们看到前序中7之前的元素都在中序第一个数组中,9之后的所有元素就在第二个数组种,所以我们从7和9之间划分。

image-20231031192617165

第二轮:

我们先看两个序列的第一个数组:

前序:2 3 4 5 6 8 7

中序:3 4 8 6 7 5 2

可以知道这里的数字都是根节点左边的数.通过第一轮的规律进行划分:

前序:2 [3 4 5 6 8 7 ]
中序:[3 4 8 6 7 5 ] 2

因此此时的树结构:

image-20231031193003416

第三轮:

同理:对 3 4 5 6 8 7 继续划分:前序:3 [4 5 6 8 7 ] 中序:3 [4 8 6 7 5 ]此时结构为:

image-20231031193401755

第四轮:

前序:[4 5 6 8 7 ]

中序:[4 8 6 7 5 ]

得到:

image-20231031193636864

此时为:

5,6,8,7和 8,6,7,5继续划分:

得到:前序:5 [6 8 7 ] 中序:[8 6 7 ] 5

最终得到:

image-20231031194019874

image-20231031195843181

中序和后序恢复二叉树:

通过中序和后序也能恢复原始序列的,唯一的不同是后序序列的最后一个是根节点,中序的处理也是上面一样的过程:

  • 前序:1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
  • 中序:3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
  • 后序:8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

问题:为什么前序和后序不能恢复二叉树

通过前序和后序列,哪些属于左子树,哪些属于右子树呢?很明显通过两个序列都不知道,所以前序和后序序列不能恢复二叉树。

遗留问题:

如果将上述过程用代码实现该怎么做呢?通过前序和中序构造树就是LeetCode105题,通过中序和后序构造树就是LeetCode106题,