UVA548 紫皮书代码解析

UVA548 紫皮书代码解析

刚开始接触二叉树，这道例题的代码花了好长时间才看懂，在这里写一篇关于这个代码的解析，希望能给大家提供一点帮助。

先给出题目中所给三组数据对应的二叉树

3 2 1 4 5 7 6 3 1 2 5 6 7 4 7 8 11 3 5 16 12 18 8 3 11 7 16 18 12 5 255 255

说明一下代码主要变量的含义

in_order[maxv]，按输入顺序存储中序遍历的结果。 post_order[maxv]，按输入顺序存储后序遍历的结果。 lch[maxv],rch[maxv]，这两个数组直接用权值做标号，分别表示对应点的左右两点。例如：lch[7]=0(7没有左子树),rch[7]=11。

解释一下主要函数的运行原理

先贴代码

bool read_list(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;
}

作用： 读入输入的一行数组，将其存入a数组中。 原理： 先将输入的字符串（“3 2 1 4 5 7 6”），存入ss中，然后由stringstream将每个数字单独分出来存入a数组中（这里不懂的可以查一下stringstream分割带空格的字符串）。

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;
}

作用： 将存在in_order和post_order中的两组数组建成一棵二叉树，用lch和rch保存。 变量含义： L1:中序遍历的第一个数。 R1:中序遍历的最后一个数。 L2:后序遍历的第一个数。 R2:后序遍历的最后一个数。 原理： 这里使用递归的原理进行建树，首先第一行给出终止条件，找到根节点所在位置（后序遍历的最后一个数），然后找出左右子树的结点个数，然后建立当前根节点的左右子树。

void dfs(int u, int sum)
{
	sum += u;
	if (!lch[u] && !rch[u])
	{
		if (sum  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;
}

int best, best_sum;

void dfs(int u, int sum)
{
	sum += u;
	if (!lch[u] && !rch[u])
	{
		if (sum