实现二叉树（search）

★实验任务

可怜的 Bibi 刚刚回到家，就发现自己的手机丢了，现在他决定回头去搜索自己的手机。现在我们假设 Bibi 的家位于一棵二叉树的根部。在 Bibi 的心中，每个节点都有一个权值 x，代表他心中预感向这个节点走可能找回自己手机的程度（虽然他的预感根本不准）。当 Bibi 到达一个节点时，如果该节点有未搜索过的儿子节点，则 Bibi 会走向未搜索过的儿子节点进行搜索，否则就返回父亲节点。如果某节点拥有两个未搜索过的儿子节点，Bibi 会选择先搜索权值大的儿子节点。假设 Bibi 从一个节点到达另一个节点需要 1 单位时间，搜索节点的时间忽略不计，那么请问当 Bibi 的手机位于编号为 k 的节点时，他需要多少单位时间才能找到手机。

★数据输入

输入第一行为一个正整数 n（1≤n≤100000）表示树的节点数目，树根的编号总是为 1。接下来 n-1 行，每行两个正整数 p，x（1≤x≤100）。代表编号为 i 的节点的父亲节点 p 和权值 x。这里的 i 从 2 依次数到 n。数据保证输入的 p 小于当前的 i，且互为兄弟的两个节点的权值 x 不同。第 n+1 行一个整数 m（1≤m≤n），表示询问组数。第 n+2 行有 m 个整数，每个整数 ki（1≤ki≤n）代表该组询问中手机的位置。

★数据输出

输出 m 行，每行一个整数，代表 Bibi 找到手机需要花费的单位时间数量。

测试样例

输入：

3

1 20

1 30

1 2 3

输出：

解题过程：

暂时个人认为二叉树其实更好实现，因为之前对于儿子个数不确定的树需要用链表很不熟悉（不过现在感觉用动态数组vector可以好多了），而二叉树每个节点有两个儿子实现就比较简单；

解题思路：

通过深搜的方法实现，用递归回溯的思想对走的步数（即时间）进行计算并同步存储，这题还需要我们同时对每个节点的时间存储，因为访问的次数可能会很多容易超时。

代码：

给我帮助的同学的代码（通过vector写）：



#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<vector>

#include<algorithm>

#define MAX_SIZE 100005

using namespace std;

struct node

{

	int quan, bu;

	bool vis;

}tree[MAX_SIZE];

vector <int> v[MAX_SIZE];

int cnt = -1;

int n;

void dfs(int ge)

{

	cnt++;

	if (tree[ge].vis == false)

	{

		tree[ge].vis = true;

		tree[ge].bu = cnt;

	}

	if (!v[ge].empty())

	{

		vector<int>::iterator it;

		for (it = v[ge].begin(); it != v[ge].end(); it++)

			dfs(*it);

	}

	cnt++;

}

int main()

{

	int i, j;

	scanf("%d", &n);

	for (i = 1; i <= n; i++)

		v[i].clear();

	for (i = 2; i <= n; i++)

	{

		int a, b;

		scanf("%d%d", &a, &b);

		tree[i].quan = b;

		tree[i].vis = false;

		v[a].push_back(i);

	}

	for (i = 1; i <= n; i++)

	{

		if (!v[i].empty() && v[i].size()>1)

		{

			if (tree[v[i][0]].quan<tree[v[i][1]].quan)

				swap(v[i][0], v[i][1]);

		}

	}

	dfs(1);

	int m;

	scanf("%d", &m);

	for (i = 1; i <= m; i++)

	{

		int a;

		scanf("%d", &a);

		printf("%d\n", tree[a].bu);

	}

	//    system("pause");

	return 0;

}

之后对我之前用数组实现的代码的改进实现：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<vector>

#define MAX_SIZE 100005

using namespace std;

int cnt = -1;

struct Node

{

	int ele;

	int son1, son2;

	int vis;

	int ste;

}node[MAX_SIZE];

void dfs(int loca)

{

	cnt++;

	if (node[loca].vis == 0)

	{

		node[loca].vis = 1;

		node[loca].ste = cnt;

	}

	if (node[node[loca].son1].vis == 0 && node[loca].son1 != 0)

	{

		dfs(node[loca].son1);

		cnt++;

	}

	if (node[node[loca].son2].vis == 0 && node[loca].son2 != 0)

	{

		dfs(node[loca].son2);

		cnt++;

	}

}

int main()

{

	int n, i, j;

	cin >> n;

	for (i = 2; i <= n; i++)

	{

		int father;

		cin >> father >> node[i].ele;

		if (node[father].son1 == 0)node[father].son1 = i;

		else

		{

			if (node[node[father].son1].ele < node[i].ele)

			{

				node[father].son2 = node[father].son1;

				node[father].son1 = i;

			}

			else node[father].son2 = i;

		}

		node[i].vis = 0;

	}

	dfs(1);

	int m;

	cin >> m;

	for (i = 1; i <= m; i++)

	{

		int tmp;

		cin >> tmp;

		cout << node[tmp].ste << endl;

	}

	return 0;

}

题目收获：二叉树可以方便的通过数组实现，而树其实也不会很难，可以通过vector动态数组实现就行。

巴特西

实现二叉树（search）

解题思路：

代码：

最新文章

热门文章