[二叉树](3)遍历二叉树和线索二叉树

在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部的结点逐一进行某种操作,这就提出了一个遍历二叉树(traversing Binary Tree)的问题

那如何按某条搜索路径巡访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。

”访问“的含义很广,可以是对结点作各种处理,如输出结点的信息等,遍历对线性表来说,是一个容易解决的问题,而对二叉树则不然,由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使得二叉树上的结点能排列在一个线性队列上,从而便于遍历

回顾二叉树的递归定义可知,二叉树是由3个基本单元组成:根结点,左子树和右子树,因此,若能依次遍历这三部分,便是遍历了整个二叉树,假如以上L、D、R分别表示遍历左子树、访问根结点和遍历右子树,则可有DLR、LDR、LRD、DRL、RDL、RLD这六种遍历二叉树的方案

若限定先左后右,则只有DLR(根左右)、LDR(左根右)、LRD(左右根)这三种情况

分别称之为:先(根)序遍历、中(根)序遍历、后(根)序遍历,可得下列遍历二叉树的递归算法定义:

先序遍历二叉树的操作定义为:

  • 若二叉树为空,则空操作,否则:

    1. 访问根结点
    2. 先序遍历左子树
    3. 先序遍历右子树

中序遍历二叉树的操作定义为:

  • 若二叉树为空,则空操作,否则:

    1. 中序遍历左子树
    2. 访问根结点
    3. 中序遍历右子树

后序遍历二叉树的操作定义为:

  • 若二叉树为空,则空操作,否则:

    1. 后序遍历左子树
    2. 后序遍历右子树
    3. 访问根结点

代码如下所示:

Bool Visit(BinTree* T)
{
    printf("%d", T->data);
    return TRUE;
}

//Lanqiao_2013_9

Status PreOrderTraversal(BinTree* T)
{
    if (T)
    {
        Visit(T);//访问根
        PreOrderTraversal(T->lchild);
        PreOrderTraversal(T->rchild);
        return OK;
    }
    return ERROR;
}

Status InOrderTraversal(BinTree* T)
{
    if (T)
    {
        InOrderTraversal(T->lchild);
        Visit(T);//访问根
        InOrderTraversal(T->rchild);
        return OK;
    }
    return ERROR;
}

Status PostOrderTraversal(BinTree* T)
{
    if (T)
    {
        PostOrderTraversal(T->lchild);
        PostOrderTraversal(T->rchild);
        Visit(T);//访问根
        return OK;
    }
    return ERROR;
}

我们通过以下笔记来详细记录这三种访问二叉树的操作过程,首先如图所示的二叉树中序遍历如下表达式:

a+b*(c-d)-e/f

img

若按先序遍历此二叉树,按访问结点的先后次序将结点排列起来,可得到二叉树的先序序列为:

-+a*b-cd/ef

类似的,中序遍历此二叉树,可得到此二叉树的中序序列为:

a+b*c-d-e/f

后序遍历此二叉树,可得此二叉树的后序序列为:

abcd-*+ef/-

从表达式来看,以上三个序列恰好为表达式的前缀表达式,中缀表达式,后缀表达式,我们可以联想到之前栈的应用,正好记录过,当时还折磨了我好久,来复习下:

  • 以二叉树表示表达式的递归定义如下,若二叉树为数或简单变量,则相应二叉树中仅有一个根结点,其数据与存放该表达式的信息
  • 若表达式=(第一操作数)(运算符)(第二操作数),则相应的二叉树中以左子树表示第一操作数,右子树表示第二操作数,则结点的数据域存放运算符(若为一元算符,则左子树为空),操作数本身又为表达式

从上述二叉树遍历的定义可知,3种遍历算法之不同处仅在于访问根结点和遍历左、右子树的先后关系,如果在递归算法中暂且抹去和递归无关的Visit语句,则3个遍历算法完全相同

由此,从递归执行过程的角度来看先序、中序、后序遍历也是完全相同的,下图用虚线表示了3种遍历算法的递归执行过程:其中

  • 向下的箭头表示更深一层的递归调用
  • 向上的箭头表示从递归调用退出返回
  • 虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历过程中访问结点时输出的信息

img

例如:有序中序遍历中访问结点是在遍历左子树之后,遍历右子树之前进行,则带圆形的字符标在向左递归返回和向右递归调用之间,由此,只要沿虚线从1出发到2结束,将沿途所见的三角形(或圆形、或方形)内的字符几下,便得遍历二叉树的先序(或中序、或后序)序列。

