# 11214: 【原1214】traverse

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1214

## Sample Input

``````9
2 0 111
5 3 222
0 4 333
7 0 444
0 6 555
0 0 666
0 8 777
0 9 888
0 0 999
``````

## Sample Output

``````111 222 555 666 333 444 777 888 999
555 666 222 333 777 888 999 444 111
111 222 333 444 555 666 777 888 999
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/3/31.
//

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

template<typename Item>
class Queue {
class Node {
public:
Item item;
Node *next = nullptr;
};

int N;
Node *first;
Node *last;

public:
Queue() {
N = 0;
first = last = nullptr;
}

bool isEmpty() const {
return N == 0;
}

int size() const {
return N;
}

void enqueue(Item item) {
if (N == 0) {
first = new Node{item};
last = first;
} else {
Node *tmp = last;
last = new Node{item};
tmp->next = last;
}
++N;
}

Item dequeue() {
Item item = first->item;
Node *tmp = first;
first = first->next;
if (N == 1) last = nullptr;
delete tmp;
--N;
return item;
}

Item getFirst() const {
return first->item;
}

Item getLast() const {
return last->item;
}

void clear() {
Node *tmp;
while (first != nullptr) {
tmp = first;
first = first->next;
delete tmp;
}
N = 0;
first = last = nullptr;
}

void print(ostream &os = std::cout) const {
Node *p = first;
while (p) {
os << p->item << ' ';
p = p->next;
}
os << endl;
}

virtual ~Queue() {
Node *tmp;
while (first != nullptr) {
tmp = first;
first = first->next;
delete tmp;
}
}
};

