网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

浙大PTA 编程题 03-树2 List Leaves (25 分)(c++)

2021/6/27 21:55:37 人评论

思路: 这道题的意思就是:按照层序来输出叶结点。因为是按照层序,所以遍历树中元素的方式就不同于树的同构了,因为遍历完左儿子1,不能遍历左儿子1的左儿子2,而是要遍历和左儿子1并列的右儿子1,这…

思路:

这道题的意思就是:按照层序来输出叶结点。因为是按照层序,所以遍历树中元素的方式就不同于树的同构了,因为遍历完左儿子1,不能遍历左儿子1的左儿子2,而是要遍历和左儿子1并列的右儿子1,这就需要我们记住左儿子1的父亲,才能找到右儿子1,这样用结构数组来编程太过繁琐,所以就想到了用deque容器来实现。deque容器可以在front 和back处插入数据,并可以删除front和back处的数据,太适合层序遍历了。

重点:

1.因为用户输入树的数据不是按着层序输入的,需要我们自行找到树的根结点。

2.容器deque中元素的插入和删除。d.push_back();   d.pop_front(); 从后面插入,从前面删除。

运行结果:

代码如下:

#include<iostream>
#include<deque>
using namespace std;
#define Max 10
#define Null -1
struct Tree
{
	char Left;
	char Right;
}T[Max];
int InputTree(struct Tree T[])
{
	int N;
	cin >> N;
	//创建标记,用来找根结点
	int check[Max];
	for (int i = 0; i < N; i++)
	{
		check[i] = 0;
	}

	char left, right;

	if (N != 0)
	{
		for (int i = 0; i < N; i++)
		{
			//输入左右儿子
			cin >> left >> right;

			//接收左儿子
			if (left != '-')
			{
				T[i].Left = left - '0';
				check[T[i].Left] = 1;
			}
			else
			{
				T[i].Left = Null;
			}

			//接收右儿子
			if (right != '-')
			{
				T[i].Right = right - '0';
				check[T[i].Right] = 1;
			}
			else
			{
				T[i].Right = Null;
			}
		}
	}
	else
	{
		return Null;
	}
	
	//找出根结点
	int root;
	for (int i = 0; i < N; i++)
	{
		if (check[i] == 0)
		{
			root = i;
		}
	}
	return root;
}
void PrintLeaves(int root,struct Tree T[])
{
	//输出格式要求首末没有空格
	int flag = 0;

	if (root == Null)
	{
		return;
	}

	//建立deque容器,先插入数据root
	deque<int>d;
	d.push_back(root);
	while (!d.empty())  /*循环条件就是看看容器deque什么时候为空,
		                  为空就说明整个树的元素都遍历完了,
		                  则退出循环*/
	{
		//判断d中首元素是不是叶结点,是就输出,不是,就把他的左右儿子从后面存入容器
		if (T[d[0]].Left == Null && T[d[0]].Right == Null)
		{
			if (flag == 0)
			{
				cout << d[0];
				flag++;
			}
			else
			{
				cout << " " << d[0];
			}
		}
		//存左儿子
		if (T[d[0]].Left != Null)
		{
			d.push_back(T[d[0]].Left);
		}
		//存右儿子
		if (T[d[0]].Right != Null)
		{
			d.push_back(T[d[0]].Right);
		}
		//删除首元素(因为首元素的左右儿子都存进容器了,并且也判断完了他是不是叶结点了)
		//这样,首元素的左儿子就变成了首元素
		//然后和首元素的左儿子并列的首元素的右儿子在变成首元素
		//永远都用d[0]
		d.pop_front();
	}
}
int main()
{
	int Root;
	Root = InputTree(T);
	PrintLeaves(Root,T);
	system("pause");
	return 0;
}

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?