分别可以得到上图左边树中的前缀表达式(-abc)、中缀表达式(ab-c)、和后缀表示(ab*c-)

仿照递归算法执行的过程中递归工作栈的状态变化可直接写出相应的非递归算法,例如,从中序遍历递归算法执行过程中,递归工作栈的状态可见:

  1. 工作记录中包含两项

    1. 其一是递归调用的语句编号
    2. 其二是指向根结点的指针
    3. 则当栈顶记录的指针非空时,应遍历左子树,即指向左子树根的指针进栈
  2. 若栈顶记录中的指针值为空时,则应退至上一层

    1. 若是从左子树返回,则应访问当前层即栈顶记录中指针所指的根结点
    2. 若是从右子树返回,则表明当前层的遍历结束,应继续退栈
  3. 从另一角度看,这意味着遍历右子树时不再需要保存当前层的根指针,可直接修改栈顶记录中的指针即可

非递归中序遍历

由上述可得以下为中序的非递归算法:

Status InOrderTraversal_Nr(BinTree T)
{
    BinTreeStack S;
    InitStack(&S);
    BinTree p = T;
    while (p || S.top > S.base)
    {
        while (p)
        {
            Push(&S, p); p = p->lchild;
        }
        Pop(&S, &p);
        Visit(p);
        p = p->rchild;
    }
    return OK;
}

我们来简单看看这段代码和中序遍历:左根右

在代码中,先将根结点压入栈内,然后不断迭代左结点当当前子树左结点为空的时候,弹出根结点访问,然后转为右结点,在右结点为空时,则继续弹出,进行下一棵子树的判断,这是否与我们的递归如出一辙?

我们利用一棵简单的树来模拟上述代码的过程:

<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/InorderBinTree.mp4";></video>

非递归先序遍历

通过上述演示,我们可以推出其先序遍历非递归算法,代码如下所示:

Status InOrderTraversal_Nr(BinTree T)
{
    BinTreeStack S;
    InitStack(&S);
    BinTree p = T;
    while (p || S.top > S.base)
    {
        while (p)
        {
            Visit(p); 
            Push(&S, p);
            p = p->lchild;
        }
        Pop(&S, &p);
        p = p->rchild;
    }
    return OK;
}

我们可以看到,先序与中序不同之处只在于对结点进行访问的位置不同,从先序的访问顺序:根、左、右。以及递归算法我们就很好理解它

非递归后序遍历

当然后序有点不同,但是还是同样的思路,一个栈是实现不了后序的,后序遍历的非递归算法是三种顺序中最复杂的。

原因在于,后序遍历是先访问左、右子树,再访问根节点,而在非递归算法中,利用栈回退到时,并不知道是从左子树回退到根节点,还是从右子树回退到根节点

如果从左子树回退到根节点,此时就应该去访问右子树,而如果从右子树回退到根节点,此时就应该访问根节点。

我们可以换一种思路,后序顺序为:左右根,而栈的特点是先进先出,可以实现一个线性表的逆序

我们是否可以利用栈的特点对 左、右、根 逆序成 根、右、左 存入栈中然后逆序输出呢?

答案必然是可以的,以上面那棵树为例,它的后序遍历为:ab+c-,正好对应栈中的:

img

但是问题又来了,我们在一个栈中,若需要访问左右孩子必须将该结点取出来去访问,最后得到的结果必定是栈空和p为空

那么我们则可以利用一个辅助栈,进行存储每一次访问的根结点即可。

代码如下所示:

