数据结构05：给出指定二叉树求其先中后序遍历

数据结构05：给出指定二叉树求其先中后序遍历

给出指定二叉树求其先中后序遍历

函数递归法(深度优先：先中后序；广度优先：层序)

先序递归中序递归后序递归 循环实现法

先序循环中序循环后序循环 源代码验证实现

函数递归法(深度优先：先中后序；广度优先：层序) 先序递归

void PreOrder(BiTree T){
    
    if(T != nullptr){
        visit(T);
        PreOrder(T->lChild);
        PreOrder(T->rChild);
    }
}

中序递归

void InOrder(BiTree T){
    
    if(T != nullptr){
        InOrder(T->lChild);
        visit(T);
        InOrder(T->rChild);
    }
}

后序递归

void PostOrder(BiTree T){
    
    if(T != nullptr){
        PostOrder(T->lChild);
        PostOrder(T->rChild);
        visit(T);
    }
}

循环实现法 先序循环

void PreOrder_Loop(BiTree T){
    
    BiTree s = T;
    BiTree node;
    while(!stack_Order.empty() || s != nullptr){
        if(s != nullptr){
            stack_Order.push(s);
            visit(s);
            s = s->lChild;
        }
        else{
            node = stack_Order.top();
            s = node->rChild;
            stack_Order.pop();
        }
    }
}

中序循环

void InOrder_Loop(BiTree T){
    
    BiTree s = T;
    BiTree node;
    while(!stack_Order.empty() || s != nullptr){
        if(s != nullptr){
            stack_Order.push(s);
            s = s->lChild;
        }
        else{
            node = stack_Order.top();
            visit(node);
            s = node->rChild;
            stack_Order.pop();
        }
    }
}

后序循环

void PostOrder_Loop(BiTree T){
    
    BiTree s = T;
    BiTree node;
    while(!stack_Order.empty() || s != nullptr){
        if(s != nullptr){
            stack_Order.push(s);
            stack_PostOutput.push(s);
            s = s->rChild;
        }
        else{
            node = stack_Order.top();
            s = node->lChild;
            stack_Order.pop();
        }
    }
    while(!stack_PostOutput.empty()){
        visit(stack_PostOutput.top());
        stack_PostOutput.pop();
    }
}

源代码验证实现