算法知识-16-树

一、树的基本概念

度（Degree）

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

深度（Depth）

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

二、二叉树的概念

定义

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

特殊二叉树

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

二叉树的遍历方式

先序遍历（根左右）

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

中序遍历（左根右）

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

后序遍历（左右根）

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

三、构造树【初赛向】

![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/e856e782f40c4b1c9374b65a6fa6a222.png
根据上图所示，我们可以将
先序竖着写
后序竖着倒着写
中序横向写

已知中，先，求后：

已知一棵二叉树的先序遍历序列为 ABCDEFHIJK，中序遍历序列为 FEDCBAHIJK。要求选择出该二叉树的后序遍历序列。
给出了四个选项：
A. FEDCBHIJKA
B. FEDCBAHIJK
C. FEDCBKJIHA
D. FEDCBJIKHA
来，开始画图👇👇
在这里插入图片描述
出来的图还是很容易看的，然后再说明对应的后序