二叉树遍历的递归和非递归实现-蒲公英云

二叉树遍历的递归和非递归实现

所谓二叉树的遍历，是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问且仅被访问一次

前序遍历

1、递归实现

如果二叉树非空，则先访问根结点—左子树—右子树

void PreOrder(BiTree T){
    if(T!=NULL){
    visit(T);//先访问根结点
    PreOrder(T->lchild); //先序遍历左子树
    PreOrder(T->rchild); //先序遍历右子树
    }
}

2、非递归实现

借助栈实现

void PreOrder(BiTree T){
    InitStack(s);//初始化一个栈
    BiTree p=T;//初始化一个遍历指针
    while(p!=NULL||StackEmpty(s)!=NULL){//当p非空，或者栈非空时
        if(p!=NULL){
            visit(p); //先访问根结点
            Push(S,p);//将当前节点入栈
            p=p->lchild;
        }else{ //此时p的左子树均已访问
                Pop(S,p); //将栈顶元素出栈
                p=p->rchild;
        }
    }
}

中序遍历

递归实现

void InOrder(BiTree T){
    if(T!=NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
    }
}

非递归实现

void InOrder(BiTree T){
    InitStack(S);
    BiTree p=T;
    while(p!=NULL||StackEmpty(S)!=NULL){
        if(p!=NULL){
            Push(S,p);//将p入栈
            p=p->lchild;
        }else{
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}

后序遍历

递归实现

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

非递归实现

void PostOrder(BiTree T){
    InitStack(S);
    BiTree p=T;q=NULL; //设置一个p指针用来标识当前结点的右子树是否被访问
    while(p!=NULL||StackEmpty(S)!=NULL){
        if(p!=NULL){
            Push(S,p);
            p=p->lchild;
        }else{
            GetTop(s,p);//取栈顶元素
            if(p->rchild==NULL||p->rchild==q){//p的右子树为空或者p的右子树已经被访问
                visit(P);
                Pop(S,p);
                q=p;
                p=NULL;//将p设置为空是为了继续读取下一个栈顶元素
            }else{
                p=p->rchild;
            }
        }
    }
}