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

本文主要是介绍浙大PTA 编程题 03-树2 List Leaves (25 分)（c++），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：

这道题的意思就是：按照层序来输出叶结点。因为是按照层序，所以遍历树中元素的方式就不同于树的同构了，因为遍历完左儿子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;
}

这篇关于浙大PTA 编程题 03-树2 List Leaves (25 分)（c++）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！