递归实现

先序遍历

void PreTravel(BinTree T){
        if(!T)
           return;
        cout << bt << " ";
        PreTravel(T->left);
        PreTravel(T->right);
}

中序遍历

void PreTravel(BinTree T){
        if(!T)
           return;
        PreTravel(T->left);
		cout << bt << " ";
        PreTravel(T->right);
}

后序遍历

void PreTravel(BinTree T){
        if(!T)
           return;
        PreTravel(T->left);
        PreTravel(T->right);
		cout << bt << " ";
}

非递归实现

先序遍历

#define Null -1

typedef struct tnode{
    char data;
    int left = -1;
    int right = -1;
}*BinTree,tree;

void PreTravel(BinTree T,int bt){
    stack s = new snode();
    init(s);
    int temp;
    while(bt != Null || !(s->top == -1)){
        while(bt != Null){
			cout << bt << " ";
            push(s,bt+'0');
            bt = T[bt].left;
        }
        bt = pop(s) - '0';
        bt = T[bt].right;
    }
    delete s;
}

中序遍历

void InTravel(BinTree T,int bt){
    stack s = new snode();
    init(s);
    int temp;
    while(bt != Null || !(s->top == -1)){
        while(bt != Null){
            push(s,bt+'0');
            bt = T[bt].left;
        }
        bt = pop(s) - '0';
        cout << bt << " ";
        bt = T[bt].right;
    }
    delete s;
}

后序遍历

void PoTravel(BinTree T,int bt){
    stack s = new snode();
    init(s);
    int temp;
    int check[10] = {0};
    while(bt != Null || !(s->top == -1)){
        while(bt != Null){
            push(s,bt+'0');
            bt = T[bt].left;
        }
        bt = pop(s) - '0';
        check[bt]++;
        if(check[bt] == 1)
            push(s,bt+'0');
        else if(check[bt] == 2)
            cout << bt << " ";
        bt = T[bt].right;
    }
    delete s;
}

总结

递归实现比较简单，而非递归实现主要是通过栈来实现，其中前序和中序需要入栈一次，而后序遍历需要入栈两次