精典二叉树非递归遍历的算法

主题：精典二叉树非递归遍历的算法

biy492732033 [专家分：0] 发布于 2006-05-14 21:07:00

遍历二叉树的非递归算法
编写的方法：根据树中结点的遍历规律及顺序直接写出其非递归算法。
先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{    // 基于方法一，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{    // 基于方法二，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

【算法】
void    InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】

T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef struct stackElement{
Bitree    data;
char        tag;
}stackElemType;
【算法】
void    PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1);        // 设置栈顶标记
T = GetTopPointer(S);    // 取栈顶保存的指针
T = T->rchild;
}else break;
}
}

[fly]回帖[/fly][email]null[/email]

本帖地址： http://bbs.pfan.cn/post/164802.html

回复列表（共13个回复）

11 楼

kurlez [专家分：200] 发布于 2006-06-04 00:13:00

可以这么理解：
所有的递归程序都是在OS上运行的。OS并不知道递归的概念——它就是看见函数便压栈，返回就弹出堆栈。你如果模拟了运行栈，那么就把递归转换成了堆栈的方式。

对于多次递归的函数，转换成堆栈的复杂程度是很难想象的。。。。

12 楼

goal00001111 [专家分：4030] 发布于 2006-06-04 09:45:00

我原来也做过几个,大家看看:
先序遍历
void preorder(btree *bt)
{
    btree *p, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
    int top=0;

    if(bt != NULL)//先判断是否为空树
    {
        stack[top] = bt; //根结点入栈
        while(top >= 0)
        {
            p = stack[top--]; //栈顶元素出栈
            printf("%d", p->data);//输出该结点
            if(p->rchild != NULL) //如果该结点有右孩子，将右孩子入栈
            {
                 stack[++top] = p->rchild;
            }
            if(p->lchild != NULL) //如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
            {
                 stack[++top] = p->lchild;
            }
        }
    }
}
或者：
void preorder(btree *bt)
{
    btree *p, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
    int top=0;

    if(bt != NULL)//先判断是否为空树
    {
            p = bt;
            while (p || top > 0)
            {
                  if (p)
                  {
                        stack[top++] = p;
                        printf("%c", p->data);//输出该结点
                        p = p->lchild;
                  }
                  else
                  {
                      p = stack[--top]; //栈顶元素出栈
                      p = p->rchild;
                  }
            }
      }
}
中序遍历
void inorder(btree *bt)
{
    btree *p=bt, *stack[MAX]; //p表示当前结点，栈stack[]用来存储结点
    int top=0;

    if(p != NULL) //先判断是否为空树
    {
        while(top >= 0)
        {
            if(p != NULL) //先处理结点的左孩子结点
            {
                stack[top++] = p; //当前结点入栈
                p = p->lchild; //寻找左孩子结点
            }
            else //找到最左边的孩子结点后
            {
                if(top == 0) //表示全部元素均已输出，结束输出
                    break;
                p = stack[--top];//栈顶元素出栈
                printf("%d", p->data); //输出该结点
                  p = p->rchild; //处理其右孩子结点
            }
        }
    }
}
或者：
void inorder(btree *bt)
{
    btree *p=bt, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
    int top=-1;

    do
    {
        while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
        {
            stack[++top] = p;
            p = p->lchild;
        }
        if(top >= 0) //所有左孩子处理完毕后
        {
            p = stack[top--];//栈顶元素出栈
            printf("%d", p->data); //输出该结点
            p = p->rchild; //处理其右孩子结点
        }
    } while((p != NULL)||(top >= 0));
}
后序遍历
void postorder(btree *bt)
{
    btree *p=bt, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
    int tag[MAX];
    int top=-1;

    do
    {
        while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
        {
            stack[++top] = p;
            tag[top] = 0;
            p = p->lchild;
        }
        if(top >= 0) //所有左孩子处理完毕后
        {
            if(!tag[top]) //如果当前结点的右孩子还没被访问
            {
                p = stack[top];//输出栈顶结点，但不退栈，因为要先输出其孩子结点
                p = p->rchild; //处理其右孩子结点
                tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
            }
            else //如果该结点的左右孩子都被访问过了
            {
                 printf("%d", stack[top--]->data); //栈顶元素出栈，输出该结点，此时结点p指向NULL
            }
        }
    } while((p != NULL)||(top >= 0));
}

13 楼

dgggy521 [专家分：0] 发布于 2006-07-29 11:36:00

咋都没注释呢.....可不是个好习惯,...看很费时间的!!!

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：精典二叉树非递归遍历的算法

回复列表（共13个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：精典二叉树非递归遍历的算法

回复列表 （共13个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共13个回复）