二叉树先序、中序、后序遍历的非递归实现_随笔

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

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

结构体定义先序遍历的非递归实现中序遍历的非递归实现后序遍历的非递归实现完整代码
语言： C++

结构体定义

#include 
using namespace std;
#define MAXSIZE 1000

//########################################数据结构定义#########################################
// 二叉树定义
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef BiTNode *ElemType;
//顺序栈
typedef struct {
    ElemType data[MAXSIZE];
    int top;
} SqStack;
//########################################数据结构定义#########################################

先序遍历的非递归实现

先序遍历为根左右的访问顺序，用栈实现；

沿着左孩子依次访问根结点并将结点入栈，直到结点点为空，执行第二步；出栈，若出栈元素有右孩子，则转入右子树中执行第一步，即在右子树中沿着其左孩子依次入栈；若出栈元素无右孩子，则继续执行第二步。

// 先序遍历的非递归实现
void PreOrderNoRecursive(BiTree T)
{
    SqStack S;
    InitStack(S);
    BiTNode *p = T;
    while (p || !IsEmpty(S))
    { // 当p不空和栈不空均成立是结束循环
        if (p)
        {
            printf("%c", p->data); // 访问
            Push(S, p);            //根节点进栈
            p = p->lchild;         // 沿和左孩子依次入栈，直到为Null
        }
        else
        {                  //根节点为空
            Pop(S, p);     // 出栈
            p = p->rchild; // 向右子树走
        }
    }
}

中序遍历的非递归实现

中序遍历为左根右的访问顺序，用栈实现；

沿着左孩子依次将根结点入栈，直到结点点为空，执行第二步；出栈并访问，若出栈元素有右孩子，则转入右子树中执行第一步，即在右子树中沿着其左孩子依次入栈；若出栈元素无右孩子，则继续执行第二步。

// 中序遍历的非递归实现
void InOrder_no_recursive(BiTree T)
{
    SqStack S;
    InitStack(S);
    BiTNode *p = T;
    while (p || !IsEmpty(S))
    { // 当p不空和栈不空均成立是结束循环
        if (p)
        {
            Push(S, p);    //根节点进栈
            p = p->lchild; // 沿和左孩子依次入栈，直到为Null
        }
        else
        {                          //根节点为空
            Pop(S, p);             // 出栈
            printf("%c", p->data); // 访问
            p = p->rchild;         // 向右子树走
        }
    }
}

后序遍历的非递归实现

后序遍历为左右根的访问顺序，但是相比于先序和中序较难。因为出栈时需要检查是否有右孩子，若有则需要处理右子树。然而，右孩子是比根节点先遍历的，所以我们无法保证当前的栈顶元素结点的右孩子是否被访问过。所以我们可以通过以下的方法来确定右子树是否被访问过：

增加一个指向前驱结点的指针pre，若栈顶元素右孩子存在且等于pre，则说明右子树已经被遍历过了，接下来就是出栈并访问当前子树的根节点；若右孩子存在且不等于pre，则转入右子树处理。结点定义时增加一个标志域tag，表示当前结点是否被访问过。

流程：

沿着左孩子依次将根结点入栈，直到结点点为空，执行第二步；读栈顶元素，若出栈元素有右孩子且不等于pre，则转入右子树中执行第一步，即在右子树中沿着其左孩子依次入栈；若出栈元素无右孩子或者右孩子等于pre，则继续执行第二步。

// 后序遍历的非递归实现
void PostOrderNoRecursive(BiTree T)
{
    SqStack S;
    InitStack(S);
    BiTNode *p = T, *pre = T; // pre指向前驱结点
    while (p || !IsEmpty(S))
    {
        // @1
        if (p)
        { // p不为空，沿左孩子依次将根节点入栈
            Push(S, p);
            p = p->lchild;
        }
        // @2
        else
        {
            GetTop(S, p); // 读栈顶元素
            if (p->rchild &&
                p->rchild !=
                    pre)
            { // 栈顶元素右孩子存在且不等于前驱结点，则转入其右子树执行@1
                p = p->rchild;
            }
            else
            {                          // 右孩子不存在，则出栈，继续执行@2
                Pop(S, p);             //  出栈
                printf("%c", p->data); //  访问出栈元素
                pre = p;               //  更新前驱结点指针
                p = NULL;              //  将p置为NULL，保证下一次循环继续执行@2 *** 作
            }
        }
    }
}