template<typename Item>
class BinaryTree {

class Node {
public:
Node *left = nullptr, *bro = nullptr;
Node *father = nullptr;
Item val;
};

int size;
int maxSize;
Node *root;
Node **nodes;

Queue<Item> pre;
Queue<Item> post;
Queue<Item> level;

private:
void dfs(Node *node) {
pre.enqueue(node->val);
if (node->left) dfs(node->left);
post.enqueue(node->val);
if (node->bro) dfs(node->bro);
}

void bfs() {
Queue<Node *> queue;
queue.enqueue(root);

Node *p;
while (!queue.isEmpty()) {
p = queue.dequeue();
while (p) {
level.enqueue(p->val);
if (p->left)
queue.enqueue(p->left);
p = p->bro;
}
}
}

public:
BinaryTree() {
BinaryTree(5);
}

explicit BinaryTree(int maxSize) {
root = nullptr;
this->maxSize = maxSize;
nodes = new Node *[maxSize + 1]{};
for (int i = 1; i <= maxSize; ++i) {
nodes[i] = new Node();
}
size = 0;
}

void add(int left, int bro, Item item) {
if (size == maxSize) resize(maxSize * 2);
++size;

nodes[size]->val = item;
nodes[size]->left = nodes[left];
nodes[size]->bro = nodes[bro];
if (left) nodes[left]->father = nodes[size];
if (bro) nodes[bro]->father = nodes[size];
}

void resize(int newSize) {
auto oldNodes = nodes;
nodes = new Node *[newSize + 1]{};
for (int i = 1; i <= maxSize; ++i) {
nodes[i] = oldNodes[i];
}
for (int i = maxSize + 1; i <= newSize; ++i) {
nodes[i] = new Node;
}
maxSize = newSize;
}

void getRoot() {
Node *p = nodes[1];
while (p->father) {
p = p->father;
}
root = p;
}

void traverse() {
getRoot();
pre.clear();
post.clear();
level.clear();

dfs(root);
bfs();
};

const Queue<Item> &getPre() {
return pre;
}

const Queue<Item> &getPost() {
return post;
}

const Queue<Item> &getLevel() {
return level;
}

virtual ~BinaryTree() {
for (int i = 1; i <= maxSize; ++i) {
delete nodes[i];
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin >> N;
BinaryTree<int> binaryTree(N);
int a, b, c;
while (N--) {
cin >> a >> b >> c;
}

binaryTree.traverse();
binaryTree.getPre().print();
binaryTree.getPost().print();
binaryTree.getLevel().print();

return 0;
}
``````

## FineArtz's solution

``````/* traverse */
#include <iostream>
using namespace std;

struct Node{
int child = 0, sibling = 0;
int val = 0;
};

Node a[100005];
bool b[100005] = {0};
int n;

void foretra(int x){
if (x == 0)
return;
cout << a[x].val << ' ';
int t = a[x].child;
while (t){
foretra(t);
t = a[t].sibling;
}
}

void backtra(int x){
if (x == 0)
return;
int t = a[x].child;
while (t){
backtra(t);
t = a[t].sibling;
}
cout << a[x].val << ' ';
}

void hieatra(int root){
int q[100005];
int front = 0, rear = 0;
q[rear++] = root;
while (front != rear){
int now = q[front];
front++;
cout << a[now].val << ' ';
int t = a[now].child;
while (t){
q[rear++] = t;
t = a[t].sibling;
}
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i].child >> a[i].sibling >> a[i].val;
b[a[i].child] = true;
b[a[i].sibling] = true;
}
int root = 0;
for (int i = 1; i <= n; ++i){
if (!b[i]){
root = i;
break;
}
}
foretra(root);
cout << '\n';
backtra(root);
cout << '\n';
hieatra(root);
cout << '\n';
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

template <class T>
class mQueue {
class node {
public:
T data;
node* next = nullptr;
};
* rear = nullptr;
size_t _size = 0;

public:
//构造函数
mQueue() {
}
//判断是否为空
bool empty() {
}
//增加
void push(const T& val) {
rear->next = new node;
rear = rear->next;
rear->data = val;
++_size;
}
//删除
void pop() {
//安全措施
return;
--_size;
}
//大小
size_t size() {
return _size;
}
//最前
T& front() {
//安全措施
}
//最后
T& back() {
//安全措施
return rear->data;
}
};

template <class T>
class mVector {
T** vector_data = nullptr;
unsigned int size = 0;
unsigned int capacity = 0;

public:
//构造函数
mVector() = default;
mVector(unsigned int _size) :size(_size) {
capacity = _size * 2;
vector_data = new T * [capacity] {nullptr};
}
mVector(unsigned int _size, const T& val) :size(_size) {
capacity = _size * 2;
vector_data = new T * [capacity] {nullptr};
for (unsigned int i = 0; i < _size; ++i)
vector_data[i] = new T(val);
}
mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
vector_data = new T * [capacity] {nullptr};
for (int i = 0; i < size; ++i)
vector_data[i] = new T(*_vector.vector_data[i]);
}
//析构函数
~mVector() {
for (unsigned int i = 0; i < size; ++i)
delete vector_data[i];
delete[] vector_data;
}

//迭代器
class iterator {
T** pos = nullptr;
friend iterator mVector<T>::begin();
friend iterator mVector<T>::end();
friend void mVector<T>::erase(const iterator& val);
public:
iterator() = default;
iterator(const iterator& other) {
pos = other.pos;
}
iterator& operator++() {
++pos;
return *this;
}
iterator operator++(int) {
iterator temp(*this);
++pos;
return temp;
}
iterator& operator--() {
--pos;
return *this;
}
iterator operator--(int) {
iterator temp(*this);
--pos;
return temp;
}
bool operator==(const iterator& other) const {
return pos == other.pos;
}
bool operator!=(const iterator& other) const {
return pos != other.pos;
}
iterator& operator=(const iterator& other) {
pos = other.pos;
return *this;
}
T& operator*() const {
return **pos;
}
};

//增加元素
void push_back(const T & val) {
if (size < capacity)
vector_data[size++] = new T(val);
else {
T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
for (unsigned int i = 0; i < size; ++i)
temp_data[i] = vector_data[i];
temp_data[size++] = new T(val);
capacity = (capacity + 1) * 2;
delete[] vector_data;
vector_data = temp_data;
}
}

//删除末尾
void pop_back() {
delete vector_data[size];
vector_data[size--] = nullptr;
}

//清空
void clear() {
for (unsigned int i = 0; i < size; ++i) {
delete vector_data[i];
vector_data[i] = nullptr;
}
size = 0;
}

//删除
void erase(const iterator & val) {
delete* val.pos;
for (auto p = val.pos; p != vector_data + size - 1; ++p)
* p = *(p + 1);
--size;
vector_data[size] = nullptr;
}

//重载运算符
T & operator[](const unsigned int& pos) {
return *vector_data[pos];
}

iterator begin() {
iterator temp;
temp.pos = vector_data;
return temp;
}

iterator end() {
iterator temp;
temp.pos = vector_data + size;
return temp;
}

};

//二叉树类
template <class T>
class myBinaryTree {
public:
class node {
public:
T data;
node *lchild = nullptr, *rchild = nullptr, *parent = nullptr;
};
node *root = nullptr;
node **nodeList = nullptr;
long long sizeOfTree = 0;

//创建树
void createTree(int num) {
nodeList = new node*[num + 1]{ nullptr };
sizeOfTree = num;
}

void creadNode(int nodeNum, int lchild, int rchild, int data) {
if (nodeList[nodeNum] == nullptr)
nodeList[nodeNum] = new node;

nodeList[nodeNum]->data = data;

if (lchild != 0) {
if (nodeList[lchild] == nullptr)
nodeList[lchild] = new node;
nodeList[lchild]->parent = nodeList[nodeNum];
nodeList[nodeNum]->lchild = nodeList[lchild];
}

if (rchild != 0) {
if (nodeList[rchild] == nullptr)
nodeList[rchild] = new node;
nodeList[rchild]->parent = nodeList[nodeNum];
nodeList[nodeNum]->rchild = nodeList[rchild];
}
}

void checkRoot() {
for (int i = 1; i <= sizeOfTree; i++) {
if (nodeList[i]->parent == nullptr) {
root = nodeList[i];
break;
}
}
}

//清空
void clear() {
clear(root);
}

void clear(node *p) {
if (p == nullptr)
return;
clear(p->lchild);
clear(p->rchild);
delete p;
p = nullptr;
}

//构造
myBinaryTree() {}

//析构
~myBinaryTree() {
clear(root);
}

//判断是否非空
bool empty() {
return root == nullptr;
}

//判断是否为完全二叉树
bool isCBT() {
if (empty())
return false;
//层次遍历
mQueue<node*> treeQueue;
bool flag = false;
//先入队
treeQueue.push(root);

//反复
while (!treeQueue.empty()) {
//先出队一个
node* temp = treeQueue.front();
treeQueue.pop();

//右孩子有左孩子没有
if (temp->lchild == nullptr&&temp->rchild != nullptr)
return false;

if (!flag) {
//左孩子有右孩子没有
if (temp->lchild != nullptr&&temp->rchild == nullptr) {
flag = true;
//左孩子入队
treeQueue.push(temp->lchild);
}
//左右孩子都没有
else if (temp->lchild == nullptr&&temp->rchild == nullptr) {
flag = true;
}
//左右都有孩子
else {
treeQueue.push(temp->lchild);
treeQueue.push(temp->rchild);
}
}
else {
//判断是否为叶子
if (temp->lchild != nullptr || temp->rchild != nullptr)
return false;
}
}

return true;
}

//返回大小
long long size() {
return sizeOfTree;
}

//层次遍历
mVector<T> levelTraversal() {
if (sizeOfTree == 0)
return *new mVector<T>;

mVector<T> result;
mQueue<node*> treeQueue;

//根结点入队
treeQueue.push(root);

//层次遍历
while (!treeQueue.empty()) {
//出队
node* temp = treeQueue.front();
treeQueue.pop();

//入队
if (temp->lchild != nullptr)
treeQueue.push(temp->lchild);
if (temp->rchild != nullptr)
treeQueue.push(temp->rchild);

//写入
result.push_back(temp->data);
}

//返回
return result;
}

//前序遍历
mVector<T> preorderTraversal() {
mVector<T> result;
preorderTraversal(root, result);
return result;
}

void preorderTraversal(node* treeRoot,mVector<T> &result) {
//显示当前
result.push_back(treeRoot->data);

if (treeRoot->lchild != nullptr)
preorderTraversal(treeRoot->lchild,result);
if (treeRoot->rchild != nullptr)
preorderTraversal(treeRoot->rchild,result);
}

//中序遍历
mVector<T> midorderTraversal() {
mVector<T> result;
midorderTraversal(root, result);
return result;
}

void midorderTraversal(node* treeRoot, mVector<T> &result) {
if (treeRoot->lchild != nullptr)
midorderTraversal(treeRoot->lchild, result);
//显示当前
result.push_back(treeRoot->data);
if (treeRoot->rchild != nullptr)
midorderTraversal(treeRoot->rchild, result);
}

//后序遍历
mVector<T> lostorderTraversal() {
mVector<T> result;
lostorderTraversal(root, result);
return result;
}

void lostorderTraversal(node* treeRoot, mVector<T> &result) {
if (treeRoot->lchild != nullptr)
lostorderTraversal(treeRoot->lchild, result);
if (treeRoot->rchild != nullptr)
lostorderTraversal(treeRoot->rchild, result);
//显示当前
result.push_back(treeRoot->data);
}
};

//左孩子右兄弟二叉树类
template <class T>
class mySpecialBinaryTree {
public:
class node {
public:
T data;
node *lchild = nullptr, *rbrother = nullptr;
bool isRoot = true;
};
node *root = nullptr;
node **nodeList = nullptr;
long long sizeOfTree = 0;

//创建树
void createTree(int num) {
nodeList = new node*[num + 1]{ nullptr };
sizeOfTree = num;
}

void creadNode(int nodeNum, int lchild, int rbrother, int data) {
if (nodeList[nodeNum] == nullptr)
nodeList[nodeNum] = new node;

nodeList[nodeNum]->data = data;

if (lchild != 0) {
if (nodeList[lchild] == nullptr)
nodeList[lchild] = new node;
nodeList[lchild]->isRoot = false;
nodeList[nodeNum]->lchild = nodeList[lchild];
}

if (rbrother != 0) {
if (nodeList[rbrother] == nullptr)
nodeList[rbrother] = new node;
nodeList[rbrother]->isRoot = false;
nodeList[nodeNum]->rbrother = nodeList[rbrother];
}
}

void checkRoot() {
for (int i = 1; i <= sizeOfTree; i++) {
if (nodeList[i]->isRoot) {
root = nodeList[i];
break;
}
}
}

//清空
void clear() {
clear(root);
}

void clear(node *p) {
if (p == nullptr)
return;
clear(p->lchild);
clear(p->rbrother);
delete p;
p = nullptr;
}

//构造
mySpecialBinaryTree() {}

//析构
~mySpecialBinaryTree() {
clear(root);
}

//判断是否非空
bool empty() {
return root == nullptr;
}

//返回大小
long long size() {
return sizeOfTree;
}

//层次遍历
mVector<T> levelTraversal() {
if (sizeOfTree == 0)
return *new mVector<T>;

mVector<T> result;
mQueue<node*> treeQueue;

//根结点入队
treeQueue.push(root);

//层次遍历
while (!treeQueue.empty()) {
//出队
node* temp = treeQueue.front();
treeQueue.pop();

//入队
for (auto p = temp->lchild; p!= nullptr; p = p->rbrother)
treeQueue.push(p);

//写入
result.push_back(temp->data);
}

//返回
return result;
}

//前序遍历
mVector<T> preorderTraversal() {
mVector<T> result;
preorderTraversal(root, result);
return result;
}

void preorderTraversal(node* treeRoot, mVector<T> &result) {
//显示当前
result.push_back(treeRoot->data);

if (treeRoot->lchild != nullptr)
preorderTraversal(treeRoot->lchild, result);
if (treeRoot->rbrother != nullptr)
preorderTraversal(treeRoot->rbrother, result);
}

//后序遍历
mVector<T> lostorderTraversal() {
mVector<T> result;
lostorderTraversal(root, result);
return result;
}

void lostorderTraversal(node* treeRoot, mVector<T> &result) {
if (treeRoot->lchild != nullptr)
lostorderTraversal(treeRoot->lchild, result);
//显示当前
result.push_back(treeRoot->data);
if (treeRoot->rbrother != nullptr)
lostorderTraversal(treeRoot->rbrother, result);
}
};

int main() {
int num;
mySpecialBinaryTree<int> bTree;
cin >> num;
bTree.createTree(num);

for (int i = 1; i <= num; i++) {
int lchild, rchild, nodeData;
scanf("%d %d %d", &lchild, &rchild, &nodeData);
}

bTree.checkRoot();
auto ans = bTree.preorderTraversal();

cout << ans[0];
for (int i = 1; i < bTree.sizeOfTree; i++)
printf(" %d", ans[i]);
auto ans1 = bTree.lostorderTraversal();

cout << endl;

cout << ans1[0];
for (int i = 1; i < bTree.sizeOfTree; i++)
printf(" %d", ans1[i]);

auto ans2 = bTree.levelTraversal();

cout << endl;

cout << ans2[0];
for (int i = 1; i < bTree.sizeOfTree; i++)
printf(" %d", ans2[i]);

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 100000;
int leftNum[maxN + 100] = {0}, rightNum[maxN + 100] = {0};
long long int numNum[maxN + 100] = {0};

template <class elemType>
class queue {
public:
virtual bool isEmpty() const = 0;
virtual void enQueue(const elemType &) = 0;
virtual elemType deQueue() = 0;
virtual elemType getHead() const = 0;
virtual ~queue() {}
};

template <class elemType>
class seqQueue : public queue<elemType> {
private:
elemType *data;
int maxSize;
int front, rear;
void doubleSpace();

public:
seqQueue(int size = maxN + 100);
~seqQueue();
bool isEmpty() const;
void enQueue(const elemType &);
elemType deQueue();
int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
elemType *tmp = data;
data = new elemType[maxSize * 2];

for (int i = 1; i <= maxSize; i++) {
data[i] = tmp[(front + i) % maxSize];
}

front = 0;
rear = maxSize;
maxSize *= 2;
delete[] tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
if ((rear + 1) % maxSize == front) {
doubleSpace();
}
rear = (rear + 1) % maxSize;
data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
front = (front + 1) % maxSize;
return data[front];
}

template <class elemType>
return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
return ((rear + maxSize - front) % maxSize);
}

template <class T>
class bTree {
private:
struct Node {
T data;
Node *leftSon;
Node *leftBrother;
Node *rightBrother;
Node *parent;

Node(T d = 0)
: data(d), parent(0), leftSon(0), leftBrother(0), rightBrother(0) {}
};
Node *root;
Node *nodes[maxN + 100];
void clear(Node *);
void preOrder(Node *) const;
void postOrder(Node *) const;

public:
bTree(int n = 10);
~bTree();
void findRoot();
void levelOrder() const;
void preOrder() const;
void postOrder() const;
};

template <class T>
bTree<T>::bTree(int n) : root(NULL) {
for (int i = 1; i <= n + 5; i++) {
nodes[i] = new Node;
}
}

template <class T>
bTree<T>::~bTree() {
clear(root);
}

template <class T>
void bTree<T>::clear(Node *p) {
if (p == NULL) {
return;
}

clear(p->leftSon);
clear(p->rightBrother);
delete p;
}

template <class T>
void bTree<T>::addNode(int n, int i, T x, bool isRight) {
if (i != 0 && !isRight) {
nodes[i]->parent = nodes[n];
nodes[n]->leftSon = nodes[i];
} else if (i != 0 && isRight) {
nodes[i]->leftBrother = nodes[n];
nodes[n]->rightBrother = nodes[i];
}
nodes[n]->data = x;
}

template <class T>
void bTree<T>::findRoot() {
root = nodes[1];
while (root->parent != NULL || root->rightBrother != NULL ||
root->leftBrother != NULL) {
if (root->parent != NULL) {
root = root->parent;
} else if (root->leftBrother != NULL) {
root = root->leftBrother;
}
}
}

template <class T>
void bTree<T>::levelOrder() const {
seqQueue<Node *> que;
Node *tmp, *tmp1;

cout << root->data << ' ';
que.enQueue(root);
while (!que.isEmpty()) {
tmp = que.deQueue();
tmp1 = tmp->leftSon;
while (tmp1) {
cout << tmp1->data << ' ';
que.enQueue(tmp1);
tmp1 = tmp1->rightBrother;
}
}
}

template <class T>
void bTree<T>::preOrder(Node *t) const {
cout << t->data << ' ';

Node *tmp = t;
while (tmp->rightBrother != 0 && t == root) {
preOrder(tmp->rightBrother);
tmp = tmp->rightBrother;
}

if (t->leftSon != 0) {
preOrder(t->leftSon);
Node *tmp1 = t->leftSon;
while (tmp1->rightBrother != 0) {
preOrder(tmp1->rightBrother);
tmp1 = tmp1->rightBrother;
}
}
}

template <class T>
void bTree<T>::postOrder(Node *t) const {
Node *tmp = t;
while (tmp->rightBrother != 0 && t == root) {
postOrder(tmp->rightBrother);
tmp = tmp->rightBrother;
}

if (t->leftSon != 0) {
postOrder(t->leftSon);

Node *tmp1 = t->leftSon;
while (tmp1->rightBrother != 0) {
postOrder(tmp1->rightBrother);
tmp1 = tmp1->rightBrother;
}
}
cout << t->data << ' ';
}

template <class T>
void bTree<T>::preOrder() const {
preOrder(root);
}

template <class T>
void bTree<T>::postOrder() const {
postOrder(root);
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int N;

cin >> N;
bTree<long long int> Tree(N);
for (int i = 1; i <= N; i++) {
cin >> leftNum[i] >> rightNum[i] >> numNum[i];
}

for (int i = 1; i <= N; i++) {
}
for (int i = 1; i <= N; i++) {
}

Tree.findRoot();

Tree.preOrder();
cout << '\n';
Tree.postOrder();
cout << '\n';
Tree.levelOrder();

return 0;
}
``````

## q4x3's solution

``````/**
* 树的前序后序遍历
**/
#include <iostream>
#include <stdio.h>

using namespace std;

const int MAXN = 1e5 + 233;
int l[MAXN], r[MAXN], val[MAXN], vis[MAXN], q[MAXN << 1];
int N, rt;

void pre(int rt) {
printf("%d ", val[rt]);
int son = l[rt];
if(!son) return;
while(1) {
pre(son);
son = r[son];
if(son == 0) break;
}
return;
}

void pos(int rt) {
int son = l[rt];
if(!son) {
printf("%d ", val[rt]);
return;
}
while(1) {
pos(son);
son = r[son];
if(son == 0) break;
}
printf("%d ", val[rt]);
return;
}

void seq() {
int head = 0, rear = 0;
q[rear ++] = rt;
printf("%d ", val[top]);
int son = l[top];
while(1) {
if(!son) break;
q[rear ++] = son;
son = r[son];
}
}
}