Status PostOrderTraversal_Nr(BinTree T)
{
    BinTreeStack S,S2;
    InitStack(&S);
    InitStack(&S2);

    BinTree p = T;
    while (p || S.top > S.base)
    {
        while (p)
        {
            //Visit(p); 
            Push(&S2, p);//压入辅助栈
            Push(&S, p);
            p = p->rchild;//访问右子树
        }
        Pop(&S, &p);
        p = p->lchild;//访问左结点
    }
    S2.top--;
    while (S2.top >= S2.base)
    {
        printf("%c", (*S2.top)->data);
        S2.top--;
    }
    return OK;

网上很多不同版本的二叉树遍历非递归方法,个人觉得以上三种最好,也能统一起来一个相似的模板,对于栈和递归之间的联系也是最透彻的,上述三种算法出自下列视频中的UP主,感谢!

非递归层次遍历

当然我们还可以通过层次遍历来访问结点,以上先中后都是向一条路径走到底,然后回溯再换条路线,这就是深度优先搜索,而层次不同,层次是将所有的路径全部一起访问,这是广度优先搜索

这两种搜索算法在图的遍历中会做详细记录,当然,这两种算法都是常用算法,特别是在递归回溯中,我们可以利用DFS的思想将递归过程看作树形结构,在我记录的题解中有提及过

既然知道了是BFS的做法,那么惯用,我们都需要使用一个辅助队列来实现,将所有结点依次存入队列中,再取出来,进行访问,顺序是从左到右,从上到下。

我们还是用一个简单的树来了解:

<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/TreeLevel.mp4";></video>

代码如下所示:

Status LevelBinaryTreeTraversal(BinTree T)
{
    Queue Q;
    InitQueue(&Q);
    BinTree p = T;
    if (p)
    {
        PutTail(&Q, p);
        while (Q.front != Q.rear)
        {
            GetHead(&Q, &p);
            Visit(p);
            if (p->lchild) PutTail(&Q, p->lchild);
            if (p->rchild) PutTail(&Q, p->rchild);
        }
        return OK;
    }
    return ERROR;
}

二叉树基于遍历的各项操作

可通过二叉树的递归遍历来写出基于二叉树上的各种操作。

创建二叉树

遍历是对二叉树各种操作的基础,可以在遍历的过程中对结点进行各种操作,如:对于一棵已知树求结点的双亲,求结点的孩子结点,判定结点所在层次等,反之,也可以在遍历过程中生成结点,建立二叉树的存储结构。

下列是按先序创建二叉树的算法,我们约定,‘#’字符代表NULL,则我们对应先序遍历的规则给定的字符串:ABC##D##EF##G## 图示如下:

img

算法如下:

Status PreCreateBinAryTree(BinaryTree** T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
    {
        (*T) = NULL;
        return OK;
    }
    else
    {
        (*T) = (BinTree)malloc(sizeof(BinaryTree));
        (*T)->data = ch;
        PreCreateBinAryTree(&(*T)->lchild);
        PreCreateBinAryTree(&(*T)->rchild);
    }
    return OK;
}

对应的,我们可以写出其中序和后序创建的算法,只需要改变一下对结点的操作即可,我们可以知道,对应书写表达串只能有:除了“#”为空外,其余都为结点

我们只需要改变对数据域的赋值即可,若是中序创建,我们则将赋值放到创建完左子树以后,在逐步回来的时候对根进行赋值,若是后序创建,我们则将左右子树全部申请好空间后,逐步回来对结点进行赋值

在后序创建二叉树的思路中,我们又可以得知,创建是按:左、右、根,的顺序去申请的空间,即先将左子树全部申请完,直到字符为#的时候,再去申请右子树,直到遇到两个##则代表构成一个叶子结点,最后再返回到根进行赋值即可。

复制二叉树

与创建最为相似的就是复制操作了,从树T复制到树R,我们可走过T的每一个结点对R进行创建,与广义表的复制算法也极为相似,甚至更为简易,算法如下:

Status CopyBinTree(BinTree* R, BinTree* T)
{
    if ((*T) == NULL)
    {
        *R = NULL;
    }
    else
    {
        if (!((*R) = (BinTree)malloc(sizeof(BinaryTree)))) return ERROR;
        (*R)->data = (*T)->data;
        (*R)->lchild = NULL; (*R)->rchild = NULL;
        CopyBinTree(&(*R)->lchild, &(*T)->lchild);
        CopyBinTree(&(*R)->rchild, &(*T)->rchild);

    }
    return OK;
}

求结点总数

在二叉树中求结点总数我们可以把问题归纳为:左子树结点树+右子树结点树+1(根结点为1个),然后利用递归特性完成算法。

int NodeTotal(BinTree T)
{
    if (!T) return 0;
    return NodeTotal(T->lchild) + NodeTotal(T->rchild) + 1;
}

求树深度

树的深度就是左右子树中最大的子树个数,我们依旧可通过递归算法来求解,先把问题分解为求左子树深度,求右子树深度,然后更新他们的最大值

int DepthBinTree(BinTree T)
{
    if (!T) return 0;
    else
    {
        int m = DepthBinTree(T->lchild) + 1;
        int n = DepthBinTree(T->rchild) + 1;
        if (m > n) return m;
        else return n;
    }
}

求叶子结点个数

同样,求叶子结点个数也可利用递归解决,我们可以知道,只有当左右两孩子都为空的时候,才是叶子结点,则我们只需在递归过程中,记录下所有左右子树都为空的结点数量即可。

int LeafTotal(BinTree T)
{
    if (!T->lchild && !T->rchild)
        return 1;
    else
         return LeafTotal(T->lchild) + LeafTotal(T->rchild);
}

显然,遍历二叉树的算法中的基本操作是访问结点,则不论哪一种次序进行遍历,对含n个结点的二叉树,其时间复杂度均为O(n),所需的辅助空间为遍历过程中栈的最大容量,即树的深度,最坏情况下为n,则空间复杂度也为O(n)

遍历时也可采用二叉树其他的存储结构,如带标志域的三叉链表,此时一存储结构中已有遍历所需足够信息,则遍历过程中不需另设栈,也可和遍历广义表的算法相类似,采用带标志域的二叉链表作存储结构。

并在遍历过程中利用指针域暂存遍历路径,也可省略栈的空间,但这样做将在时间上有很大损失。

线索二叉树

从上述笔记可知:遍历二叉树是以一定规则将二叉树中结点排列称一个线性序列,得到二叉树中结点的先序序列、中序序列或者后序序列。

这实质上是对一个非线性结构进行线性化操作,使每个结点(除第一个和最后一个外)在这些线性序列中有且仅有一个前驱和后继。

例如在中序序列中:a+b*c-d-e/f

中结点(数据域)为‘c’的结点的前驱是:‘*’后继是‘-’

但是,当以二叉链表作为存储结构时,只能找到结点的左、右孩子信息,而不能直接得到结点在任一序列中的前驱和后继信息,这种信息只有在遍历的动态过程中才能得到

如何保存这种在遍历过程中得到的信息呢?一个最简单的办法是在每个结点上增加两个指针域fwd和bkwd,分别指示结点在依任一次序遍历的动态过程中得到的前驱和后继的信息,显然,这样做使得结构的存储密度大大降低

另一方面,在有n个结点的二叉链表中必定存在 n+1 个空链域,由此设想能否利用这些空链域来存放结点的前驱和后继的信息

试做如下规定:若结点有左子树,则让其lchild域指示其左孩子,若结点没有左孩子,则让其lchild域指示其前驱

若结点有右孩子,则让其rchild域指示其右孩子,若结点没有右孩子,则让其rchild域指示其后继。

为了避免混淆,尚且需要改变结点结构,增加两个标志域

img

其中:

img

以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱和后继的指针,叫做线索,加上线索的二叉树,称之为线索二叉树(Threaded Binary Tree)

如下图所示的中序线索二叉树,与其对应的是中序线索链表:

img中序线索二叉树

img中序线索链表

其中实线为指针(指向左右子树),虚线为线索(指示前驱和后继),对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

在线索树上进行遍历只要先找到序列中的第一个结点,然后依次找到结点的后继直至其后继为空为止

如何在线索树中找结点的后继?以上图中的中序线索二叉树为例来看,树中所有的叶子结点的右链是线索,则右链域直接指示了结点的后继,如结点b的后继为结点*

树中所有的非终端结点的右链均为指针,则无法由此得到后继的信息,然而,根据中序遍历的规律可知:

  • 结点的后继

应是遍历其右子树时访问的第一个结点

,即右子树中最左下的结点

    • 例如在寻找结点*的后继时,首先沿右指针找到其右子树的根节点“-”
    • 然后顺其左指针往下直至左标志为1的结点,即为结点*的后继
    • 在图中为结点c
    • 反之,在中序线索树中找结点前驱的规律是:若其左标志域为“1”,则左链为线索,指示其前驱,否则遍历左子树时最后访问的一个结点(左子树中最右下的结点)为其前驱。

    在后序线索树中找到结点后继较为复杂些,可分3种情况:

    1. 若结点x是二叉树的根,则其后继为空
    2. 若结点x是其双亲的右孩子

      1. 或是其双亲的左孩子,且其双亲有右子树,则其后继为双亲的右子树上按后序遍历列出的第一个结点(如下图所示)
    3. 若结点x是其双亲的左孩子,且其双亲有右子树,则其后继为双亲的右子树上按后序遍历列出的第一个结点

    img

    如上图所示为后序后继线索二叉树,结点B的后继为结点C,结点C的后继为结点D,结点F的后继为结点G,而结点D的后继为结点E

    可见,在后序线索化树上找后继时需知道结点的双亲,即需带标志域的三叉链表作存储结构。

    可见,在中序线索二叉树上遍历二叉树,虽则时间复杂度亦为O(n),但常数因子要比上节讨论的算法小,且不需要设栈,因此,若在某程序种所用二叉树需经常遍历或查找结点在遍历所得线性序列种的前驱和后继,则应采用线索链表作存储结构

    二叉树线索存储链表如下所示:

    typedef enum PointerTag { Link, Thread };
    typedef struct BiThrNode {
        TElemType data;
        struct BiThrNode* lchild;
        struct BiThrNode* rchild;//左右孩子指针
        PointerTag LTag, RTag;//左右标志
    }BiThrNode, * BiThrTree;

    为方便起见,仿照线性表的存储结构,在二叉树的线索链表上也添加一个头结点,并令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点

    反之,令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点

    这好比为二叉树建立了一个双向线索链表,既可从第一个结点其顺后序进行遍历,也可从最后一个结点起顺前驱进行遍历,下述算法正是以双向线索链表为存储结构时对二叉树进行遍历的算法:

    Status InOrderTraverse_Thr(BiThrTree T)
    //T指向头结点,头结点的左链lchild指向根结点,可参加线索化算法
    //中序遍历二叉线索树T的非递归算法,访问每个数据元素
    {
        BiThrTree p = T->lchild;//p访问根结点
        while (p != T)//p不等于T,未访问到最后一个结点
        {
            while (p->LTag == Link) p = p->lchild;//走到左子树的末端
            printf("%d", p->data);//访问左子树为空的根结点,为中序序列中的第一个结点
            while (p->RTag == Thread && p->rchild != T)//访问其后继线索
            {
                p = p->rchild;//不断访问线索
                printf("%d", p->data);
            }
            p = p->rchild;//结束外层循环
        }
        return OK;
    }

    线索化二叉树

    那么,又如何进行二叉树的线索化呢?由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只有在遍历时才能得到

    因此线索化的过程即为在遍历的过程中修改空指针的过程

    为了记下遍历过程中访问结点的先后关系,维护一个全局指针类型遍历pre始终指向刚刚访问过的结点,若指针p指向当前访问的结点,则pre指向它的前驱

    由此可得中序遍历建立中序线索化链表如下所示:

    BiThrTree pre;
    void InThreading(BiThrTree p)
    {
        if (p)
        {
            InThreading(p->lchild);//左子树线索化
            if (!p->lchild) {//当前指针连接前驱
                p->LTag = Thread;
                p->lchild = pre;
            }
            if (pre->rchild) {//前驱指针连接当前结点链接后继
                pre->RTag = Thread;
                pre->rchild = p;
            }
            pre = p;//更新当前结点为前驱结点,搜寻后继
            InThreading(p->rchild);
        }
    }
    Status InOrderThreading(BiThrTree* Thrt, BiThrTree T)
    //中序遍历二叉树T,并将其中序线索化,Thrt指向头结点
    {
        if (!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(ERROR);
        (*Thrt)->LTag = Link;
        (*Thrt)->RTag = Thread;//建立头结点
        (*Thrt)->rchild = (*Thrt);//右指针回指
    
        if (!T)(*Thrt)->lchild = (*Thrt);//若二叉树空,则左指针回指
        else
        {
            (*Thrt)->lchild = T;
            pre = *Thrt;
            InThreading(T);//中序遍历进行中序线索化
            pre->rchild = (*Thrt);
            pre->RTag = Thread;
            (*Thrt)->rchild = pre;
        }
        return OK;
    }

    下面给出完整的遍历(递归与非递归)、创建、操作、线索化二叉树的测试代码。

    关于先、中、后序线索化二叉树,我研究了很久才明白,下面放入大佬博文的传送们:

    点击进入详解

    代码如下,可直接测试。

    ThreadBinTree’s-Pre-And-In_Post下载

    这里对后序遍历做一个笔记,大佬博客看不懂的可以看如下笔记:

    img

    我们以如下二叉树做一个示例

    img

    本文链接:

    https://nullcode.fun/42.html
    1 + 6 =
    快来做第一个评论的人吧~