填空

一、散列查找

1.哈希查找：

计算哈希地址→构建表（链地址法或者开放定址法）→统计查找长度

• 哈希函数：题目给出 H(k) = k mod 11（地址范围 0~10）；

• 解决冲突方式：

  • 链地址法→竖着画（同一地址的关键字按顺序连成链表，新冲突元素默认插在链表尾部，除非题目指定头部）；
  • 开放定址法→横着画（看是线性探测还是二次探测）

• 查找成功的平均查找长度ASL = 所有关键字的查找长度之和 ÷ 关键字总数 n；

2.二叉排序树

1. 构造树：按插入顺序，依 “左小右大” 规则插节点；
2. 算深度：数根到最远叶子的层数；
3. 找指定节点：逐层定位目标层→目标位置→按 “左小右大” 找其子节点；
4. 成功 ASL：（各节点层数和）÷ 关键字数；
5. 不成功 ASL：（各失败位置路径长度和）÷（关键字数 + 1）。

3.折半查找判定树

1. 建判定树：二叉排序树进行中序遍历，会形成一个有序序列，对这个序列从0开始编号，先（0+最后一个）/2，作为根节点
   同理就可以画出折半查找判定树
2. 查找成功时的平均查找长度：（各节点层数和）÷ 关键字数

4.顺序查找长度

找第一个要1次，找第二个要2次……，所以查找成功时的平均查找长度为（1+2+…+n）/n = n+1/2

5.平衡二叉树

一个一个画，何时不平衡，就什么时候把他变成平衡（从值看谁再中间，谁提上去当根），从不平衡的地方开始到新插入点的方向数三个开始转平衡

1
2
3
4
5
6
7

  12
 /  \
1    13
       \
   	 34   
   	   \
 	    38

变为

1
2
3
4
5

  12
 /  \
1    34
    /  \
   13	 38   

例子2：

东湖高新区有10个核酸检测点，每个核酸检测点在某时段的采集样本数为{62，88，58，48，35，73，52，99，38，93}，现用下列三种方法对样本数进行查找，完成下列问题。

【注意】平均查找长度按照最简分数的形式分子/分母填写。

（1）散列查找
构建哈希表时，哈希函数为H(k)=k mod 11，采用链地址法解决冲突。请问哈希表中5号地址单元对应的链表中第一个结点对应的关键字是（ 38 ），7号地址单元对应的链表中最后一个结点对应的关键字是（ 73 ），在等概率情况下查找成功时的平均查找长度是（ 13/10 ）。
（2）动态查找
用上述样本数序列构造二叉排序树。请问二叉排序树深度为（ 5 ），第3层最右边结点的左孩子对应的关键字为（93），在等概率情况下查找成功时的平均查找长度为（31/10），在等概率情况下查找不成功时的平均查找长度为（41/11）。
（3）折半查找
对（2）中建立的二叉排序树进行中序遍历，对遍历后的有序序列进行折半查找。请问折半查找判定树中第2层从左往右第1个结点的左孩子对应的关键字为（ 35），第3层从左往右第3个结点的右孩子对应的关键字为（ 73 ），在等概率情况下查找成功时的平均查找长度为（ 29/10 ）。

（1）散列查找

要求用链地址法→画出来

1

查找成功时的平均查找长度ASL=（7*1+3*2）/10

==如果是线性探测→算不成功平均查找长度==

• 举个例子：画出来是这样子的（√表示有数，×表示是空）（实际上√应该对应的是数字）

• 	√	×	√	√	√	×	√	√
  一般	2	1	4	3	2	1	4	3
  特殊（只算跟关键字——跟空不算）	1	0	3	2	1	0	3	2

• 就是空的地方开始往前算

（2）二叉排序树

1
2
3
4
5
6
7
8
9

       62
      /  \
    58    88
   /  \    \
  48   73   99
 /  \    \
35   52   93
 \
  38