int main() {
scanf("%d", &N);
for(int i = 1;i <= N;++ i) {
scanf("%d%d%d", &l[i], &r[i], &val[i]);
vis[l[i]] = 1;
vis[r[i]] = 1;
}
for(int i = 1;i <= N;++ i) {
if(!vis[i]) {
rt = i;
break;
}
}
pre(rt); putchar('\n');
pos(rt); putchar('\n');
seq(); putchar('\n');
}
``````

## skyzh's solution

``````#include <iostream>

using namespace std;

template <typename T>
struct Node {
T x;
int l, sibling;
Node() : l(0), sibling(0) {}
Node(const T& x, int l = 0, int r = 0) : x(x), l(l), sibling(r) {}
};

template <typename T>
struct Tree {
Node <T> *nodes;
Tree(int cap) : nodes(new Node<T> [cap]) {}
~Tree() { delete [] nodes; }
};

Tree <int> tree(100001);
bool is_child[100001] = { 0 };

void pre_traverse(const Tree<int> & tree, int node) {
if (node == 0) return;
const Node<int> &ptr = tree.nodes[node];
printf("%d ", ptr.x);
pre_traverse(tree, ptr.l);
pre_traverse(tree, ptr.sibling);
}

void post_traverse(const Tree<int> & tree, int node) {
if (node == 0) return;
const Node<int> &ptr = tree.nodes[node];
post_traverse(tree, ptr.l);
printf("%d ", ptr.x);
post_traverse(tree, ptr.sibling);
}

