二叉树

二叉树允许是空的（但是一般的树不允许）
二叉树每个节点至多2个孩子节点，区分左右孩子节点
二叉树的存储：直接存储每个节点的左右孩子，有时也存父亲节点

•【3】二叉树的定义及其基本性质
•【4】二叉树的孩子表示法
•【4】二叉树的遍历：前序、中序、后序遍历
•【4】完全二叉树的定义与基本性质
•【4】完全二叉树的数组表示法
•【4】二叉树的定义、构造及其遍历

前序遍历 中序遍历 后序遍历

前序遍历 中序遍历 后序遍历 与 先访问左边还是右边没有关系（一定先左边，再右边）

前序遍历：
输出自己
dfs 左子树
dfs 右子树

中序遍历：
dfs 左子树
输出自己
dfs 右子树

后序遍历：
dfs 左子树
dfs 右子树
输出自己

前序遍历 先根节点 然后左子树前序遍历 最后右子树前序遍历
中序遍历 先左子树中序遍历 然后根节点 最后右子树中序遍历
后序遍历 先左子树后序遍历 然后右子树后序遍历 最后根节点

      1
     / \
    /   \
   2     3
  / \   / \
 4   5 6   7

前序遍历：1 2 4 5 3 6 7
中序遍历：4 2 5 1 6 3 7
后序遍历：4 5 2 6 7 3 1
层序遍历：1 2 3 4 5 6 7

已知 前序遍历 和 中序遍历 可以唯一确定二叉树（也可以确定 后序遍历）
已知 后序遍历 和 中序遍历 可以唯一确定二叉树（也可以确定 前序遍历）
已知 前序遍历 和 后序遍历 不能唯一确定二叉树（如果只有一个孩子，无法确定是左孩子还是右孩子）

参考题目

P1305 新二叉树

https://www.luogu.com.cn/problem/P1305

题目描述

输入一串二叉树，输出其前序遍历。

输入格式

第一行为二叉树的节点数 nn。(1≤n≤261 \leq n \leq 26)

后面 nn 行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用 * 表示

输出格式

二叉树的前序遍历。

样例 #1

样例输入 #1
6
abc
bdi
cj*
d**
i**
j**
样例输出 #1
abdicj

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
char L[256];
char R[256];
void dfs(char c) {
	cout << c;
	if (L[c] != 0 && L[c] != '*') {
		dfs(L[c]);
	}
	if (R[c] != 0 && R[c] != '*') {
		dfs(R[c]);
	}
}
int main() {
	cin >> n;
	char x, y, z, rt;
	for (int i = 0; i < n; i++) {
		cin >> x;
		cin >> L[x];
		cin >> R[x];
		if (i == 0) {
			rt = x;
		}
	}
	dfs(rt);
	return 0;
}

题解

输入二叉树，求前序遍历

P1030 [NOIP2001 普及组] 求先序排列

https://www.luogu.com.cn/problem/P1030

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8\le 8）。

输入格式

22行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

11行，表示一棵二叉树的先序。

样例 #1

样例输入 #1
BADC
BDCA
样例输出 #1
ABCD

提示

【题目来源】

NOIP 2001 普及组第三题

参考代码

#include <bits/stdc++.h>
using namespace std;
void dfs(string in, string post) {
	if (in.size() > 0) {
		char ch = post[post.size() - 1];
		cout << ch;
		int p = in.find(ch);
		dfs(in.substr(0, p), post.substr(0, p));
		dfs(in.substr(p + 1), post.substr(p, post.size() - 1 - p));
	}
}
int main() {
	string in, post;
	cin >> in >> post;
	dfs(in, post);
}

题解

已知 后序遍历 和 中序遍历 求 前序遍历

后序的最后一个字符，一定是根节点
已知根节点，可以把中序遍历分成左右子树两段
两段递归做

P1229 遍历问题

https://www.luogu.com.cn/problem/P1229

题目描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输入格式

输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。

输出格式

输出可能的中序遍历序列的总数，结果不超过长整型数。

样例 #1

样例输入 #1
abc                           
cba
样例输出 #1
4

提示

无提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int cnt;
int main() {
	string a, b;
	cin >> a >> b;
	for (int i = 1; i < a.size(); i++) {
		for (int j = 1; j < b.size(); j++) {
			if (a[i] == b[j - 1] && a[i - 1] == b[j]) {
				cnt++;
			}
		}
	}
	cout << (1 << cnt) << endl;
}

题解

已知 前序遍历 和 后序遍历 求 中序遍历，为什么结果不唯一，有多少组解？

如果根节点 a 有左子树 b 和右子树 c
那么 前序遍历 和 后序遍历 是
a b (左子树的前序遍历) c (右子树的前序遍历)
(左子树的后序遍历) b (右子树的后序遍历) c a

前序遍历中 a 右边的字符 是 a 的左孩子
后序遍历中 a 左边的字符 是 a 的右孩子

如果 a 没有左子树 或 右子树，那么
前序遍历中 a 右边的字符 和 后序遍历中 a 左边的字符 相同
区分不出是左孩子，还是右孩子，答案需要乘以2

abc255_f Pre-order and In-order

https://atcoder.jp/contests/abc255/tasks/abc255_f
输入二叉树的 前序遍历 和 中序遍历
输出二叉树每个点的两个孩子是什么

参考代码

题解

  1. 二叉树
    1. 前序遍历 中序遍历 后序遍历
    2. 参考题目
      1. P1305 新二叉树
      2. P1030 [NOIP2001 普及组] 求先序排列
      3. P1229 遍历问题
      4. abc255_f Pre-order and In-order
≡