• 成功 ASL：各节点层数和 =

  1	(1个*第5层+3*4+3*3+2*2+1*1)→ 31/10

• 不成功 ASL：失败位置共 11 个，路径长度和 =

  1	2个*距离为5+5*4+3*3+1*2=41，41/11

（3）折半查找判定树

第一步：获取中序遍历有序序列

二叉排序树中序遍历 = 升序序列，给定数据（62、88、58、48、35、73、52、99、38、93）的中序序列为：

35、38、48、52、58、62、73、88、93、99（共 10 个元素，索引 0~9）

第二步：构建折半查找判定树（核心规则：每次选中间元素为根）

1. 判定树构建步骤：
   • 根（第 1 层）：中间元素索引 (0+9)//2=4 → 关键字 58；
   • 左子树（根左半段 0~3）：中间索引 (0+3)//2=1 → 第 2 层左 1 结点 38；
   • 右子树（根右半段 5~9）：中间索引 (5+9)//2=7 → 第 2 层右 1 结点 88；
   • 逐层递归，最终判定树结构如下（plaintext 格式）：

1
2
3
4
5
6
7

     58（第1层）
    /   \
  38     88（第2层，左1=38）
 /  \   /  \
35  48 62   93（第3层，左3=73）
     \  \    \
      52 73   99（第4层）

第三步：解答题目问题

1. 第 2 层从左往右第 1 个结点（38）的左孩子：35；
2. 第 3 层从左往右第 3 个结点（73）的右孩子：无（或填 “不存在”，结合判定树结构，73 右子树为空，若题目要求填关键字则需确认，此处按构建结果为 “无”）；
3. 查找成功平均查找长度：(1×1 + 2×2 + 3×4 + 4×3)÷10 = (1+4+12+12)÷10=29/10。

（4）顺序查找长度

已知数据记录{1，13，12，34，38，33，27，22}，试分别用顺序查找、折半查找、二叉排序树、平衡二叉树、散列来实现查找，完成下列问题。

对上述数据序列进行顺序查找，请问在等概率情况下查找成功时的平均查找长度为（ 9/2 ）。

（5）平衡二叉树

用上述数据序列构造平衡二叉树，请问平衡二叉树中第2层从左往右第2个结点对应的关键字为（ 34），第4层最右边结点对应的关键字为（ 33 ），在等概率情况下查找成功时的平均查找长度为（ 11/4 ）。

二、图的遍历

1.深度优先搜索

从第一个开始，没访问过就从该节点开始往后访问为访问过的，到空就往回，继续向后遍历

2.深度优先生成树

由1.深度优先搜索画出，从哪开始访问的就是谁的孩子

3.广度优先遍历

从第一个开始，全部访问到，再从第一个孩子开始继续全部访问

4.广度优先生成树

由3.广度优先遍历画出

例子：

已知图的邻接表如下所示，分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树，回答下列问题。

（1）自顶点A出发的深度优先遍历序列为：（ABCDEF ）。
【注意】假如深度优先遍历序列是A，B，C，D，E，则填空时填写ABCDE即可。首尾及中间均没有空格，后面类似空格均按此方法填写。
（2）自顶点A出发的深度优先生成树中，树的高度是（ 6 ）；从顶点A到顶点F，每个顶点的度分别是（ 1-1-1-1-1-0 ）；顶点B，C，D，E，F的双亲结点分别是（ ABCDE）。
【注意】假如每个顶点的度分别是1，2，3，4，5，则填空时填写1-2-3-4-5即可，数字之间用减号(-)连接。如果各顶点的双亲结点分别是A，B，C，D，则填写ABCD即可。首尾及中间均没有空格，后面类似空格均按此方法填写。
（3）自顶点A出发的广度优先遍历序列为：（ABECDF ）。
（2）自顶点A出发的广度优先生成树中，树的高度是（ 3 ）；从顶点A到顶点F，每个顶点的度分别是（ 2-2-0-0-1-0 )；顶点B，C，D，E，F的双亲结点分别是（ABBAE )