template <typename T>
struct Queue {
T* d;
int f, r;
Queue(int cap) : d(new T[cap]), f(0), r(0) {}
bool empty() { return f == r; }
void enqueue(const T& x) { d[r++] = x; }
const T dequeue() { return d[f++]; }
~Queue() { delete[] d; }
};

void level_traverse(const Tree<int> & tree, int root) {
if (root == 0) return;
Queue <int> q(300000);
q.enqueue(root);
while (!q.empty()) {
const Node<int>& node = tree.nodes[q.dequeue()];
printf("%d ", node.x);
if (node.l != 0) {
q.enqueue(node.l);
int ptr = tree.nodes[node.l].sibling;
while (ptr) {
q.enqueue(ptr);
ptr = tree.nodes[ptr].sibling;
}
}
}
}

int main() {
int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d%d%d", &tree.nodes[i].l, &tree.nodes[i].sibling, &tree.nodes[i].x);
is_child[tree.nodes[i].l] = is_child[tree.nodes[i].sibling] = true;
}
int root = 0;
for (int i = 1; i <= N; i++) {
if (!is_child[i]) root = i;
}
pre_traverse(tree, root);
printf("\n");
post_traverse(tree, root);
printf("\n");
level_traverse(tree, root);
printf("\n");
return 0;
}
``````

