算法知识

一、树的基本概念

一个结点的子树个数，称为这个结点的度。
树中各结点度的最大值，称为这棵树的度。

一棵树中所有的结点层次的最大值称为树的深度。

二、二叉树的概念

二叉树是一种特殊的树型结构，树中结点的度都不大于 2，它是一种最简单且最重要的树。
结点数量
在二叉树的第i层上最多有个2i-1 结点（i>=1）。
深度为k的二叉树最多有2k-1个结点（k>=1）。

满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。
完全二叉树：二叉树中除去最后一层结点为满二叉树，且最后一层的结点依次从左到右分布。需要注意的是，满二叉树也是完全二叉树。

访问顺序：访问根结点 -> 遍历左子树 -> 遍历右子树。
先序序列的第一个点是根结点。在子树的先序序列中，第一个点是该子树的根。

访问顺序：遍历左子树 -> 访问根结点 -> 遍历右子树。
步骤：
第 1 步：有左子树一直找左子树。
第 2 步：当没有左子树或左子树已经遍历完，访问根结点。
第 3 步：找右子树，重复上述步骤。
中序序列可以通过根结点划分左右子树。

访问顺序：遍历左子树 -> 遍历右子树 -> 访问根结点。
步骤：
第 1 步：有左子树一直找左子树。
第 2 步：没有左子树，找右子树，重复上述步骤。
第 3 步：当没有右子树或左右子树已经遍历完，访问根结点。
后序序列的最后一个点是根结点。在子树的后序序列中，最后一个点是该子树的根。

三、构造树【初赛向】

根据上图所示，我们可以将
先序竖着写
后序竖着倒着写
中序横向写

已知一棵二叉树的先序遍历序列为 ABCDEFHIJK，中序遍历序列为 FEDCBAHIJK。要求选择出该二叉树的后序遍历序列。
给出了四个选项：
A. FEDCBHIJKA
B. FEDCBAHIJK
C. FEDCBKJIHA
D. FEDCBJIKHA
来，开始画图

出来的图还是很容易看的，然后再说明对应的后序

【CSP2019】假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为（ ）。
a.ABCDEFGHIJ
b.ABDEGHJCFI
c.ABDEGJHCFI
d.ABDEGHJFIC
来，开始画图

出图，然后自己找后续吧