[数据结构与算法]二叉树的前序遍历、中序遍历、后续遍历和层序遍历

题目

L2-004 这是二叉搜索树吗？ (25 分)

L2-006 树的遍历 (25 分)

L2-011 玩转二叉树 (25 分)

L2-035 完全二叉树的层序遍历 (25 分)

L3-010 是否完全二叉搜索树 (30 分)

代码

L2-004 这是二叉搜索树吗？ (25 分)

// https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192
#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int n, a[N];
vector <int> v;

void dfs (int l, int r, int mir) {
	if (l > r) return ;
	int rt = a[l];
	int p = l+1, q = l+1;
	if (!mir) { // 非镜像
		while (p <= r && a[p] < rt) p ++, q ++; // 找到第一个大于等于根节点的，也就是右子树的开头
		while (q <= r && a[q] >= rt) q ++; // 找到右子树的结尾的后一个
	} else {
		while (p <= r && a[p] >= rt) p ++, q ++;
		while (q <= r && a[q] < rt) q ++;
	}
	dfs (l+1, p-1, mir);
	dfs (p, q-1, mir);
	v.push_back (rt); // 直接按照后续遍历的顺序保存；先dfs左右子树后再将根节点加入v中；如果中序遍历，只需要改变push_back语句与dfs语句的次序即可
}

void print () {
	puts ("YES");
	cout << v[0];
	for (int i = 1;i < v.size();i ++)
		cout << ' ' << v[i];
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	
	dfs (1, n, 0);
	
	if (v.size () == n) { // 如果v中包含了n个元素，说明n个数全部加入
		print ();
		return 0;
	}
	
	v.clear ();
	dfs (1, n, 1);
	
	if (v.size() == n) print ();
	else puts ("NO");

	return 0;
}

L2-006 树的遍历 (25 分)

题解

#include<bits/stdc++.h>
using namespace std;

vector <int> v;

int a[50], b[50], n, left_val[50], right_val[50]; // left_val[x] 表示值为x的根左子树树根的值 

int dfs (int l1, int r1, int l2, int r2) { // 记忆化搜索 // [l1,r1]表示递归的后序遍历序列的索引范围，[l2,r2]表示递归的中序遍历的索引范围 
	
	if (l1 > r1 || l2 > r2) return 0; // 递归边界 
	
	int root = a[r1], p = l2;	
	while (p <= r2) { // 找到中序遍历中根所在的索引 
		if (b[p] == root) break;
		p ++;
	}
	int left_sum = p - l2; // 左子树节点数 
	left_val[root] = dfs (l1, l1+left_sum-1, l2, p-1); // left_subtree // [l1, l1+left_sum-1] 表示后序遍历序列中左子树的索引范围
	right_val[root] = dfs (l1+left_sum, r1-1, p+1, r2); // right_subtree
	return root;
}

void bfs (int x) {
	queue <int> q;
	q.push (x);
	while (q.size ()) {
		int t = q.front ();
		q.pop ();
		v.push_back (t);
		if (left_val[t]) q.push (left_val[t]);
		if (right_val[t]) q.push (right_val[t]);
	}	
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	for (int i = 1;i <= n;i ++) cin >> b[i];
	
	dfs (1, n, 1, n);
	
	bfs (a[n]);
	
	cout << v[0];
	for (int i = 1;i < v.size();i ++)
	cout << ' ' << v[i];

	return 0;
}

L2-011 玩转二叉树 (25 分)

#include<bits/stdc++.h>
using namespace std;
const int N = 50;

int n, a[N], b[N];
int right_subtree_root[N<<1], left_subtree_root[N<<1];

int dfs (int l1, int r1, int l2, int r2) {
	if (l1 > r1 || l2 > r2) return 0;
	
	int rt = b[l2];
	int p = l1;
	while (p <= r1 && a[p] != rt) p ++;
	
	right_subtree_root[rt] = dfs (l1, p-1, l2+1, l2+p-l1); // 镜像，dfs左子树，但是赋值给rt的右子树数组 
	left_subtree_root[rt] = dfs (p+1, r1, l2+p-l1+1, r2); // 前序遍历数组左子树和右子树索引范围的判定，是根据中序遍历得到左子树元素个数和右子树元素个数 
	return rt;
}

