最新消息:点击查看大S的省钱秘笈

二叉树的非递归遍历 C语言版

编程相关 Slyar 14145浏览 15评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

上周数据结构课在讲二叉树的遍历,老师只讲递归算法,没有什么技术含量,遂自己琢磨非递归算法实现…

前序遍历:先访问根节点,再访问左子树,最后访问右子树。设置一个栈,出栈即为访问节点。先将根节点进栈,在栈不空时一直如下循环:出栈,访问,将其右孩子进栈,再将左孩子进栈。

中序遍历:先访问左子树,再访问根节点,最后访问右子树。设置一个栈,出栈即为访问节点。先将根节点的左节点全部进栈,然后出栈一个节点,访问。将该节点的右孩子节点进栈,再将右孩子节点的所有左节点全部进栈…如此这般直到栈空为止。

后序遍历:先访问左子树,再访问右子树,最后访问根节点。设置一个栈。先将根节点的左节点全部进栈。出栈一个节点,将该节点的右孩子进栈,再将右孩子的左节点全部进栈…当一个节点的左、右孩子都被访问过后再访问该节点,如此这般直到栈空为止。(判断某节点的右孩子是否被访问,需要单独设置一个指针跟踪刚刚访问的节点。在后序遍历中,某节点的右孩子节点一定刚好在该节点之前被访问)

因为代码的重点是非递归遍历,所以建立二叉树的过程我就使用了”前序递归”。对于如下一棵树,以”#”代表空节点,前序递归建立二叉树需要的输入数据和前序遍历的顺序是一样的,且每个叶子节点的左右孩子均为”#”。

输入:ABDH##I##EJ##K##CF#L##G##
前序遍历:A B D H I E J K C F L G
中序遍历:H D I B J E K A F L C G
后序遍历:H I D J K E B L F G C A

二叉树

代码如下:

/*
Slyar
//www.slyar.com
2009.5.16
*/
#include 
#include 

#define MAXSIZE 200

/* 定义二叉树节点类型 */
typedef struct node
{
    char data;
    struct node *lchild, *rchild;
}BTNode;

/* 函数声明 */
BTNode* CreatBitTree();
void PreOrder(BTNode*);
void InOrder(BTNode*);
void PostOrder(BTNode*);

/* 主函数 */
int main()
{
    BTNode *root = NULL;
    root = CreatBitTree();
    PreOrder(root);
    InOrder(root);
    PostOrder(root);
    system("pause");
    return 0;
}

/* 递归前序建立二叉树 */
BTNode* CreatBitTree()
{
    char ch;
    BTNode *b;
    scanf("%c", &ch);
    /* 遇到空节点停止递归 */
    if (ch == '#')
    {
        b = NULL;
    }
    else
    {
        b = (BTNode*) malloc(sizeof(BTNode));
        /* 建立根节点 */
        b->data = ch;
        /* 递归先序建立左子树 */
        b->lchild = CreatBitTree();
        /* 递归先序建立右子树 */
        b->rchild = CreatBitTree();
    }
    return b;
}

/* 非递归前序遍历二叉树 */
void PreOrder(BTNode* b)
{
    BTNode *stack[MAXSIZE], *p;
    int top = -1;
    if (b != NULL)
    {
        /* 根节点入栈 */
        top++;
        stack[top] = b;
        /* 栈不空时循环 */
        while (top > -1)
        {
            /* 出栈并访问该节点 */
            p = stack[top];
            top--;
            printf("%c ", p->data);
            /* 右孩子入栈 */
            if (p->rchild != NULL)
            {
                top++;
                stack[top] = p->rchild;
            }
            /* 左孩子入栈 */
            if (p->lchild != NULL)
            {
                top++;
                stack[top] = p->lchild;
            }
        }
        printf("\n");
    }
}

/* 非递归中序遍历二叉树 */
void InOrder(BTNode* b)
{
    BTNode *stack[MAXSIZE], *p;
    int top = -1;
    if (b != NULL)
    {
        p = b;
        while (top > -1 || p != NULL)
        {
            /* 扫描p的所有左节点并入栈 */
            while (p != NULL)
            {
                top++;
                stack[top] = p;
                p = p->lchild;
            }
            if (top > -1)
            {
                /* 出栈并访问该节点 */
                p = stack[top];
                top--;
                printf("%c ", p->data);
                /* 扫描p的右孩子 */
                p = p->rchild;
            }
        }
        printf("\n");
    }
}

/* 非递归后序遍历二叉树 */
void PostOrder(BTNode* b)
{
    BTNode *stack[MAXSIZE], *p;
    int sign, top = -1;
    if (b != NULL)
    {
        do
        {
            /* b所有左节点入栈 */
            while (b != NULL)
            {
                top++;
                stack[top] = b;
                b = b->lchild;
            }
            /* p指向栈顶前一个已访问节点 */
            p = NULL;
            /* 置b为已访问 */
            sign = 1;
            while (top != -1 && sign)
            {
                /* 取出栈顶节点 */
                b = stack[top];
                /* 右孩子不存在或右孩子已访问则访问b */
                if (b->rchild == p)
                {
                    printf("%c ", b->data);
                    top--;
                    /* p指向被访问的节点 */
                    p = b;
                }
                else
                {
                    /* b指向右孩子节点 */
                    b = b->rchild;
                    /* 置未访问标记 */
                    sign = 0;
                }
            }
        }while (top != -1);
        printf("\n");
    }
}

转载请注明:Slyar Home » 二叉树的非递归遍历 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (15)

  1. 感谢LZ,思路很巧妙,受益良多.不过我发现InOrder函数无需额外设置p变量和进行if(b!=NULL)的判断,这样也可以: void InOrder(BTNode* b) { BTNode *stack[MAXSIZE]; int top = -1; while (top > -1 || b != NULL) { while (b != NULL) { stack[++top] = b; b = b->lchild; } if (top > -1) { b = stack[top--]; printf("%c ", b->data); b = b->rchild; } } }
    xn6年前 (2014-07-30)回复
  2. 有没有可以输入两种遍历序列 然后生成一棵树并且输出树形?老师要求好高
    7年前 (2014-01-03)回复
    • 二叉树重建?什么叫输出树形?
      Heracles7年前 (2014-01-05)回复
  3. 我自己写的 https://lk1ngaa7.cf/?p=318
    liukai97927年前 (2013-11-21)回复
  4. 看不懂 啊 最烦编程了
    奇闻趣事7年前 (2013-07-18)回复
  5. 为什么是右孩子先进栈?
    左岸代码右岸诗8年前 (2013-03-19)回复
    • 前序遍历 右孩子访问次序在左孩子之后,所以要陷入栈。
      7年前 (2013-08-13)回复
  6. 弱弱的问一下,BTNode *stack[MAXSIZE]是什么意思
    dkuhg9年前 (2011-10-22)回复
  7. @Churchill 你看清楚再评论,不要误导别人啊
    匿名9年前 (2011-08-09)回复
  8. @Churchill 呃,你再仔细往下看看吧...
    Slyar11年前 (2010-01-08)回复
  9. 你好。冒昧的说一句。你上面程序中后续遍历的第一个if(b != NULL)条件错了,应该改成while(b != NULL),这样才能对栈持续进行操作。
    Churchill11年前 (2010-01-08)回复
  10. 很好!非常感谢!!希望以后还能继续发表
    匿名11年前 (2009-12-27)回复
  11. 很强,谢谢分享
    Dongfei11年前 (2009-07-29)回复
  12. 匿名12年前 (2009-05-30)回复
  13. 非递归的DFS,赞。
    Felix02112年前 (2009-05-18)回复