一、深度优先生成树（DFS）

（遍历顺序：A → B → C → D → E → F）（就是竖着画下来，不用分左右）

1
2
3
4
5
6
7
8
9
10
11

A
 \
  B
   \
    C
     \
      D
     /
    E
     \
      F

二、广度优先生成树（BFS）

1
2
3
4
5
6
7

    A
   / \
  B   E
 / \	 \
C   D   F
     

三、最小生成树

1.Prim算法

• 思路：从一个顶点开始，逐步将 “与当前生成树距离最近的顶点” 加入生成树（类似 “贪心扩展顶点”）。
• 适用场景：顶点数较少、边数较多的稠密图。

2.Kruskal算法

• 思路：先将所有边按权值排序，再依次==选权值最小的边==，若加入后不形成环则保留（类似 “贪心选边”）。
• 适用场景：边数较少、顶点数较多的稀疏图。

例子

分别采用Prim算法和Kruskal算法构造下图的最小生成树，回答下列问题。

（1）采用Prim算法（从顶点1开始）构造最小生成树。第2次选择的边是（1-7 ），第3次选择的边是（ 1-2 ），第4次选择的边是（ 2-3 ），第5次选择的边是（ 2-4），第6次选择的边是（2-5 ）。
【注意】边的填写方法：将边的两个端点对应的编号用减号-连接起来。假如某次选择的边是（1，3），则需要填写1-3或者3-1。首尾及中间均没有空格，后面类似空格均按此方法填写。
（2）采用Kruskal算法构造最小生成树。第2次选择的边是（2-3 ），第3次选择的边是（1-7 ），第4次选择的边是（ 2-4 ），第5次选择的边是（ 2-5 ），第6次选择的边是（1-2 )。

四、拓扑排序（AOV）

1.拓扑序列

从做题角度

==把入度为0的写上，把从该点出发的箭头擦掉，选择一个入度为0的==

从算法角度

1. 计算各顶点的入度：
   • 入度：指向该顶点的边的数量。
   • 本题中各顶点入度：
     • A：0（无入边）；B：1（仅 A→B）；C：2（A→C、D→C）；D：1（A→D）；E：2（B→E、A→E）；F：1（D→F）；G：2（E→G、F→G）。
2. 初始化队列：将入度为 0 的顶点（本题只有 A）加入队列。
3. 循环处理队列：
   • 取出队首顶点，加入拓扑序列；
   • 删除该顶点的所有出边，同时将出边指向的顶点的入度减 1；
   • 若某顶点入度减为 0，加入队列。

2.最大拓扑序列

所有前驱事件必须出现在后继事件之前；“最大字符串” 是指每次选择 “当前入度为 0 的顶点中字典序最大的顶点”。

五、关键路径（AOE）

1.事件最早发生时间（ve）

==正向推导== （求最大）

每个事件的 ve(当前事件) = max(所有前驱事件的ve + 对应活动的持续时间)。

2.事件最迟发生时间（vl）

==反向推导== （求最小）

每个事件的 vl(当前事件) = min(所有后继事件的vl - 对应活动的持续时间)。

3.活动最早开始时间（e）

活动的最早的 = 起始的最早

4.活动最迟开始时间（l）

活动的最迟 = 终点的最迟 - 权

5.关键活动

活动的e（最早开始时间）= l（最迟开始时间）

例子：

对下图所示的AOE网，求各顶点代表的事件的最早和最迟发生时间，以及指定弧代表的活动的最早和最迟开始时间。

