| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 691 人关注过本帖
标题:二叉树非递归遍历算法详解
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  问题点数:0  回复次数:0   
二叉树非递归遍历算法详解
二叉树非递归遍历算法详解
巧若拙(欢迎转载,但请注明出处:http://blog./qiaoruozhuo)

二叉树是一种很常见的非线性数据结构,它的应用非常广泛,有必要熟练掌握。二叉树的二叉链表存储表示如下:
typedef char ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode;

typedef struct BiTNode *BiTree;

二叉树的递归算法很容易实现,而且简明易懂,但非递归算法就不是那么好理解了。本文将结合代码详细解释遍历二叉树的三种不同方式。
采用非递归方式遍历二叉树,必须构造一个栈,利用栈后进先出的特点,按照一定顺序把各结点存入到栈中。由于访问二叉树总是要从根结点开始的,所以根结点总是要第一个入栈,但根结点的出栈时机要根据遍历的方式来定。
    先来看前序遍历方式。前序遍历是先输出根结点,再输出左子树,最后输出右子树,故要在访问其孩子结点前,先将根结点出栈,并输出其数据域,然后根据栈后进先出的特点,先将其右孩子入栈(如果有),再将其左孩子入栈(如果有)。代码如下:
void PreOrderTraverse_S_1(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点,栈stack[]用来存储结点
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        stack[++top] = BT; //根结点入栈
        while (top >= 0)
        {
            p = stack[top--]; //栈顶元素出栈
            printf("%c", p->data);//输出该结点
            if (p->rchild != NULL) //如果该结点有右孩子,将右孩子入栈
            {
                 stack[++top] = p->rchild;
            }
            if (p->lchild != NULL) //如果该结点有左孩子,将左孩子入栈,按照后入先出原则,左孩子先出栈
            {
                 stack[++top] = p->lchild;
            }
        }
    }   
}

    函数PreOrderTraverse_S_1()充分利用了栈后进先出的特点,思路清晰,代码简洁。其实,我们还可以通过分析前序遍历二叉树的特征,先输出当前根结点数据,并将其入栈,再遍历左孩子,然后栈顶元素出栈,访问其右孩子。依此反复循环,直到输出所有结点(即栈空)为止。代码如下:
void PreOrderTraverse_S_2(BiTree BT) //采用非递归方式前序遍历二叉树BT
{
    BiTree p, stack[MAXSIZE];//p表示当前结点,栈stack[]用来存储结点
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        p = BT;
        while (p || top >= 0)
        {
            if (p != NULL) //先输出结点数据,再遍历左孩子
            {
                printf("%c", p->data);//输出该结点
                stack[++top] = p;
                p = p->lchild;
            }
            else
            {
                p = stack[top--]; //栈顶元素出栈
                p = p->rchild; //访问右孩子
            }
        }
    }
}

如果能充分理解函数PreOrderTraverse_S_2(),中序遍历二叉树是不难实现的,它与前序遍历的区别在于:它需要先遍历左子树,再输出根结点。所以代码只需要更改一下语句printf("%c", p->data);的位置即可。代码如下:

void InOrderTraverse_S(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点,栈stack[]用来存储结点
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        p = BT;
        while (p || top >= 0)
        {
            if (p != NULL) //不急着输出结点数据,先遍历左孩子
            {
                stack[++top] = p;
                p = p->lchild;
            }
            else
            {
                p = stack[top--]; //栈顶元素出栈
                printf("%c", p->data);//输出该结点
                p = p->rchild; //访问右孩子
            }
        }
    }
}

后序遍历二叉树算法的基本思路和前序遍历基本一样,也是利用栈后进先出的特点,先将右孩子入栈,再将左孩子入栈。但实现起来稍微复杂点,主要原因是要在访问了左,右子树之后才能输出根结点,需要访问根结点两次,而且必须在第二次访问根结点时才能将根结点退栈,所以需要一个辅助标记,记录根结点是否已经被访问过。代码如下:
void PostOrderTraverse_S_1(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点,栈stack[]用来存储结点
    int tag[MAXSIZE] = {0}; //用来标志栈顶元素是否初次被访问
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        stack[++top] = BT; //根结点入栈
        tag[top] = 0; //初次访问该结点
        
        while (top >= 0)
        {
            p = stack[top]; //取栈顶元素,但先不出栈
            if ((p->rchild == NULL && p->lchild == NULL) || tag[top] == 1)//是叶子结点或者该结点已经被访问过,直接退栈,并输出其数据
            {
                printf("%c", p->data);//输出该结点
                top--;    //退栈
            }
            else //先访问其子孙
            {
                tag[top] = 1; //表明该结点已经被访问过了,下次回来的时候直接退栈即可
                if (p->rchild != NULL) //如果该结点有右孩子,将右孩子入栈
                {
                     stack[++top] = p->rchild;
                     tag[top] = 0; //初次访问该结点
                }
                if (p->lchild != NULL) //如果该结点有左孩子,将左孩子入栈,按照后入先出原则,左孩子先出栈
                {
                     stack[++top] = p->lchild;
                     tag[top] = 0; //初次访问该结点
                }
            }
        }
    }   
}

类比函数PreOrderTraverse_S_1()和函数PreOrderTraverse_S_2(),我们也可以通过分析后序遍历二叉树的特征,得到新的算法实现。这里也需要借助一个辅助标记,用来记录栈顶元素的右孩子是否被访问过。我们先访问左孩子,然后取出栈顶元素赋值给p,但先不出栈,若栈顶元素右子树尚未访问,访问其右孩子;若已经访问过,则输出该结点,退栈,并让p指向NULL,以避免重复访问左孩子。代码如下:
void PostOrderTraverse_S_2(BiTree BT)
{
    BiTree p, stack[MAXSIZE];//p表示当前结点,栈stack[]用来存储结点
    int tag[MAXSIZE] = {0}; //用来标志栈顶元素的右孩子是否被访问过,0表示未访问,1表示已访问
    int top = -1; //栈空
   
    if (BT != NULL)//先判断是否为空树
    {
        p = BT;
        while (p || top >= 0)
        {
            if (p != NULL) //不急着输出结点数据,先访问左孩子
            {
                stack[++top] = p;
                tag[top] = 0; //表明该结点的右子树尚未访问
                p = p->lchild;
            }
            else
            {
                p = stack[top]; //取栈顶元素,但先不出栈
                if (tag[top] == 0) //若右子树尚未访问,访问其右孩子
                {
                    tag[top] = 1; //表明该结点的右子树已接受访问
                    p = p->rchild;
                }
                else
                {
                    printf("%c", p->data);//输出该结点
                    top--;    //退栈,并让p指向NULL,以避免重复访问左孩子
                    p = NULL;
                }
            }
        }
    }
}

代码总是很多,讲解总是很短。一段小小学习总结,占用您不少宝贵时间,如果有什么疑问,就请留言吧,我一定知无不言,言无不尽。

[ 本帖最后由 巧若拙 于 2014-10-3 21:10 编辑 ]
2014-09-20 21:37







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026908 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved