PTA甲级考试真题练习20——1020 Tree Traversals
程序员文章站
2022-06-07 13:13:38
...
题目
生词生句
- 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;
}
上一篇: PAT Basic 1077.互评成绩计算 (20)
下一篇: 牛客练习赛71 E 神奇的迷宫
推荐阅读
-
PTA甲级考试真题练习111——1111 Online Map
-
PTA甲级考试真题练习22——1022 Digital Library
-
PTA甲级考试真题练习18——1018 Public Bike Management
-
PTA甲级考试真题练习20——1020 Tree Traversals
-
PTA甲级考试真题练习30——1030 Travel Plan
-
PTA甲级考试真题练习17——1017 Queueing at Bank
-
PTA甲级考试真题练习8——1008 Elevator
-
PTA甲级考试真题练习23——1023 Have Fun with Numbers
-
PTA甲级考试真题练习5——1005 Spell It Right
-
PTA甲级考试真题练习11——1011 World Cup Betting