二叉树先序、中序、后序递归&&非递归

2021年9月7日 15点热度 0条评论 来源: 童话ing

这三种遍历,递归方式都很简单,大概就围绕着这样一个顺序:

先序:根左右,中序:左根右,后序:左右根。

对于非递归方式:由于采用栈(先进后出)这种数据结构存储结点,因此,结点入栈时需要考虑顺序和原来相反。

先序和中序都比较简单,后序相对较难,在代码中叙述。

先序:首先根结点入栈,访问根结点,然后结点入栈就先入右边,再入左边,因为退栈访问时候是先进后出的,而先序顺序是按照根左右这样一个顺序,最后就一直按照这样退栈访问再入栈即可。

中序:先入栈根结点,然后让指针一直沿着左子树走到最左下,途中将所有遇到的非空左子结点入栈,然后退栈访问,退栈时栈顶结点的右子结点入栈,继续上述操作即可。

/*
在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点
思路:对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,
此时该结点出现在栈顶,但是此时不能将其出栈并访问, 因此其右孩子还未被访问。所以接下来
按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可
以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出
现在栈顶,只有在第二次出现在栈顶时,能访问它。因此需要多设置一个变量标识该结点是否是第
一次出现在栈顶,或者用一个指针看该节点是否被访问过。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long LL;
typedef struct node
{
    struct node *lchild,*rchild;
    int val;
}node,*BiTree;
BiTree Creat(BiTree &T)//先序递归建立,根左右
{
    int val;
    scanf("%d",&val);
    if(val==0) T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(node));
        T->val=val;
        Creat(T->lchild);
        Creat(T->rchild);
    }
    return T;
}
void print_mid(BiTree T)//中序递归代码,左根右
{
    if(T==NULL) return;
    print_mid(T->lchild);
    printf("%d ",T->val);
    print_mid(T->rchild);
}
void print_post(BiTree T)//后序递归代码,左右根
{
    if(T==NULL) return;
    print_post(T->lchild);
    print_post(T->rchild);
    printf("%d ",T->val);
}
void Pre_Order(BiTree T)//先序非递归
{
    stack<BiTree>s;
    BiTree p=T;
    s.push(p);
    while(!s.empty())
    {
        p=s.top();
        s.pop();
        cout<<p->val<<" ";
        if(p->rchild) s.push(p->rchild);
        if(p->lchild) s.push(p->lchild);
    }
}
void Mid_Order(BiTree T)//中序非递归
{
    stack<BiTree>s;
    BiTree p=T;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p=p->lchild;
        }
        else
        {
            p=s.top();
            s.pop();
            cout<<p->val<<" ";
            p=p->rchild;
        }
    }
}
void Post_Order(BiTree T)//后序非递归
{
    stack<BiTree>s;
    BiTree p=T,r=NULL;
    //r用于指向最近访问过的结点,也可以在结点中增加一个标记,记录该结点是否被访问
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p=p->lchild;//先沿着左子树一直向下搜索
        }
        else
        {
            p=s.top();//取栈顶元素
            if(p->rchild&&p->rchild!=r)//有右子树且该节点第一次访问
            {
                p=p->rchild;
                s.push(p);
                p=p->lchild;
            }
            else//无右子树则将该结点出栈
            {
                p=s.top();
                s.pop();
                cout<<p->val<<" ";
                r=p;
                p=NULL;//结点访问完之后重置p指针
            }
        }
    }
}
int main()
{
    printf("先序输入一棵二叉树:\n");
    BiTree T=Creat(T);
    printf("中序递归输出二叉树序列:\n");
    print_mid(T);
    printf("\n后序递归输出二叉树序列:\n");
    print_post(T);
    printf("\n先序非递归输出二叉树序列:\n");
    Pre_Order(T);
    printf("\n中序非递归输出二叉树序列:\n");
    Mid_Order(T);
    printf("\n后序非递归输出二叉树序列:\n");
    Post_Order(T);
    return 0;
}
//测试数据:1 2 3 5 0 0 0 4 0 0 2 4 0 0 3 0 5 0 0

 

    原文作者:童话ing
    原文地址: https://blog.csdn.net/dl962454/article/details/82929073
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。