## victrid's solution

``````#include <cstdio>
#include <iostream>
using namespace std;

struct tree {
tree* left;
tree* brat;
int weight;
bool isroot;
tree() : left(nullptr), brat(nullptr), weight(0), isroot(true){};
};

tree seq[1000002] = {};

//pretrav
bool pretrav_f = false;
void pretrav(tree* root) {
if (pretrav_f)
printf(" ");
pretrav_f = true;
printf("%d", root->weight);
if (root->left != nullptr)
pretrav(root->left);
if (root->brat != nullptr)
pretrav(root->brat);
return;
}

//posttrav
bool posttrav_f = false;
void posttrav(tree* root) {
if (root->left != nullptr)
posttrav(root->left);
if (posttrav_f)
printf(" ");
posttrav_f = true;
printf("%d", root->weight);
if (root->brat != nullptr)
posttrav(root->brat);
return;
}

//bfstrav
tree* datastorage[1000003] = {nullptr};
tree** frontptr;
tree** endptr;
void clearqueue() {
frontptr = datastorage;
endptr   = datastorage + 1;
}
void clearstack() {
endptr = datastorage;
}
void enqueue(tree* cr) {
*endptr = cr;
endptr++;
}
bool qempty() {
return frontptr + 1 == endptr;
}
void enstack(tree* cr) {
*endptr = cr;
endptr++;
}
tree* destack() {
if (endptr == datastorage)
return nullptr;
else
endptr--;
return *endptr;
}
tree* dequeue() {
if (frontptr + 1 == endptr)
return nullptr;
else
frontptr++;
return *frontptr;
}
bool bfstrav_f = false;
void bfstrav(tree* root) {
clearqueue();
enqueue(root);
while (!qempty()) {
tree* rt = dequeue();
while (rt != nullptr) {
if (bfstrav_f)
printf(" ");
bfstrav_f = true;
printf("%d", rt->weight);
if (rt->left != nullptr)
enqueue(rt->left);
rt = rt->brat;
}
}
return;
}
int main() {
int t, l, b, vl, root;
scanf("%d", &t);
for (int i = 1; i <= t; i++) {
scanf("%d %d %d", &l, &b, &vl);
if (l != 0) {
seq[i].left         = seq + l;
seq[i].left->isroot = false;
}
if (b != 0) {
seq[i].brat         = seq + b;
seq[i].brat->isroot = false;
}
seq[i].weight = vl;
}
for (int i = 1; i <= t; i++)
if (seq[i].isroot) {
root = i;
break;
}
pretrav(seq + root);
printf("\n");
posttrav(seq + root);
printf("\n");
bfstrav(seq + root);
printf("\n");

return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
void pre(int x){
cout<<v[x]<<" ";
int p=l[x];
while (p) {pre(p); p=r[p];}
}
void post(int x){
int p=l[x];
while (p) {post(p); p=r[p];}
cout<<v[x]<<" ";
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%d%d%d",&l[i],&r[i],&v[i]);
s[l[i]]=1;
s[r[i]]=1;
}
for (int i=1;i<=n;++i)
if (!s[i]) root=i;
pre(root);
cout<<endl;
post(root);
cout<<endl;
queue[0]=root;
while (p) {
queue[tail++]=p;
p=r[p];
}
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 100010;
struct node {
int lson = 0, rbro = 0, value = 0;
};
node a[MAX_N];

void preorder(int t) {

cout << a[t].value << " ";
if (a[t].lson) preorder(a[t].lson);
if (a[t].rbro) preorder(a[t].rbro);
}

void postorder(int t) {

if (a[t].lson) postorder(a[t].lson);
cout << a[t].value << " ";
if (a[t].rbro) postorder(a[t].rbro);
}

void level(queue<int> t) {

queue<int> next;
while (!next.empty()) next.pop();
while (!t.empty()) {
int temp = t.front();
t.pop(); cout << a[temp].value << " ";
if (a[temp].lson) {
next.push(a[temp].lson);
int temp2 = a[a[temp].lson].rbro;
while (temp2) {
next.push(temp2);
temp2 = a[temp2].rbro;
}
}
}
if (!next.empty()) level(next);
}

int main() {

ios::sync_with_stdio(false);
int n; cin >> n;
int pre[MAX_N]; memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; ++i) {
int temp, lson, rbro;
cin >> lson >> rbro >> temp;
a[i].lson = lson;
a[i].rbro = rbro;
a[i].value = temp;
pre[lson] = i;
if (rbro) {
pre[rbro] = pre[i] = -1;
}
}
int root;
for (root = 1; root <= n; ++root) if (pre[root] == 0) break;

preorder(root);
cout << endl;
postorder(root);
cout << endl;
queue<int> p; p.push(root);
level(p);
cout << endl;
return 0;
}
``````

