二叉树遍历（前序、中序、后序） UVA 548 Tree

今天复习前面的内容的时候看到一道题UVA 548 Tree，说的是输入一个二叉树中序和后序的集合，沿着二叉树的一条边走，问叶子为多少的这条路最短。

看到这道题，中序？后序？什么玩意？？？不知道，百度！查了之后会了，就回来A了这题。

先给一个二叉树

二叉树前序遍历

         前序遍历顺序可以简记为根左右

   规则：

   （1）访问根节点

   （2）前序遍历左子树

   （3）前序遍历右子树

（注：遍历过程为递归）

结果：ABCDEF

 

二叉树中序遍历

        中序遍历顺序简记为左根右

   规则：

   （1）中序遍历左子树

   （2）访问根节点

   （3）中序遍历右子树

结果：CBDAFE

 

二叉树后序遍历

        后序遍历顺序简记为左右根

   规则：

   （1）后序遍历左子树

   （2）后序遍历右子树

   （3）访问根节点

结果：CDBFEA

 

然后就以上面给出的UVA 548为例，熟悉一下这规则

#include<stdio.h>
#include<string.h>
#include<sstream>
#include<iostream>
using namespace std;
#define MAXN 10010
#define INF 0x3f3f3f3
int in_order[MAXN], post_order[MAXN], lch[MAXN], rch[MAXN];
int n,best,best_sum;

bool read(int *a)
{
	string line;
	if (!getline(cin, line))
		return false;
	stringstream ss(line);
	n = 0;
	int x;
	while (ss >> x)
		a[n++] = x;
	return n > 0;
}

int build(int L1, int R1, int L2, int R2)
//建树过程，后序遍历中，最后一个数字肯定是该层的根节点，然后在中序遍历中找到该节点
//找到节点后，中序遍历左边为左子树，右边为右子树
//后序遍历前面相对应的数量的数字为左子树，剩下的为右子树
//即 中序遍历结构 左子树-根-右子树
//   后序遍历结构 左子树-右子树-根
{
	if (L1 > R1){
		return 0;
	}
	int root = post_order[R2];
	int p = L1;
	while (in_order[p] != root)
		p++;
	int cnt = p - L1;
	lch[root] = build(L1, p - 1, L2, L2 + cnt - 1);
	rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1);
	return root;
}
void dfs(int u, int sum)
{
	sum += u;
	if (!lch[u] && !rch[u]){
		if (sum < best_sum || (sum == best_sum&&u < best))
		{
			best = u;
			best_sum = sum;
		}
	}
	if (lch[u])dfs(lch[u], sum);
	if (rch[u])dfs(rch[u], sum);
}
int main()
{
	while (read(in_order))
	{
		read(post_order);
		best_sum = INF;
		build(0, n - 1, 0, n - 1);
		dfs(post_order[n - 1], 0);
		printf("%d\n", best);

	}
	return 0;
}

另外，这段代码还能进行优化，不知道你想到没。

就是我们可以在建树的过程中同时记录最小值

#include<stdio.h>
#include<string.h>
#include<sstream>
#include<iostream>
using namespace std;
#define MAXN 10010
#define INF 0x3f3f3f3
int in_order[MAXN], post_order[MAXN], lch[MAXN], rch[MAXN];
int n, best, best_sum;

bool read(int *a)
{
	string line;
	if (!getline(cin, line))
		return false;
	stringstream ss(line);
	n = 0;
	int x;
	while (ss >> x)
		a[n++] = x;
	return n > 0;
}

int build(int L1, int R1, int L2, int R2, int sum)
{
	if (L1 > R1){
		return 0;
	}
	int root = post_order[R2];
	int p = L1;
	while (in_order[p] != root)
		p++;
	int cnt = p - L1;
	sum += root;
	lch[root] = build(L1, p - 1, L2, L2 + cnt - 1, sum);
	rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1, sum);
	if (!lch[root]&&!rch[root]){
		if (sum < best_sum || (sum == best_sum&&root < best))
		{
			best = root;
			best_sum = sum;
		}
	}
	return root;
}

int main()
{
	while (read(in_order))
	{
		read(post_order);
		best_sum = INF;
		build(0, n - 1, 0, n - 1, 0);
		printf("%d\n", best);

	}
	return 0;
}