《Cracking the Coding Interview 》之 二叉树的创建 与 遍历(非递归+递归version)

#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 = -999;

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 = 0; i < n; i ++){
        int r;
        cin>>r;
        v.push_back(r);
    }
    v.push_back(NULLVAL);
    createBTree(root, v, 0);
    //travalTree(root);
    cout<<"Preorder:"<<endl;
    travelWithoutRecursivePreorder(root);
    cout<<"Inorder"<<endl;
    travelWithoutRecursiveInorder(root);
    cout<<"Postorder"<<endl;
    travelWithoutRecursivePostorder(root);
    return 0;
}