#include <iostream>
#include <cstdio>
#include <vector>
#include <stack> #define ls(x) (((x + 1)<<1) - 1)
#define rs(x) ((x + 1)<<1) using namespace std; const int NULLVAL = -; typedef struct Node{
struct Node *left;
struct Node *right;
int val;
}TNode, * PNode; typedef struct Node2{
PNode btNode;
bool isFirst;
Node2(){
isFirst = true;
}
}traNode, * PTraNode; void createBTree(PNode rt, vector<int>v, int cur)
{
rt -> val = v[cur];
if (ls(cur) < v.size() && v[ls(cur)] != NULLVAL){
PNode newNode = new TNode();
rt -> left = newNode;
createBTree(rt -> left, v, ls(cur));
}if (rs(cur) < v.size() && v[rs(cur)] != NULLVAL){
PNode newNode = new TNode();
rt -> right = newNode;
createBTree(rt -> right, v, rs(cur));
}
} void travelTree(PNode rt)
{
if(rt){
travelTree(rt -> left);
cout<<"node: "<<rt -> val<<endl;
travelTree(rt -> right);
}
} void travelWithoutRecursiveInorder(PNode rt)
{
if(rt == NULL) return ;
PNode p = rt;
stack<PNode>sta; while(!sta.empty() || p != NULL){ while(p != NULL){
sta.push(p);
p = p -> left;
}
if( !sta.empty()){
p = sta.top();
sta.pop();
cout<<"val: "<<p->val<<endl;
p = p -> right;
}
}
} void travelWithoutRecursivePreorder(PNode rt)
{
if(rt == NULL) return ;
PNode p = rt;
stack<PNode>sta;
while(p || sta.empty() == false){
while(p){
sta.push(p);
cout<<"val: "<<p->val<<endl;
p = p -> left;
}
if(!sta.empty()){
p = sta.top();
sta.pop();
p = p -> right;
}
}
} /*
* Postorder后序遍历骚味复杂一点点,因对于任意一个节点需要先访问其left child 然后访问 其right child 最后第二次访问到该节点
* 才能输出该点值.所以 需要再另行设计一个数据结构 traNode 里面封装了{TreeNode 和 isFirst(一个标记用来指示这个节点是否是第一次访问到)}
* 只有第二次访问到才会输出该值.
* 其实还有第二种方法:
*/
void travelWithoutRecursivePostorder(PNode rt)
{
if(rt == NULL) return;
stack<PTraNode>sta;
PNode p = rt;
while(p || !sta.empty()){
while(p){
PTraNode ptn = new traNode();
ptn ->btNode = p;
sta.push(ptn);
p = p -> left;
}
if(!sta.empty()){
PTraNode ptn = sta.top();
sta.pop();
if(ptn->isFirst ){
ptn->isFirst = false;
sta.push(ptn);
p = ptn->btNode -> right;
}else{
cout<<"val: "<<ptn->btNode->val<<endl;
p = NULL;
}
}
}
}
int main()
{
freopen("in", "r", stdin);
PNode root = new TNode();
int n;
vector<int>v;
cin>>n;
for(int i = ; i < n; i ++){
int r;
cin>>r;
v.push_back(r);
}
v.push_back(NULLVAL);
createBTree(root, v, );
//travalTree(root);
cout<<"Preorder:"<<endl;
travelWithoutRecursivePreorder(root);
cout<<"Inorder"<<endl;
travelWithoutRecursiveInorder(root);
cout<<"Postorder"<<endl;
travelWithoutRecursivePostorder(root);
return ;
}