• 【注意】

  • 如果一个空需要填写多个整数时，按顺序将整数之间用减号( - )连接，首尾及中间均没有空格。例如某个空需要从左到右依次填写1，2，3，4，5，6共6个整数，则填写1-2-3-4-5-6即可。
  • 弧的填写方法：弧尾在前，弧头在后，中间用减号-隔开。
  • 如果一个空需要填写多条弧时，按弧尾从小到大有序，弧尾相同的弧头从小到大有序，弧之间用/分开。例如某个空需要填写6条弧，分别是<A，C>，<C，D>，<C，E>，<D，F>，<E，F>，<F，H>，则填写A-C/C-D/C-E/D-F/E-F/F-H。

  （1）将该AOE网的拓扑序列视为字符串，那么表示拓扑序列的最大字符串是（ ADGIBEHCFJ ）。
  （2）顶点B，C，D，E所代表的事件的最早发生时间依次是（ ），顶点G，H，I，J所代表的事件的最早发生时间依次是（ ）。
  （3）顶点B，C，D，E所代表的事件的最迟发生时间依次是（ ），顶点G，H，I，J所代表的事件的最迟发生时间依次是（ ）。
  （4）有向弧<B，C>，<D，G>，<E，F>所代表的活动的最早开始时间依次是（ ），有向弧<G，F>，<H，J>，<I，J>所代表的活动的最早开始时间依次是（ ）；
  （5）有向弧<B，C>，<D，G>，<E，F>所代表的活动的最迟开始时间依次是（ ），有向弧<G，F>，<H，J>，<I，J>所代表的活动的最迟开始时间依次是（ ）；
  （6）按顺序写出所有的关键活动：（ ）。

六、最短路径

1.迪杰斯特拉（Dijkstra）

把表格画出来，依次选出路径长度最短的，从改点出发，更新

例子：

对如下有向带权图，若采用迪杰斯特拉算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是( )。

答案：fde

选出一个最短的（此时就是最短路径），从该顶点出发(小的就替换)

再选一个短的

七、排序

1.希尔排序

按增量 d 分组（每组元素下标相差 d），每组内部直接插入排序，再合并。

2.快速排序

选基准，左右指针交替找 “右先找小左找大” 元素交换，最终基准归位，左≤基准、右≥基准

3.堆排序

从小到大排的话，建大根堆（父节点≥子节点）（先从上到下，从左到右画出完全二叉树，然后从底部开始调整：底部选最大跟根比，根大就不换，根小就换），再交换堆顶与堆尾，调整堆之后第二大的就是堆顶

4.基数排序

按题目给的顺序按照 “个位→十位” 逐位排序，先入桶，再按首尾相连（从下往上的顺序）的顺序进行十位上的排序。

例子

对关键字序列 { 44，9，83，97，18，44，68，20，52 } 按从小到大的顺序排序，分别写出使用以下排序方法进行排序中的关键字序列状态。（关键字序列默认从位置1开始依次往后存放）

（1）希尔排序

第一趟希尔排序（排序增量选取3）结束后，关键字68的位置是（ 4 ），第6个位置的关键字是（ 52 ）。

（2）快速排序

选择第一个关键字作为基准关键字进行快速排序，一次划分结束后，请问基准关键字左边的关键字从左到右依次为（ 20-9-18），基准关键字右边的关键字从左到右依次为（ 97-44-68-83-52）。

（3）堆排序

建立初始堆后，堆顶关键字是（ 97 ），关键字20对应结点的祖先结点（不包括关键字20对应的结点）的关键字（从上到下）是（97-52-44 ）。
第一次交换调整后，堆顶关键字是（ 83），关键字68对应结点的左孩子和右孩子结点对应的关键字分别是（ 44-9）。

（4）基数排序

第一趟分配收集后，第2个位置的关键字是（ ），关键字97的位置是（ ）。

（1）希尔排序

1. 分组：d=3，序列分 3 组（位置 1,4,7；2,5,8；3,6,9）→ 组 1 [44,97,68]、组 2 [9,18,20]、组 3 [83,44,52]；
2. 组内直接插入排序：组 1→[44,68,97]，组 2 不变，组 3→[44,52,83]；
3. 合并分组：按原位置填充各组结果→ 最终序列 [44,9,44,68,18,52,97,20,83]；
4. 查找目标：68 在位置 4，第 6 个位置是 52。

