二叉树的非递归遍历

先序遍历

利用栈进行树的非递归便利遍历

void preOrder_v1(BTNode* bt){
    int max=50;
    BTNode* stack[max];
    int top=-1;
    while(bt || top!=-1){
        if(bt){
            printf("%d ",bt->val);
            stack[++top]=bt;
            bt=bt->lchild;
        }else{
            bt=stack[top--];
            bt=bt->rchild;
        }
    }
}

void preOrder_v2(BTNode* bt){
    int max=50;
    BTNode* stack[max];
    int top=-1;
    if(bt){
        stack[++top]=bt;
        while(top!=-1){
            bt=stack[top--];
            printf("%d ",bt->val);
            if(bt->rchild){
                stack[++top]=bt->rchild;
            }
            if(bt->lchild){
                stack[++top]=bt->lchild;
            }
        }
    }
}

void preOrder_v3(BTNode* bt){
    int max=50;
    BTNode* stack[max];
    int top=-1;
    while(bt || top!=-1){
        while(bt){
            printf("%d ",bt->val);
            stack[++top]=bt;
            bt=bt->lchild;
        }
        if(top!=-1){
            bt=stack[top--];
            bt=bt->rchild;
        }
    }
}

中序遍历

void inOrder(BTNode* bt){
    int max=50;
    BTNode* stack[max];
    int top=-1;
    while(bt || top!=-1){
        while(bt){
            stack[++top]=bt;
            bt=bt->lchild;
        }
        if(top!=-1){
            bt=stack[top--];
            printf("%d ",bt->val);
            bt=bt->rchild;
        }
    }
}

后序遍历

void postOrder(BTNode* bt){
    int max=50;
    BTNode* stack[max];
    int top=-1;
    BTNode* curr;
    BTNode* pre=NULL;
    if(bt){
        stack[++top]=bt;
        while(top!=-1){
            curr=stack[top];
            if((curr->lchild==NULL && curr->rchild==NULL)
                ||(pre!=NULL &&
                (pre==curr->lchild || pre==curr->rchild))){
                printf("%d ",curr->val);
                top--;
                pre=curr;
            }else{
                if(curr->rchild){
                    stack[++top]=curr->rchild;
                }
                if(curr->lchild){
                    stack[++top]=curr->lchild;
                }
            }
        }
    }
}

层次遍历

使用队列进行树的层次遍历（广度优先遍历，Breath-first Treaversal/Search）

void traverse_level(BTNode* bt){
    int max=50;
    BTNode* que[max];
    int front,rear;
    front=rear=0;
    if(bt){
        rear=(rear+1)%max;
        que[rear]=bt;
        while(front!=rear){
            front=(front+1)%max;
            bt=que[front];
            printf("%d ",bt->val);
            if(bt->lchild){
                rear=(rear+1)%max;
                que[rear]=bt->lchild;
            }
            if(bt->rchild){
                rear=(rear+1)%max;
                que[rear]=bt->rchild;
            }
        }
    }
}