二叉树的先序、中序、后序遍历的方法

2021年9月10日 18点热度 0条评论 来源: Allen_Lin_

两大类:非递归和递归写法

一、递归方法(略)

二、(一般)非递归方法 [1]

1. 先序遍历(push 后/附近 打印)和中序遍历(pop 后/附近 打印)(略)

2. 后序遍历(三种思路)

思路.1. ) 双栈(先/中序的栈①+数据栈②; 其中栈②巧用了 左右子树遍历互调后的先序遍历 和 目标(后序)遍历恰好顺序相反);实现如下

[Easy Understanding]原文链接: https://blog.csdn.net/whzyb1991/article/details/44278723 

思路.2. ) 在树结点定义中添加一个成员:int visited 代表访问次数, 当访问次数达到Ⅱ后(已经遍历完了它之前的所有左右子树) && 在pop后/附近 打印;实现如下

...
...
...

typedef struct tree
{
    ElementType data;
     
    struct tree* lchild;
    struct tree* rchild;
    int visit;
}*Tree;
...
...
...
void posttraversal(Tree t)
{
    Tree T=t;
    T->visit=0;
    Stack s=createstack();
    while(T||!isempty(s))
    {
        while(T){
            if(T->visit==0){
                (T->visit)++;
                push(s,T);
            }
            T=T->lchild;
        }
        if(!isempty(s)){
            T=pop(s);
            if(T->visit==2)
                printf("%c",T->data);
            else{
                T->visit++;
                push(s,T);
                T=T->rchild;
            }
        }
    }
}

作者:Mrmooc239   作者发表时间:2017-3-23   ——摘自中国大学MOOC 数据结构(浙江大学)

思路.3. ) 控制在打印该结点值之前已经讲它之前的所有的结点已过压栈(通过两个条件:top(s).right != NULL && top(s).right != last_r; 其实也就一个条件C:top(s).right != NULL && top(s).right != last_r , 意思是 栈顶的右孩子/子树已经遍历过、输出过,无需将其压栈(C=false), 否则 top(s).right  为空或者不等于上次访问的右孩子/子树(C=true), 则说明遍历完了它之前的所有左右子树,即 下一步就是将其pop 并打印了);实现如下

//添加访问次数属性就破坏了树结点的结构了吧,将树全部先压入栈的方式又需要很大的栈,可以考虑在pop之前先看看当前的栈顶结点有没右儿子
//如果有右儿子的话,将右儿子压栈,对右子树进行处理
void last_search(bin_tree t)
{
    ptr_stack s = create_stack();
    bin_tree last_r = NULL;
    while (t || !is_empty(s))
    {
        while (t)
        {
            push(s, t);
            t = t->left;
        }
        if (!is_empty(s))
        {
            //思路,由于是后序,所以如果当前要弹出的结点的右儿子不为空,且其右儿子不是上一次弹出的
            //要对右儿子先进行处理
            if (top(s)->right && top(s)->right != last_r)
            {
                t = top(s)->right;
            }
            else
            {
                t = pop(s);
                last_r = t;
                printf("%d ", t->data);
                t = NULL;
            }
        }
    }
    free(s);
}

作者: mooc14904434... 作者发表时间:2017-4-1    ——摘自中国大学MOOC 数据结构(浙江大学)

(以上两段代码摘自中国大学MOOC 数据结构(浙江大学)  的 “讨论3.4 如何用堆栈实现后序遍历的非递归程序”)

注1:思路.2. 中的访问次数; 以课程中何钦铭老师讲到的:每个结点有三次"访问" 分别对应下图中的三个小图标

注2:下图中何钦铭老师讲到:三种遍历的原理/定义(不管是递归还是非递归)的路径都一样,对应下图中的一条线/路径;这也是递归方式和非递归中先、中序遍历这几种遍历的代码如此相似原因

三、(由层序遍历改编而来的)非递归方法 [2]

先序遍历:一开始入栈根节点。出栈并打印栈顶结点,然后先入栈该结点的非空右儿子再入栈非空左儿子,如此重复直到栈空。

原因:

0、若栈空时存在一个未打印结点a,因(树非空时)根结点一定会打印,那么根到a这条路径上必存在一个被打印的结点,其路径上的儿子不被打印,该儿子作为a的祖先显然是非空的。然而根据算法描述,一个结点被打印后其非空儿子会入栈,栈空前一定会出栈打印的。可见假设不成立,即栈空时所有结点都会被打印。

1、pop打印结点<--push结点<--(若结点不是整棵树的根节点)pop打印父结点。可见根结点比左右子树先打印。

2、打印右子树<--pop打印右子树的根结点<--右子树根结点在栈顶<--(若左子树非空)左子树结点全部pop打印(可由条目0推得)。可见左子树比右子树先打印。

 

中序遍历:一开始入栈根结点。若栈顶结点的左儿子非空且不是上次出栈的结点,则将该儿子入栈,否则先出栈并打印栈顶结点,若该结点有非空右儿子,则将该儿子入栈,如此反复直到栈空。

 

后序遍历:一开始入栈根节点。若栈顶结点有非空且未出过栈的儿子,则按照先右后左的顺序将其入栈(栈顶结点不出栈),否则出栈并打印,如此反复直到栈空。

作者:摸鱼小能手  作者发表时间:2017-3-20   ——摘自中国大学MOOC 数据结构(浙江大学)

 

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