（2）快速排序

1. 初始化：low=1（基准 44）、high=9，pivot=44；
2. 右指针找比 44 小的元素（high=8→20），左指针找比 44 大的元素（low=3→83），交换后序列 [20,9,44,97,18,44,68,83,52]；
3. 重复交换：high=5→18，low=4→97，交换后 [20,9,18,44,97,44,68,83,52]；
4. 拆分左右：基准左（20,9,18），基准右（97,44,68,83,52）。

（3）堆排序

先顺序画入，再化为大根堆，再交换最小最大，再化为大根堆

1
2
3
4
5
6
7

        44
      /   \
     9     83
   /  \    / \
  97  18  44  68
 /  \    
20   52   

• 调整

1
2
3
4
5
6
7

        97
      /   \
    52     83
   /  \    / \
  44  18  44  68
 /  \    
20   9   

• 换位置（找第二大的）

1
2
3
4
5
6
7

        9
      /   \
    52     83
   /  \    / \
  44  18  44  68
 /  \    
20   97   

• 再调整

1
2
3
4
5
6
7

        83
      /   \
    52     68
   /  \    / \
  44  18  44  9
 /     
20  97   

（4）基数排序

先按个位从上往下放

如果还要第二轮，放入的顺序就是首尾相连（从下往上的顺序）：20,52,83,44,44,97,18,68,9

八、哈夫曼树

1. 初始：将所有字符视为独立叶子节点，按权值升序排序；
2. 合并：每次选权值最小的两个节点，小的放左边，左子树权值＜右子树权值，合并为新节点（新节点权值 = 两节点权值和）；
3. 替换：删除原两个节点，将新节点加入集合，重复合并步骤，直到集合只剩 1 个根节点；
4. 辅助：画完全二叉树结构图，标注各节点权值、层数，方便后续查询。

1.哈夫曼树编码

编码：根节点为第 1 层，左子树路径记 “0”，右子树记 “1”，从根到叶子的路径即为该字符的 Huffman 编码；

2.带权路径长度WPL

WPL=权值×路径长度

例子

有一份通信电文，由8个字符（A、B、C、D、E、F、G、H）组成，各字符对应的权值分别为15，9，2，6，16，3，17，14。请按照左子树取小的原则构造一颗Huffman树并回答下列问题。
（1）按要求构造的Huffman树的高度是（ 6 ）。
（2）该Huffman树的第3层有（ 2 ）个叶子结点。
（3）该Huffman树的第4层有（ 4 ）个节点。
（4）在该Huffman树中，字符F对应结点的祖先结点（不包括字符F对应的结点）的权值从上到下依次是（ 82-49-20-11-5 ）。
【注意】假如它们所对应的结点所在的层数依次是1，2，3，4，5，6，7，8，则填空时填写1-2-3-4-5-6-7-8即可，数字之间用减号(-)连接，首尾及中间均没有空格，后面类似空格均按此方法填写。
（5）在该Huffman树中，8个字符（A、B、C、D、E、F、G、H）对应结点所在的层数依次是（ 4-4-6-5-3-6-3-4 ）。
（6）字符A对应的Huffman编码是（ 111 ）。
（7）字符B对应的Huffman编码是（ 100 ）。
（8）字符C对应的Huffman编码是（ 10100 ）。
（9）字符G对应的Huffman编码是（ 01 ）。
（10）该Huffman树的带权路径长度WPL值是（ 229 ）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        82
     /      \
    /        \
   33         49
  /  \       /    \
 /    \     /      \
16(E)17(G) 20       29
          /  \     /  \
         /    \   /    \
        9(B)  11 14(H)15(A)
             /  \
            /    \
           5      6(D)
          /  \
         /    \
        2(C)  3(F)