void bfs (int x) {
	vector <int> v;
	queue <int> q;
	q.push (x);
	while (q.size()) {
		int t = q.front ();
		v.push_back (t);
		q.pop ();
		if (left_subtree_root[t]) q.push (left_subtree_root[t]); // 因为在dfs时已经进行过镜像操作了，所以这里就先左子树数组再右子树数组 
		if (right_subtree_root[t]) q.push (right_subtree_root[t]);
	}
	
	cout << v[0] ;
	for (int i = 1;i < v.size();i ++) cout << ' ' << v[i];
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i]; // mid
	for (int i = 1;i <= n;i ++) cin >> b[i]; // before
	
	dfs (1, n, 1, n);
	
	bfs (b[1]);
	
	return 0;
}

L2-035 完全二叉树的层序遍历 (25 分)

充分利用了完全二叉树索引的性质，第i个节点的左孩子保存在a[2*i]中，右孩子保存在a[2*i+1]中，所以我们可以根据后续遍历递归输入。

这个方法太棒了！

#include<bits/stdc++.h>
using namespace std;
const int N = 100;

int n, tree[N];

void build (int x) {
	if (x > n) return ; 
	build (x << 1);
	build (x << 1 | 1);
	cin >> tree[x];
}

int main()
{
	cin >> n;
	build (1);	
	cout << tree[1];
	for (int i = 2;i <= n;i ++)
	cout << ' ' << tree[i];
	return 0;
}

我写的：（繁琐）

只要思想就是递归确定左子树和右子树元素个数，左子树元素个数就是左子树完美时的元素个数-左子树缺少的元素个数，缺少的元素个数主要看根节点的右子树，也就是该左子树的兄弟子树，如果整个树缺少元素的个数大于右子树完美时最后一层的元素个数，说明左子树也缺少元素了，缺少的元素个数就是二者的差值。

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
vector <int> v;
queue <int> q;
int n, a[N];
int left_subtree_root[N<<1], right_subtree_root[N<<1];

int dfs (int l, int r) {
	if (l > r) return 0;
	
	int num = r-l+1;
	int dp = int (log2(num)); // 从0开始
	int lack = (1 << (dp+1)) - 1 - num; // 相较于完美二叉树，此完全二叉树最后一层缺多少个节点
	int last_layer_num = (1<<dp); // 深度为dp的树的最后一层最多元素个数 
	int left_subtree_num = (1<<dp) - 1 - max (0, lack - last_layer_num/2); // 该子树的左子树元素个数 
	
	left_subtree_root[r] = dfs (l, l + left_subtree_num - 1);
	right_subtree_root[r] = dfs (l + left_subtree_num, r-1); 
	return r;
}

void layer_order (int x) {
	q.push (x);
	while (q.size()) {
		int t = q.front ();
		q.pop ();
		v.push_back (a[t]);
		if (left_subtree_root[t]) q.push(left_subtree_root[t]);
		if (right_subtree_root[t]) q.push(right_subtree_root[t]);
	}
	
	cout << v[0];
	for (int i = 1;i < v.size();i ++)
		cout << ' ' << v[i];
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	
	dfs (1, n);
	
//	for (int i = 1;i <= n;i ++) cout << left_subtree_root[i] << ' ' <<right_subtree_root[i] << endl;
	
	layer_order (n);
	
	return 0;
}

L3-010 是否完全二叉搜索树 (30 分)

搜索二叉树插入元素的过程：

1. 树空，则插入到根节点位置；
2. 树非空，与根节点比较，如果大于根节点的值则递归进入右子树，否则进入左子树。

#include<bits/stdc++.h>
using namespace std;
const int N = 100;

int n, x, cnt;
int tr[N];

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> x;
		int p = 1;
		while (tr[p] != 0) {
			if (x > tr[p]) p = (p << 1);
			else p = (p << 1 | 1);
		}
		tr[p] = x;
	}	
	
	for (int i = 1; ;i ++) {
		if (tr[i]) {
			cnt ++;
			if (cnt == 1) cout << tr[i];
			else cout << ' ' << tr[i];
		}
		if (cnt == n) {
			cout << endl;
			if (i == n) puts ("YES");
			else puts ("NO");
			return 0;
		}
	}
		
	return 0;
}