欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习20——1020 Tree Traversals

程序员文章站 2022-06-07 13:13:38
...

题目

PTA甲级考试真题练习20——1020 Tree Traversals

生词生句

  1. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree
    给定后序遍历和中序遍历,你应该输出层序遍历的结果
    preorder/inorder/postorder/level order 前序/中序/后序/层序遍历

思路

通过数的后序序列和中序序列生成二叉树,并且层序遍历二叉树
具体实现是利用递归将中序序列再次分为两个子序列(根结点的左节点序列和右结点序列),直到没有左结点和右结点

代码

#include <iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<list>
using namespace std;
#define nmax 1000  //一个用作示例的小顺序表的最大长度
#define inf 999999
vector<int> postorder;
vector<int> levelorder;
int visited[nmax];  //标记数组

typedef struct Node
{
	int key;
	Node* lchild, *rchild;
}Node,*Tree;

int FindIndex(int key,vector<int> inorder)
{
	for (int i = inorder.size() - 1; i >= 0; --i)
	{
		if (inorder[i] == key)
			return i;
	}
	return -1;
}

void SpanTree(Tree& tree,int index,int NodeType,vector<int> inorder)
{
	Node* newnode;
	//如果是树的根结点
	if (NodeType == 0)
	{
		tree = (Node*)malloc(sizeof(Node));
		tree->lchild = tree->rchild = nullptr;
		tree->key = postorder[index];
		newnode = tree;
	}
	//如果是左边结点
	else if (NodeType == 1)
	{
		newnode = (Node*)malloc(sizeof(Node));
		newnode->lchild = newnode ->rchild = nullptr;
		newnode->key = postorder[index];
		tree->lchild = newnode;
	}
	//如果是右边结点
	else
	{
		newnode = (Node*)malloc(sizeof(Node));
		newnode->lchild = newnode->rchild = nullptr;
		newnode->key = postorder[index];
		tree->rchild = newnode;
	}
	int curIndex = FindIndex(postorder[index],inorder);
	int rightLen = inorder.size() - 1 - curIndex;
	vector<int> left;
	vector<int> right;
	left.assign(inorder.begin(), inorder.begin() + curIndex);
	right.assign(inorder.begin()+curIndex+1, inorder.end());
	if (!right.empty())
	{
		//遍历右结点
		SpanTree(newnode, index - 1, 2, right);
	}
	if (!left.empty())
	{
		//遍历左结点
		SpanTree(newnode, index - rightLen - 1, 1, left);
	}
}

void BFS(const Tree& tree)
{
	queue<Tree> tree_queue;
	cout << tree->key;
	if (tree->lchild != nullptr)
		tree_queue.push(tree->lchild);
	if (tree->rchild != nullptr)
		tree_queue.push(tree->rchild);
	while (!tree_queue.empty())
	{
		Tree tmp = tree_queue.front();
		cout << " "<< tmp->key;
		tree_queue.pop();
		if(tmp->lchild!=nullptr)
			tree_queue.push(tmp->lchild);
		if(tmp->rchild!=nullptr)
			tree_queue.push(tmp->rchild);
	}
}

int main()
{
	int nodenum;
	vector<int> inorder;
	cin >> nodenum;
	int key;
	for (int i = 0; i < nodenum; ++i)
	{
		cin >> key;
		postorder.push_back(key);
	}
	for (int i = 0; i < nodenum; ++i)
	{
		cin>>key;
		inorder.push_back(key);
	}
	Tree tree;
	SpanTree(tree, postorder.size() - 1,0,inorder);
	BFS(tree);
	return 0;
}