本题构造步骤（按规则逐步合并）

初始叶子节点（权值）：C (2)、F (3)、D (6)、B (9)、H (14)、A (15)、E (16)、G (17)

1. 合并 2 和 3→新节点 5（左 2，右 3），剩余节点：5、6、9、14、15、16、17；
2. 合并 5 和 6→新节点 11（左 5，右 6），剩余节点：9、11、14、15、16、17；
3. 合并 9 和 11→新节点 20（左 9，右 11），剩余节点：14、15、16、17、20；
4. 合并 14 和 15→新节点 29（左 14，右 15），剩余节点：16、17、20、29；
5. 合并 16 和 17→新节点 33（左 16，右 17），剩余节点：20、29、33；
6. 合并 20 和 29→新节点 49（左 20，右 29），剩余节点：33、49；
7. 合并 33 和 49→根节点 82（左 33，右 49），构造完成。

Huffman 编码（左 0 右 1）

• A (15)：根→49（1）→29（1）→A（1）→编码 111；
• B (9)：根→49（1）→20（0）→B（0）→编码 100；
• C (2)：根→49（1）→20（0）→11（1）→5（0）→C（0）→编码 10100；
• G (17)：根→33（0）→G（1）→编码 01。

带权路径长度（WPL）

• 公式：WPL=Σ（字符权值 × 路径长度），路径长度 = 层数 - 1；

• 计算：

  15×3 + 9×3 + 2×5 + 6×4 + 16×2 + 3×5 + 17×2 + 14×3 = 45+27+10+24+32+15+34+42=229。

九、二叉树的遍历

求中序快捷方法：先向左到底，再往回一个，再右下到底，再回，以此类推

1.层次+中序

中序就是左根右，根据层次找到根是什么，再在中序中找到这个根，左边的就是左子树，右边的就是右子树，然后继续

2.先序+中序

先序：根左右

中序：左根右

根据先序找根，再看中序中的这个根的方位

3.中序+后序

同理

中序：左根右

后序：左右根

根据后序的最后一个找根，再看中序中这个根的方位

4.二叉树的顺序存储

顺序存储就是完全二叉树，一行一行列出来了

1
2
3
4
5
6
7
8
9

           e
      /        \
     a          f
   /   \      /   \
  _     d    _     g
 / \   / \  / \   / \
 _ _   c j  _ _   h  i
/\ /\ /
      b

十、线索二叉树

1.先序线索树

利用二叉树中闲置的空指针，记录节点在先序遍历中的前驱 / 后继节点

2.中序线索树

利用二叉树中闲置的空指针，记录节点在中序遍历中的前驱 / 后继节点

3.后序线索树

利用二叉树中闲置的空指针，记录节点在后序遍历中的前驱 / 后继节点

例子

已知一颗二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树以及先序线索二叉树，回答下列问题。
（1）该二叉树的高度是（ 5 ）。
（2）该二叉树中，结点a的左右孩子结点分别是（ bf ）。
【注意】假如结点A的左右孩子分别是a和b，则填写ab即可（如果孩子结点不存在，则指针指向为空，用数字0代替），注意大小写，首尾及中间均没有空格，后面类似空格均按此方法填写。
（3）该二叉树中，结点e的祖先结点从上到下依次是（ abd ）。
（4）该二叉树中，第4层的结点从左到右依次是（ ehi ）。
（5）该二叉树中，结点j在第（ 5 ）层。
（6）该二叉树的先序线索树中，结点c的左右指针分别指向（ bd ）。
（7）该二叉树的先序线索树中，结点d的左右指针分别指向（ ee ）。
（8）该二叉树的先序线索树中，结点g的左右指针分别指向（ hi ）。
（9）该二叉树的先序线索树中，结点i的左右指针分别指向（ hj ）。
（10）该二叉树的先序线索树中，结点j的左右指针分别指向（ i0 ）。