## Zsi-r's solution

``````#include <iostream>

using namespace std;
//树的后根遍历 == 二叉树的中序遍历
//树的先根遍历 == 二叉树的先序遍历

class node
{
public:
int data = NULL;
int lchild = 0, brother = 0;
node() {};
node(int d, int l, int b) : data(d), lchild(l), brother(b){};
node(node &x) { data = x.data, lchild = x.lchild, brother = x.brother; }
~node(){};
};

{
private:
struct nodeInQueue{
node data;
nodeInQueue *next;
nodeInQueue (const node &x, nodeInQueue *N = NULL)
{
data=x;next=N;
}
nodeInQueue() : next(NULL) {};
~nodeInQueue() {};
};

nodeInQueue *front,*rear;//队不空时，front和rear都有数据，当队长为1时，front和rear所指相同

public:
bool isEmpty()const ;
void enQueue(const node &x);
node deQueue();
};

{
front = rear = NULL;
}

{
nodeInQueue *tmp;
while(front != NULL)
{
tmp = front;
front = front ->next;
delete tmp;
}
}

{
return front == NULL;
}

{
if (rear == NULL) front = rear = new nodeInQueue (x);
else
rear=rear->next=new nodeInQueue (x);
}

{
nodeInQueue *tmp=front;
node value = front ->data;
front = front ->next;
if (front==NULL)rear=NULL;
delete tmp;
return value;
}