完整代码

#include 
using namespace std;
#define MAXSIZE 1000

//########################################数据结构定义#########################################
// 二叉树定义
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef BiTNode *ElemType;
//顺序栈
typedef struct
{
    ElemType data[MAXSIZE];
    int top;
} SqStack;
//########################################数据结构定义#########################################
//########################################栈的基本方法#########################################
//初始化栈
void InitStack(SqStack &S) { S.top = -1; }

//判断栈是否空
bool IsEmpty(SqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}

//进栈
bool Push(SqStack &S, ElemType e)
{
    if (S.top == MAXSIZE - 1) // 栈满
        return false;
    else
    {
        S.data[++S.top] = e; // 指针先加1 再入栈
        return true;
    }
}

//出栈
bool Pop(SqStack &S, ElemType &e)
{
    if (S.top == -1) //栈空，无法出栈
        return false;
    else
        e = S.data[S.top--];
    return true;
}

//读栈顶元素
bool GetTop(SqStack S, ElemType &e)
{
    if (S.top == -1)
        return false;
    else
        e = S.data[S.top];
    return true;
}
//########################################栈的基本方法#########################################

//########################################二叉树的基本方法#########################################
// 中序遍历的非递归实现
void InOrder_no_recursive(BiTree T)
{
    SqStack S;
    InitStack(S);
    BiTNode *p = T;
    while (p || !IsEmpty(S))
    { // 当p不空和栈不空均成立是结束循环
        if (p)
        {
            Push(S, p);    //根节点进栈
            p = p->lchild; // 沿和左孩子依次入栈，直到为Null
        }
        else
        {                          //根节点为空
            Pop(S, p);             // 出栈
            printf("%c", p->data); // 访问
            p = p->rchild;         // 向右子树走
        }
    }
}

// 先序遍历的非递归实现
void PreOrderNoRecursive(BiTree T)
{
    SqStack S;
    InitStack(S);
    BiTNode *p = T;
    while (p || !IsEmpty(S))
    { // 当p不空和栈不空均成立是结束循环
        if (p)
        {
            printf("%c", p->data); // 访问
            Push(S, p);            //根节点进栈
            p = p->lchild;         // 沿和左孩子依次入栈，直到为Null
        }
        else
        {                  //根节点为空
            Pop(S, p);     // 出栈
            p = p->rchild; // 向右子树走
        }
    }
}


// 后序遍历的非递归实现
void PostOrderNoRecursive(BiTree T)
{
    SqStack S;
    InitStack(S);
    BiTNode *p = T, *pre = T; // pre指向前驱结点
    while (p || !IsEmpty(S))
    {
        // @1
        if (p)
        { // p不为空，沿左孩子依次将根节点入栈
            Push(S, p);
            p = p->lchild;
        }
        // @2
        else
        {
            GetTop(S, p); // 读栈顶元素
            if (p->rchild &&
                p->rchild !=
                    pre)
            { // 栈顶元素右孩子存在且不等于前驱结点，则转入其右子树执行@1
                p = p->rchild;
            }
            else
            {                          // 右孩子不存在，则出栈，继续执行@2
                Pop(S, p);             //  出栈
                printf("%c", p->data); //  访问出栈元素
                pre = p;               //  更新前驱结点指针
                p = NULL;              //  将p置为NULL，保证下一次循环继续执行@2 *** 作
            }
        }
    }
}

// 先序遍历构造二叉树
void PreOrderCreatBiTree(BiTree &T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        T = NULL;
    else
    {
        T = (BiTNode *)malloc(sizeof(BiTNode));
        T->data = ch;
        PreOrderCreatBiTree(T->lchild);
        PreOrderCreatBiTree(T->rchild);
    }
}

int main()
{
    BiTree T;
    PreOrderCreatBiTree(T);  //先序建立二叉树  ABC##DE#G##F###
    PostOrderNoRecursive(T); // 
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5710510.html

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

发表评论

评论列表（0条）