1
2
3
4
5
6
7
8
9

      a
   / 	\
  b  	 f
 / \ 	/
c   d  g
   /  / \
  e  h   i
       	  \
           j

能根据确定出来的二叉树写出先序序列：abcdefghij，如果指针不为空就写之前指向的元素，为空就指向先序中的对应元素

十一、树和森林

1.森林的先序+后序→构造森林

先看先序第一个，再后序中找到隔开，前面是一棵树，…结合例子看（反正就是看完后序看先序，看完先序看后序）

例子

已知一个森林的先序序列和后序序列如下，请构造出该森林，并回答下列问题。
先序序列：ABCDEFGHIJKLMNO
后序序列：CDEBFHIJGA MLONK
（1）该森林包括（ 2 ）颗树。
（2）每棵树的深度分别是（ 3-3 ）。
【注意】假如有3棵树，它们的深度按顺序依次是3，4和5，则填写3-4-5即可，数字之间用减号(-)连接，首尾及中间均没有空格，后面类似空格均按此方法填写。
（3）每棵树的度分别是（ 3-2 ）。
（4）每棵树的树根分别是（ AK ）。
【注意】假如有3棵树，它们的树根按顺序依次是A，B和C，则填写ABC即可，注意大小写，首尾及中间均没有空格，后面类似空格均按此方法填写。
（5）第1颗树的第2层的结点从左到右依次是（ BFG ）。
（6）最后1颗树的第2层的结点从左到右依次是（ LN ）。
（7）结点B，F，J，L和O的度分别是（ 3-0-0-1-0 ）。
（8）结点B的孩子结点从左到右依次是（ CDE ）。
（9）结点N的孩子结点从左到右依次是（ O ）。
（10）结点H的祖先结点从上到下依次是（ AG ）。

• 要确定两棵树：

1
2
3

	A				K
B	F	G		  L	  N
  CDE	   HIJ      M		O

• 如何确定：已知先序（第一个是根A），再看后序，因为后序是根是最后一个，说明CDEBFHIJGA是一棵树上面的（此时要把先序中有这些字母的与其他的隔开→ABCDEFGHIJ KLMNO），看A前一个是G，说明G是一个根，看向先序G后面的就是他的孩子（根后面就是孩子），再看向后序G前面的已经写了的HIJ就不看了，往前一个就是F，看向先序，F后面没有说明，F没有孩子，继续看后续……

2.森林转二叉树

左孩子右兄弟

例子

已知森林的先根序列： ABCDEFGHIJ 和后根序列： BCDAFEHJIG，
请画出森林以及对应的二叉树并回答下列问题：
（1）该森林包含（ 3 ）颗树。
（2）每棵树的深度从左到右依次为（ 2-2-3 ）。
【注意】假如有3棵树，它们的深度按顺序依次是3，4和5，则填空时填写3-4-5即可，数字之间用减号(-)连接，首尾及中间均没有空格，后面类似空格均按此方法填写。
（3）每棵树的树根按顺序依次为（ AEG ）。
【注意】假如有3棵树，它们的树根按顺序依次是A，B和C，则填空时填写ABC即可，注意大小写，首尾及中间均没有空格，后面类似空格均按此方法填写。
（4）第1棵树的树根的孩子结点从左到右依次是（ BCD ）。
（5）最后1棵树的树根的孩子结点从左到右依次是（ HI ）。
（6）该森林对应的二叉树的高度是（ 6 ）。
（7）该森林对应的二叉树的第2，3，4层的结点数分别是（ 2-3-2 ）。
（8）该森林对应的二叉树中，结点J的祖先结点从上到下依次是（ AEGHI ）。
（9）该森林对应的二叉树的后序遍历序列是（ DCBFJIHGEA ）。
（10）该森林对应的二叉树中，结点D，F，H和I的双亲结点分别是（ CEGH ）。

3.二叉树转树（森林）

左孩子右兄弟