题目：
思路：
这题是比较典型的树的遍历问题，思路就是将中序遍历作为位置的判断依据，假设有个节点A和它的父亲Afa，那么如果A和Afa的顺序在中序遍历中是先A后Afa，则A是Afa的左儿子，否则是右儿子。
用for遍历一遍所有的节点，让每一个节点都连接到它的父亲，最后从根节点开始访问即可。
代码：
//
// main.cpp
// Tree
//
// Created by wasdns on 16/12/19.
// Copyright ? 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Node
{
int num;
Node *lnext, *rnext;
};
int fa[10005]; //父亲
Node* node[100005]; //节点
int midorder[100005]; //中序
int preorder[100005]; //先序
int aftorder[100005]; //后序
int tot = 0;
/*
Ininode函数：初始化各个节点
*/
void Ininode(int n)
{
for (int i = 1; i <= n; i++)
{
Node *p = new Node;
p -> num = i;
p -> lnext = NULL;
p -> rnext = NULL;
node[i] = p;
}
}
/*
isleft函数：判断儿子是左儿子还是右儿子
*/
bool isleft(int n, int num, int f)
{
bool ans = true;
for (int i = 1; i <= n; i++)
{
if (midorder[i] == num || midorder[i] == f)
{
if (midorder[i] == f) {
ans = false;
}
break;
}
}
return ans;
}
/*
CreatTree：建树
*/
Node* CreatTree(int n)
{
int i;
int fanum;
for (i = 2; i <= n; i++)
{
fanum = fa[i];
if (isleft(n, i, fanum)) {
node[fanum] -> lnext = node[i];
}
else {
node[fanum] -> rnext = node[i];
}
}
return node[1];
}
/*
CalPreorder函数：计算先序
*/
void CalPreorder(Node *p)
{
if (p -> lnext == NULL && p -> rnext == NULL) {
preorder[tot++] = p -> num;
return ;
}
preorder[tot++] = p -> num;
if (p -> lnext != NULL) CalPreorder(p -> lnext);
if (p -> rnext != NULL) CalPreorder(p -> rnext);
}
/*
CalAftorder函数：计算后序
*/
void CalAftorder(Node *p)
{
if (p -> lnext == NULL && p -> rnext == NULL) {
aftorder[tot++] = p -> num;
return ;
}
if (p -> lnext != NULL) CalAftorder(p -> lnext);
if (p -> rnext != NULL) CalAftorder(p -> rnext);
aftorder[tot++] = p -> num;
}
/*
PrintTree函数：中序遍历(queue思想)输出树
*/
void PrintTree(Node *head)
{
queue<Node*> q;
q.push(head);
Node *p;
while (!q.empty())
{
p = q.front();
q.pop();
cout << p -> num << " ";
if (p -> lnext != NULL) {
q.push(p -> lnext);
}
if (p -> rnext != NULL) {
q.push(p -> rnext);
}
}
cout << endl;
}
/*
Print函数：输出结果
*/
void Print(int n)
{
int i;
for (i = 0; i < n; i++) {
cout << preorder[i] << " ";
}
cout << endl;
for (i = 0; i < n; i++) {
cout << aftorder[i] << " ";
}
cout << endl;
}
int main()
{
int n;
cin >> n;
int i;
for (i = 1; i <= n; i++) {
cin >> fa[i];
}
for (i = 1; i <= n; i++) {
cin >> midorder[i];
}
Ininode(n);
Node* head;
head = new Node;
head = CreatTree(n);
//PrintTree(head);
CalPreorder(head);
tot = 0;
CalAftorder(head);
Print(n);
return 0;
}
2016/12/19