二叉树的先序/中序/后序遍历的递归/非递归实现

练手代码。参考《王道考研--数据结构》二叉树一章实现。

(未测试）

三种二叉树的遍历的非递归算法基本结构类似：

 

while(node!=NULL && !isEmpty){

       if(node!=NULL){

            //根据算法选取node或其右子树进栈

            node = node->left；

            continue;

       }

       pop(stack,node)

       //根据算法visit及处理右子树

       //后续遍历时需node置空

}

 

Feb.26th 2013 update: add line 71 in DLRN code.

void LNR(Node* node){
    if(node == NULL) return ;
    LNR(node->left);
    visit(node);
    LNR(node->right;
}

void NLR(Node * node){
    if(node == NULL) return;
    visit(node);
    NLR(node->left);
    NLR(node->right);
}

void LRN(Node * node){
    if(node == NULL) return;
    LRN(node->left);
    LRN(node->right);
    visit(node);
}

void DLNR(Node* node){
    if(node == NULL) return ;
    Stack * stack;
    initialStack(stack);
    while(node!=NULL && !isEmpty(stack)){
        if(node!=NULL){
            push(stack, node);
            node=node->left;
            continue;
        }
        pop(stack,node);
        visit(node);
        node=node->right;
    }
}

void DNLR(Node * node){
    if(node == NULL) return;
    Stack * stack;
    initialStack(stack);
    while(node!=NULL && !isEmpty(stack)){
        if(node!=NULL){
            visit(node);
            if(node->right!=NULL)
                push(stack, node);
            node=node->left;
            continue;
        }
        pop(stack, node);
        visit(node);
        if(node->right!=NULL)
                push(stack, node);
        node=node->left;
    }
}

void DLRN(Node *node){
    if(node == NULL) return;
    Stack* stack;
    initialStack(stack);
    Node* lastVisted = NULL;
    while(node!=NULL && !isEmpty(stack)){
        if(node!=NULL){
            push(stack, node);
            node = node->left;
            continue;
        }
        pop(stack, node);
        if(node->right!=NULL && node->right!=lastVisted){
            push(node, stack);
            node = node->right;
            push(node, stack);
            node = node->left;
        }
        else{
            visit(node);
            lastVisited = node;
            node = NULL;
        }
    }

}