UVa122（附sscanf函数）

Posted on

UVa122

题意：根据输入构造二叉树，并根据二叉树从上到下，从左到右输出节点的值

样例输入：
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

输出：
5 4 8 11 13 4 7 2 1

Tips：

  • 通过链表来实现二叉树
    *
1
2
3
4
5
6
7
//二叉树节点的定义
struct Node {
	bool flag;			//标记是否被赋值
	int value;			//节点值
	Node* left, *right; //左右节点
	Node() :flag(false), left(NULL), right(NULL) {}//构造函数
};

解析输入的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
//读取输入数据
bool readin()
{
	failed = false;
	while (scanf("%s",s))
	{
		if (!strcmp(s, "()"))break;
		int v;
		sscanf(&s[1], "%d", &v);//从字符串中读取节点的数值,任意指向字符的指针看出是字符串
		addnode(v, strchr(s, ',') + 1);//找到逗号所在位置，然后加一为后面的字符串
	}
	return true;
}

对于读取的每个节点将其加入的二叉树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void addnode(int v, char* s)
{
	int n = strlen(s);
	Node* u = root;//顺着根节点向下走
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'L') {
			if (u->left == NULL)u->left = newnode();//节点不存在
			u = u->left;//继续向左走
		}
		else if (s[i] == 'R') {
			if (u->right == NULL)u->right = newnode();//节点不存在
			u = u->right;//继续向右走
		}
	}
	if (u->flag)failed = true;
	u->value = v;//节点赋值
	u->flag = true;//修改标记，表明已经赋值
}

对于已经生成的二叉树进行广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool bfs(vector<int>& ans)
{
	queue<Node*>q;
	ans.clear();
	q.push(root);
	while (!q.empty())
	{
		Node* u = q.front();
		q.pop();
		if (!u->flag)return false;
		ans.push_back(u->value);
		if (u->left != NULL)q.push(u->left);
		if (u->right != NULL)q.push(u->right);
	}
	return true;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
	while (1)
	{
		root = newnode();
		if (!readin())break;
		vector<int> ans;
		if (!failed&&bfs(ans))
		{
			int len = ans.size();
			for (int i = 0; i < len; i++)
				printf("%d%c", ans[i], i == len - 1 ? '\n' : ' ');
		}
		else printf("not complete\n");
	}
}

sscanf函数：