树

学习
字数统计: 2k   |   阅读时长≈ 9 分钟

树

1. 树的遍历

  • 绕行踩点，按照深度优先搜索的顺序遍历整棵树，经过树的左侧时记录，得到的是先序遍历序列，经过树的下方时记录，得到的是中序遍历序列，经过数的右侧”🔺”时记录，得到的是后序遍历序列。

image-20240304151152074

image-20240304151653655

  • 若输入 $(0,0)$ 表示叶子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 用左右孩子节点表示法

const int N=1e6+5;

struct Node {
	int l;
	int r;
}node[N];

void pre_Order(int root) {
	cout<<root<<' ';
	if(node[root].l!=0) pre_Order(node[root].l);
	if(node[root].r!=0) pre_Order(node[root].r);
}

void in_Order(int root) {
	if(node[root].l!=0) in_Order(node[root].l);
	cout<<root<<' ';
	if(node[root].r!=0) in_Order(node[root].r);
}

void post_Order(int root) {
	if(node[root].l!=0) post_Order(node[root].l);
	if(node[root].r!=0) post_Order(node[root].r);
	cout<<root<<' ';
}

int main() {
	int n;
	cin>>n;
    // 输入编号1~n的左右孩子的编号
	for(int i=1;i<=n;i++) {
		int l,r;
		scanf("%d%d",&l,&r);
		node[i]={l,r}; // 编号即为值
	}
	pre_Order(1); // 前序遍历结果
	cout<<endl;
	in_Order(1); // 中序遍历结果
	cout<<endl;
	post_Order(1); // 后序遍历结果
	cout<<endl;
	return 0;
}

2. 推断二叉树

  • 已知一棵二叉树，可以确定它的四种遍历序列（前序、中序、后序、按层遍历），反过来，已知两种遍历序列，也能确定一棵二叉树。

  • 根据先序序列第一个结点确定根结点

  • 根据根结点在中序序列中的位置，分割出左子树和右子树

  • 对左子树和右子树分别递归使用相同的方法继续分解

2.1. 前序(后序)+中序→二叉树结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 输入先序序列和中序序列推断出后序序列

const int N=1e3+5;

struct Node {
	char val; 
	int l,r; // 左子树根节点编号,右子树根节点编号
}node[N];
int idx; // 建树因子
string s_pre,s_in; // 先序序列和中序序列

// 根据先序和中序建二叉树,返回树根
int create(string sp,string si) {
	int k; // 分割点
	int root=++idx;
	node[root].val=sp[0]; // 先序第一个节点作为树根
	// 找到树根在中序遍历中的位置
	for(int i=0;i<si.length();i++) {
		if(sp[0]==si[i]) {
			k=i;
			break; 
		} 
	}
	// 确定左右子树序列的长度
	int len_l=k,len_r=si.length()-1-k;
	// 序列长度>0,建立根节点的左子树,并递归对左子树按照先序和中序递归求解
	// 注意对sp和si都取相同的字符串长度
	// 先序遍历中,根节点总是在最前面,所以对sp跳过根节点
	// 中序遍历中,左子树总是在根节点之前,所以不需要跳过任何节点
	if(len_l>0) {
		node[root].l=create(sp.substr(1,len_l),si.substr(0,len_l));
	} 
	if(len_r>0) {
		node[root].r=create(sp.substr(k+1,len_r),si.substr(k+1,len_r));
	}
	return root; // 返回头结点编号
}

// 后序遍历
void postOrder(int root) {
	if(root!=0) {
		postOrder(node[root].l);
		postOrder(node[root].r);
		cout<<node[root].val;
	}
}

// 如果想按层遍历,则用BFS
void bfs(int root) {
	if(root==0) return;
	queue<int> q;
	q.push(root);
	while(q.size()) {
		int x=q.front();
		q.pop();
//		cout<<x<<' '; // 若输出编号
		cout<<node[x].val<<' ';
		if(node[x].l!=0) q.push(node[x].l);
		if(node[x].r!=0) q.push(node[x].r);
	}
}

int main() {
	cin>>s_pre>>s_in;
	int root=create(s_pre,s_in);
	postOrder(root); // 输出后续遍历结果
	cout<<endl;
	bfs(root); // 输出按层遍历的结果
	return 0;
}
/*
样例输入:
abdec
dbeac
*/

