算法与数据结构 实验题
6.4 order
我的实现
//
// 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;
}