合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。
下续：
二、树和二叉树Ⅱ
树与二叉树Ⅰ
- 1 树基本概念
- 1.1 术语介绍
- 2 二叉树
- 2.1 二叉树的递归定义
- 2.2 简单而特殊的二叉树
- 2.2.1 满二叉树
- 2.2.2 完全二叉树
- 2.3 二叉树的存储结构与基本操作
- 2.3.1 二叉树的存储与创建
- 2.3.2 二叉树的查找与修改
- 2.3.3 二叉树插入结点与创建
- 2.3.4 完全二叉树的建立方式
- 2.4 二叉树的遍历
- 2.4.1 先序遍历
- 2.4.2 中序遍历
- 2.4.3 后序遍历
- 2.4.4 层序遍历
- 2.4.4 中序遍历和后序遍历→求先序遍历
1 树基本概念 1.1 术语介绍
1、每个元素叫节点node.
2、最顶上的节点叫树根root.
3、大树的一部分可以看作一棵小树，叫子树（一般用T来表示）.
4、连着一个结点的上一层结点叫这个点的前驱，同样地，连着它的下（后）面的点叫后继；在一棵树中，除树根之外的任一一个节点只有一个前驱，但是可以有很不多不同的后记，而树根没有前驱.
5、一个结点后继的个数被称为它的度degree，而度数为0的点叫做树叶leaf，它们处在最后一层，是光的.
6、一棵树上根节点的层次level或layer为0（有时也会是1，看题目或实际情况需要），所有结点的层次的最大值为这棵树的深度depth，也叫高度height.
7、一个结点的子树的根节点是这个结点的孩子结点，而这个结点是它的孩子结点的父亲结点，与这个结点层次相同的是它的兄弟结点；比这个结点层次高的是它的子孙结点，反之，比他层次低的是它的祖先节点.（层次高，地位低；层次低，地位高）
8、一棵子树上的任意两点都是直接或间接相邻的，也就是说，从一个结点到另一个结点都有一条路径，这个路径的长度便是两点层次之差，也就是这条路径上点的个数-1.
9、许多不相交的树组在一起便形成了森林forest，而没有结点的树叫空树.
e.g.如上图，不难发现，根结点为A（树根），A的度数为2，它的后继是B和C，点B，D和E为树叶；A与E在同一棵子树上，它们之间的路径为（A, C, E），A层次为0，E层次为2，路径上有3个点，显然，路径长度为2.
2 二叉树
多叉树存储与基本操作与二叉树类似
2.1 二叉树的递归定义递归定义详细内容如下：
#1、 二叉树没有根节点，成为一棵空树.
#2、 二叉树若不是空树，则它由树根、左子树、右子树构成 ，并且左子树与右子树也是二叉树.
重复1、2两步，直到所有分支都到了1.
如下图，A、B、C、D、E都是二叉树
叫它递归定义是因为它在用自身定义自身，就像在一个函数里调用这个函数一样；类似地，它也有一个递归边界和递归式，那么定义中，#1就是递归边界，#2是递归式.
说得再通俗一点：对于一个点，它有父亲结点，也有祖父结点，甚至于曾祖父结点；那么，按照递归定义，祖父节点就是父亲节点的父亲结点，曾祖父结点就是父亲结点的父亲结点的父亲结点；同理，它的儿子结点就是它的孙子结点的父亲结点，依此类推.
术语定义：每一层的结点个数都达到了当层能达到的最大结点数.
白话定义：满满当当，不增加层数的情况下不能再加点的树.
图E就是一棵满二叉树，但其它几个图不是.
定义：不看最后一层，这个二叉树是满二叉树；最后一层中，结点从左至右并且连续一字排开，但不要求排满；也就是说，最后一层最左边要有一个结点，最后一层的结点是连续不断的.
如图D、E是完全二叉树，但其它几个图不是.
这里，我们用链表来存储二叉树，先上代码：
struct node {
typename data; //数值域，typename为任意类型
node* lchild; //指向左子树树根的指针
node* rchild; //指向右子树树根的指针
};
node* root = NULL; //最开始是一个空树
上述结构体中，在node中又定义了node，这就是递归的体现.
上面的代码仅仅是存储的容器的类型，下面，我们就要新建一个容器，并向容器里填充树.
让我们先建立一个初始的根节点：
//生成一个新结点，v为结点权值
node* nowRoot(typename v) {
node* Node = new node; //申请一个node类型的地址空间，创建一棵树
Node->data = v; //结点权值为v
Node->lchild = Node->rchild = NULL; //初始状态下没有左右孩子
return Node; //返回新结点地址
}
这样，我们就完成了一个树根的创建，也就完成了一个树的创建.
2.3.2 二叉树的查找与修改这是新建结点的前提
先上代码：
void change(node* root, typename x, typename newdata) {
if(root == NULL) //递归边界，到空树就回溯
return;
if(root->data == x) { //找到了，改掉
root->data = newdata;
}
//递归式
search(root->lchild, x, newdata); //搜左孩子
search(root->rchild, x, newdata); //搜右孩子
}
2.3.3 二叉树插入结点与创建
先是插入结点：
//insert函数将在二叉树中插入一个数据域为X的新结点
//注意根结点指针root要使用引用，否则插入不会成功
void insert(node* &root, int x) {
//递归边界，如是碰到了树叶（死胡同），就插入
if(root == NULL) {
root = nowNode(x);
return;
}
//递归式，不停左拐右拐，确定要插入值的位置
if(x应走左子树) {
insert(root->lchild, x);
} else {
insert(root->rchild, x);
}
}
最后，将前面新建树根增合起来，调用insert插入多个结点，就完成了一棵二叉树的创建，代码如下：
node* Create(int data[], int n) {
node* root = NULL; //新建空跟结点root
for(int i = 0; i < n; i++) {
insert(root, data[i]); //将data[0]~data[n-1]插入二叉树中，data数组为需要建树的数组
}
return root; //返回根节点
}
如上图，我们就建立了一棵二叉树，建立的方式如右图所示
对于一棵完全二叉树，我们发现若一个结点编号为 x x x，则它的左子树的根结点为 2 x 2x 2x，它的右子树的根结点为 2 x + 1 2x+1 2x+1，如此一来，我们就可以用一维数组建图，并且这棵树的存放顺序就是该完全二叉树的层序遍历序列.
2.4 二叉树的遍历 2.4.1 先序遍历树根→左子树→右子树
遍历左右子树时，再按照如上方法遍历，直到遍历到空树为止，这也就形成了递归遍历.
其实，遍历也是一个递归函数，二叉树的递归边界永远是
r
o
o
t
=
=
N
U
L
L
root==NULL
root==NULL，递归式递归式如上箭头式所示，那么这个函数便水到渠成了：
void preorder(node* root) {
if(root == NULL) { //永远的递归边界
return;
}
printf("%dn", root->data);
preorder(root->lchild); //递归式
preorder(root->rchild);
}
举个例子：
对于如下一棵二叉树⬇
我们的程序按如图所示的顺序运行，绿圈表示现在看的树，红圈表示需要输出的树根.
所以，这棵树的前序遍历为ABCD.
性质：对于先序遍历，序列第一个一定是根结点
左子树→树根→右子树
遍历左右子树时，再按照如上方法遍历，直到遍历到空树为止，这也就形成了递归遍历.
其它不再赘述，代码如下:
void inorder(node* root) {
if(root == NULL) {
return;
}
preorder(root->lchild); //第6行
printf("%dn", root->data); //第7行
preorder(root->rchild); //第8行
}
中序遍历和上面的先序遍历相比，只是代码第6、7、8行颠倒一下而已，应该无须解释了，只要懂了上面的思想，这个也顺理成章了.
性质：对于中序遍历，只要知道了根结点，就可以区分左右子树.
左子树→右子树→树根
和上面两个一样：
//后序遍历
void inorder(node* root) {
if(root == NULL) {
return;
}
preorder(root->lchild);
preorder(root->rchild);
printf("%dn", root->data);
}
性质：序列最后一个一定是根节点.
2.4.4 层序遍历按层次由低到高一层一层向下遍历.
由于这种遍历是先看完这一层再看下一层的，不是一条路走到黑再画一条路，所以我们用
B
F
S
BFS
BFS来完成.
接下来是详细的步骤⬇
① 将根节点
r
o
o
t
root
root压入队列
q
q
q.
② 访问队首结点，弹掉它.
③ 若该结点存在左子树，则将其左子树的根结点压入
q
q
q.
④ 若该结点存在右子树，则将其右子树的根节点压入
q
q
q.
⑤ 返回操作②，知道
q
q
q为空.
有了思想，代码也终于浮出水面：
//层序遍历
void LayerOrder(node* root) {
queue q;
q.push(root);
while(!q.empty) {
node* now = q.top(); //抓到队首元素
q.pop();
printf("%dn", now->data); //找孩子
if(now->lchild != NULL)
q.push(now->lchild);
if(now->rchild != NULL)
q.push(now->rchild);
}
}
需要注意的是：代码中必须是 n o d e ∗ node* node∗而不能用 n o d e node node，因为 n o d e node node仅仅传递了一个副本
2.4.4 中序遍历和后序遍历→求先序遍历L u o g u Luogu Luogu P 1030 P1030 P1030 求先序排列
思路：利用后序遍历和中序遍历的性质，先利用后序遍历找出树根，再到中序遍历中用树根把序列裂成左子树和右子树.
A C AC AC代码：
#includeusing namespace std; void beford(string in, string after) { if(in.size() > 0) { //如果没到空树，递归边界 char ch = after[after.size()-1]; cout << ch; //抓到根并输出 int k = in.find(ch); //裂数组 beford(in.substr(0, k), after.substr(0, k)); //递归左子树 beford(in.substr(k+1), after.substr(k, in.size()-1-k)); //递归右子树 } else { return; } } signed main() { string in, after; cin >> in >> after; beford(in, after); return 0; }
3 m s / 808.00 K B 3ms/808.00KB 3ms/808.00KB.
特别要注意一下下标的问题，细节要慢慢扣.
那么已知先序、中序求后序也就异曲同工了.
L
u
o
g
u
Luogu
Luogu
P
1827
P1827
P1827 美国血统
A
C
AC
AC Code:
#includeusing namespace std; void aftord(string pre, string in) { if(pre.size() > 0) { char ch = pre[0]; int k = in.find(ch); aftord(pre.substr(1, k), in.substr(0, k)); aftord(pre.substr(k+1), in.substr(k+1)); cout << ch; } else { return; } } signed main() { string pre, in; cin >> in >> pre; aftord(pre, in); return 0; }
本文参考《信息学奥赛：一本通 C++版》、《算法笔记》;属个人知识版权，切勿以此作商务只用.
c
r
e
a
t
e
:
2022
/
7
/
28
create :2022/7/28
create:2022/7/28
u
p
d
a
t
e
:
2022
/
7
/
29
update:2022/7/29
update:2022/7/29
赠人拇指，手留余香，记得点个免费的赞再走 Q w Q QwQ QwQ.
C S D N @ z h e n g z i a o CSDN@zhengziao CSDN@zhengziao
