算法与数据结构 实验题
6.4 order
★实验任务
给出一棵二叉树的中序遍历和每个节点的父节点，求这棵二叉树的先序和后序遍历。
★数据输入
输入第一行为一个正整数n表示二叉树的节点数目，节点编号从1到n，其中1为根节点。
第2行有n个数字，第i个数字表示i的父亲节点。（1的父亲节点为0，表示无）第3行为中序遍历。30%的数据：n<=20；60%的数据：n<=1000；100%的数据：n<=10000；
★ 数据输出
输出2行，第一行为先序遍历，第二行为后序遍历。
输入示例
10
0 7 2 2 9 1 8 1 6 8
9 5 6 1 10 8 7 3 2 4
输出示例
1 6 9 5 8 10 7 2 3 4
5 9 6 10 3 4 2 7 8 1
我的实现
第一次比较正式的写树，我所想出的这个算法效率也不是很高，感觉只能A三个点，等大神的代码出来了再看看他们的算法。
我的想法是，根据父子节点关系和中序遍历的优先级来进行建树，最后利用递归解决前序和后序遍历。
但是这样的话有T的风险，因此贴出的代码，打算和之后大神的代码进行比对。
//
// main.cpp
// Tree_Inoder
//
// Created by wasdns on 16/10/11.
// Copyright © 2016年 wasdns. All rights reserved.
//
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdlib>
#include <queue>
using namespace std;
int inorder[10005];
int depen[10005];
struct Tree {
int data;
Tree* l;
Tree* r;
};
/*
* 前序遍历实现
*/
void Preorder(Tree* p) {
if (p != NULL) {
if (p -> data != -1)
cout << p -> data << " ";
if (p -> l != NULL)
Preorder(p -> l);
if (p -> r != NULL)
Preorder(p -> r);
}
}
/*
* 后序遍历实现
*/
void Postorder(Tree* p) {
if (p != NULL) {
if (p -> l != NULL)
Postorder(p -> l);
if (p -> r != NULL)
Postorder(p -> r);
if (p -> data != -1)
cout << p -> data << " ";
}
}
/*
* 初始化节点
*/
Tree* Initial() {
Tree* p;
p = new Tree;
if (p == NULL) {
cout << "Error" << endl;
exit(1);
}
p -> data = -1;
p -> l = NULL;
p -> r = NULL;
return p;
}
/*
* 用于建树过程中区别左右子节点
*/
bool isleft(int n, int l, int r) {
bool flagl = false;
bool flagr = false;
for(int i = 1; i <= n; i++) {
if (inorder[i] == l || inorder[i] == r) {
if (inorder[i] == l) {
flagl = true;
}
else flagr = true;
break;
}
}
if (flagl && !flagr) return true;
else return false;
}
/*
* 程序核心：建树
*/
Tree* CreatTree(int n, int m) {
int i;
Tree* header;
Tree* tp;
header = Initial();
header -> data = m;
tp = header;
queue<Tree*> q;
q.push(header);
int turn = 0;
while (1) {
if (!q.empty()) {
tp = q.front();
}
else break;
turn = tp -> data;
//cout << "turn: " << turn << endl;
q.pop();
/*
* find father node's son nodes.
*/
int a = -1, b = -1;
for (i = 1; i <= n; i++) {
if (depen[i] == turn) {
if (a == -1) a = i;
else b = i;
}
}
/*
* father node don't have any son node.
*/
if (a == -1 && b == -1) {
//do nothing
continue;
}
/*
* one son node.
*/
else if (a != -1 && b == -1) {
tp -> l = Initial();
tp -> r = Initial();
if (isleft(n, a, turn)) {
tp -> l -> data = a;
q.push(tp -> l);
}
else {
tp -> r -> data = a;
q.push(tp -> r);
}
}
/*
* two son nodes.
*/
else if (a != -1 && b != -1) {
tp -> l = Initial();
tp -> r = Initial();
if (isleft(n, a, b)) {
tp -> l -> data = a;
tp -> r -> data = b;
}
else {
tp -> l -> data = b;
tp -> r -> data = a;
}
q.push(tp -> l);
q.push(tp -> r);
}
}
return header;
}
/*
* 打印树
*/
void PrintTree(Tree* p) {
queue<Tree*> q;
q.push(p);
Tree* turn;
turn = Initial();
while (!q.empty()) {
turn = q.front();
q.pop();
cout << turn -> data << " ";
if (turn -> l != NULL) {
if (turn -> l -> data != -1)
q.push(turn -> l);
}
if (turn -> r != NULL) {
if (turn -> r -> data != -1)
q.push(turn -> r);
}
}
cout << endl;
}
int main() {
int n, i;
cin >> n;
int turn = 0;
for (i = 1; i <= n; i++) {
cin >> depen[i];
if (depen[i] == 0) turn = i;
}
for (i = 1; i <= n; i++) {
cin >> inorder[i];
}
Tree* header;
header = CreatTree(n, turn);
//PrintTree(header); 打印树，检查建树过程有没有出错。
Preorder(header); //先序遍历
cout << endl;
Postorder(header); //后序遍历
cout << endl;
return 0;
}
To be continued.
2016/10/13