void pre(int accessnow,node*tree)
{
cout << tree[accessnow].data << " ";
if (tree[accessnow].lchild != 0)
pre(tree[accessnow].lchild-1, tree);
if (tree[accessnow].brother != 0)
pre(tree[accessnow].brother-1, tree);
return;
}

void post(int accessnow,node*tree)
{
if (tree[accessnow].lchild != 0)
post(tree[accessnow].lchild-1, tree);

cout << tree[accessnow].data << " ";

if (tree[accessnow].brother != 0)
post(tree[accessnow].brother-1, tree);
return;
}

node temp;
while (!s.isEmpty()){
temp = s.deQueue();
if (temp.lchild!=0)
s.enQueue(tree[temp.lchild-1]);
cout << temp.data << ' ';
while(temp.brother!=0){
temp = tree[temp.brother-1];
cout << temp.data << ' ';
if (temp.lchild!=0)
s.enQueue(tree[temp.lchild-1]);
}
}
}

int main()
{
int NumNode;
cin >> NumNode;
node *tree = new node[NumNode];

int RootLine;
bool *FindRoot = new bool[NumNode+1];
for (int i = 0; i < NumNode + 1;i++)
FindRoot[i] = false;

for (int i = 0; i < NumNode;i++)
{
cin >> tree[i].lchild >> tree[i].brother >> tree[i].data;
FindRoot[tree[i].lchild] = true;
FindRoot[tree[i].brother] = true;
}

for (RootLine = 1; RootLine < NumNode + 1;RootLine ++)
{
if (!FindRoot[RootLine])
break;
}

pre(RootLine-1, tree);
cout << endl;
post(RootLine-1, tree);

que.enQueue(tree[RootLine-1]);

cout << endl;
level(que, tree);
return 0;
}
``````