2.2. 按层遍历+中序→二叉树结构

  • 按层遍历比较特殊，因为是按层，一般用广搜实现，下面这段代码的技巧在于，新开一种数据类型用于存储将中序遍历按照按层遍历中找到的根节点的信息，存储的信息包括这个待分解的中序遍历序列以及其根节点所在的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 解题思路: 将按层遍历的序列按照中序遍历序列分解那么排在前面的一定是根节点
// 但是按照常规算法来做时间复杂度会变成O(n²),介绍下面这种做法

const int N=1e2+5;

// 额外开一个数据结构来存储按层遍历结果将中序遍历分成的每段中序遍历序列的信息
struct QNode {
	string s_in; // 中序遍历序列
	int idx; // 该中序遍历序列对应的子树的根节点编号
	QNode(){}
	QNode(string a,int b):s_in(a),idx(b){} // 构造方法
};
struct Node {
	char val;
	int l,r;
}node[N];

string s_in,s_lev; // 中序遍历序列和层次遍历序列
int cnt; // 建树因子
int lev_i; // s_lev的下标

void createTree() {
	queue<QNode> q;
	int k; // 分割点
	q.push(QNode(s_in,++cnt)); // 根节点地址为1
	while(q.size()) {
		QNode u=q.front();
		q.pop();
		// 寻找中序遍历序列中根节点(根据层遍历)元素的下标
		for(int i=0;i<u.s_in.length();i++) {
			// lev_i从0开始
			if(u.s_in[i]==s_lev[lev_i]) {
				k=i;
				break;
			}
		}	
		// 这里可以手动模拟一下,更清晰
		node[u.idx].val=s_lev[lev_i++]; // 下一次在层次遍历中看下一个字符
		string sl=u.s_in.substr(0,k),sr=u.s_in.substr(k+1); // 左子树的中序遍历序列,右子树的中序遍历序列
		// 存在左子树,建树
		if(sl.length()>0) {
			int lroot=++cnt; // 根节点分配编号
			node[u.idx].l=lroot;
			q.push(QNode(sl,lroot)); // sl是中序遍历序列,lroot是该中序遍历序列的根节点
		}
		if(sr.length()>0) {
			int rroot=++cnt;
			node[u.idx].r=rroot;
			q.push(QNode(sr,rroot));
		}
	}
}

// 前序遍历
void preOrder(int root) {
	if(root==0) return;
	cout<<node[root].val;
	preOrder(node[root].l);
	preOrder(node[root].r);
}

int main() {
	cin>>s_in>>s_lev;
	createTree();
	preOrder(1); // 输出前序
	return 0;
}
/*
输入样例:
DBEAC
ABCDE
输出样例:
ABDEC
*/

2.3. 扩展二叉树+前序(后序)→二叉树结构

  • 知道三种遍历中的其中两种可以推断出树的结构，但是用扩展二叉树标记法的时候只需要知道前序或者后序中的一种也能够推断出二叉树的结构
  • 单独知道中序遍历无论如何都无法推断出二叉树的结构
  • 下面代码的样例输入：$ABD..EF..G..C..$ 其中”.”表示的是补充的孩子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 知道扩展二叉树的先序遍历结果即可反解出中序遍历和后序遍历
// 中序遍历和后序遍历的代码简单,关键在于如何建树

const int N=1e3+5;

struct Node {
	char val;
	int l,r;
}node[N];

int idx; // 建树因子

void inOrder(int r) {
	if(r==0) return;
	inOrder(node[r].l);
	cout<<node[r].val;
	inOrder(node[r].r);	
}

void postOrder(int r) {
	if(r==0) return;
	postOrder(node[r].l);
	postOrder(node[r].r);
	cout<<node[r].val;
}

// 传入生成的二叉树的根值,返回生成的二叉树的编号
int createTree(char val) {
	if(val=='.') return 0; // 说明到根节点了,左子树/右子树建树结束
	else {
		int root=++idx;
		node[root].val=val;
		node[root].l=createTree(cin.get()); // 读取下一个字符是左子树
		node[root].r=createTree(cin.get()); // 读取下一个字符是右子树
		return root;
	}
}

int main() {
	int root=createTree(cin.get()); // 不断读取每一个字符
	inOrder(root);
	cout<<endl;
	postOrder(root);
	return 0;
}
/*
输入样例:
ABD..EF..G..C..
输出样例:
DBFEGAC
DFGEBCA
*/
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信