学科分类
目录
数据结构

二叉树的非递归遍历

树是递归定义的,因此用递归的算法思想来解决树的遍历等问题比较容易理解,求解代码也比较简洁。但除了递归,树还可以通过非递归遍历。本节以中序遍历为例,讲解二叉树的非递归遍历。,因为在实际开发应用中,中序遍历较之前序遍历与后序遍历更为常用,我们以中序遍历为例来进行讲解。

中序非递归遍历,依然是先访问左子树,然后访问根结点,最后访问右子树。以图1中的二叉树为例,对此树进行非递归中序遍历的分析如下。

图1 二叉树

此二叉树的非递归遍历同样将二叉树视为三个部分:左子树、根结点、右子树。

第一部分:根结点为A,查看A是否有左子树,有,将A暂存,访问其左子树;

第二部分:A的左子树是以B为根结点的二叉树;

(1)查看B是否有左子树,无,则访问B,输出B;

(2)查看B是否有右子树,有,则访问B的右子树;

(3)B的右子树是以F为根结点的二叉树;

(4)查看F是否有左子树,有,则将F暂存,访问F的左子树;

(5)F的左子树是以L为根结点的二叉树;

(6)查看L是否有左子树,无,则访问L,输出L;

(7)查看L是否有右子树,无,则以L为根结点的二叉树访问完毕;

(8)退回到F结点,访问F结点,输出F;

(9)查看F是否有右子树,无,则以F为根结点的二叉树访问完毕;

(10)B的右子树访问完毕,以B为根结点的二叉树访问完毕,A的左子树访问完毕;

A的左子树访问完毕,则退回到A结点处,访问A,输出A;随后检查A是否有右子树,有,则访问其右子树;

第三部分:A的右子树是以D为根结点的二叉树;

(1)查看D是否有左子树,有,则将D暂存,访问其左子树;

(2)D的左子树是以I为根结点的二叉树;

(3)查看I是否有左子树,无,则访问I,输出I;

(4)查看I是否有右子树,无,则以I为根结点的二叉树访问完毕;

(5)D的左子树访问完毕,则退回到D结点处,访问D,输出D;

(6)查看D是否有右子树,无,则以D为根结点的二叉树访问完毕;

(7)A的右子树访问完毕;

在二叉树的非递归遍历过程中,需要先找到遍历的起点,如先找到根结点A的左子树,如果A的左子树还有左子树,则会继续往下寻找,直到找到没有左子树的结点,以这个结点为起始结点开始访问。

在这个过程中,读者可能会发现,先经过的结点后访问,除非此结点没有左子树,例如结点A,先经过了结点A,但只是把A暂存起来,去访问其左子树,当把A的左子树访问完毕后才回到A结点来访问。而对于后访问到的结点,例如B结点,它也是遍历这棵树的起点,在A结点之后经过却是先被访问。对于暂时不输出的结点,将它们暂存起来,等访问到时再取出。基于上述遍历规律,我们很容易就能想到这与栈处理数据的特点相同,因此可以用栈来解决非递归中序遍历二叉树的问题。

为了让读者更好地理解其遍历过程,以图1为例,结合图解来分析树中各结点的访问及入栈出栈过程。

(1)首先访问根结点A,A有左子树,则A结点入栈,如图2所示。

图2 A结点入栈

(2)A结点入栈后,指针下移,访问A结点的左子树,其左子树是以B为根结点的二叉树。访问结点B,判断B是否有左子树。B没有左子树,输出B,如图3所示。

图3 输出结点B

(3)访问B结点后,判断B是否有右子树,有,使指针下移,指向结点F,访问F结点,判断F结点是否有左子树,有,则F结点入栈,如图4所示。

图4 F结点入栈

(4)F结点入栈后,指针下移,遍历其左子树;其左子树是以L为根结点的二叉树,访问L结点,L没有左子树,则访问L,将其输出,如图5所示。

图5 输出L结点

(5)输出L结点后,要访问其右子树,L没有右子树,则表示L结点访问完毕;根据栈顶指针回退到F结点,访问F,将其输出。如图6所示。

图6 输出F结点

(6)访问完栈顶元素结点后,要访问其右子树,F没有右子树,则根据栈顶指针指示再次回退,结果回退到结点A,访问A结点,将其输出。如图7所示。

图7 输出A结点

(7)访问完栈顶元素结点A之后,访问其右子树,即遍历D结点,因为D结点有左子树, D结点入栈,如图8所示。

图8 D结点入栈

(8)D结点入栈后,访问其左子树,左子树是以I为根结点的二叉树,而I没有左子树,则访问I结点,将其输出,如图9所示。

图9 输出结点I

(9)结点I也没有右子树,则根据栈顶指示,回退到结点D,访问D结点,将其输出,如图10所示。

图10 输出结点D

(10)访问D结点后,访问其右子树,D没有右子树,且此时栈已为空,表示树已经遍历完毕。那么图10中“BLFAID”就是其遍历输出结果。

经过上面的讲解及图解,想必读者已经理解了非递归中序遍历的过程,那么在实现相应算法时就比较容易了。其算法代码在接下来的案例中实现,为了让案例代码更完整,这里就不再单独给出算法代码。在遍历过程中用到的栈,在栈中已经学习,此处将前面章节的链式栈稍加修改,用于存储二叉树中的结点,具体如例1所示。

例1

linkstack.h //头文件

 1    #ifndef _LINKSTACK_H_
 2    #define _LINKSTACK_H_
 3    
 4    //二叉树的结点结构
 5    typedef struct BitNode
 6    {
 7        char data;         //数据类型为char
 8        struct BitNode* lchild, *rchild;
 9    }BitNode;
 10    
 11    //栈的结点结构
 12    typedef struct Node * pNode;
 13    typedef struct Stack * LinkStack;
 14    struct Node //数据结点
 15    {
 16        BitNode* data;          //数据,BitNode结构体类型的指针
 17        pNode next;             //指针
 18    };
 19    
 20    struct Stack               //此结构记录栈的大小和栈顶元素指针
 21    {
 22        pNode top;             //栈顶元素指针
 23        int size;             //栈大小
 24    };
 25    
 26    LinkStack Create(); //创建栈
 27    int IsEmpty(LinkStack lstack); //判断栈是否为空
 28    int Push(LinkStack lstack, BitNode* val); //元素入栈
 29    pNode getTop(LinkStack lstack); //获取栈顶元素
 30    pNode Pop(LinkStack lstack); //弹出栈顶元素
 31    
 32    #endif

linkstack.c //算法实现

 33    #include "linkstack.h"
 34    #include <stdio.h>
 35    #include <stdlib.h>
 36    
 37    LinkStack Create() //创建栈
 38    {
 39        LinkStack lstack = (LinkStack)malloc(sizeof(struct Stack));
 40        if (lstack != NULL)
 41        {
 42            lstack->top = NULL;
 43            lstack->size = 0;
 44        }
 45        return lstack;
 46    }
 47    
 48    int IsEmpty(LinkStack lstack) //判断栈是否为空
 49    {
 50        if (lstack->top == NULL || lstack->size == 0)
 51            return 1;
 52        return 0;
 53    }
 54    
 55    int Push(LinkStack lstack, BitNode* val)
 56    {
 57        pNode node = (pNode)malloc(sizeof(struct Node)); //为元素val分配结点
 58        if (node != NULL)
 59        {
 60            node->data = val;
 61            node->next = getTop(lstack); //新元素结点指向下一个结点,链式实现
 62            lstack->top = node;           //top指向新结点
 63            lstack->size++;
 64        }
 65        return 1;
 66    }
 67    
 68    pNode getTop(LinkStack lstack) //获取栈顶元素
 69    {
 70        if (lstack->size != 0)
 71            return lstack->top;
 72        return NULL;
 73    }
 74    
 75    pNode Pop(LinkStack lstack) //弹出栈顶元素
 76    {
 77        if (IsEmpty(lstack))
 78        {
 79            return NULL;
 80        }
 81        pNode node = lstack->top;             //node指向栈顶元素
 82        lstack->top = lstack->top->next;     //top指向下一个元素
 83        lstack->size--;
 84        return node;
 85    }

main.c //测试文件

 86    #include <stdio.h>
 87    #include <stdlib.h>
 88    #include "linkstack.h"
 89    
 90    //寻找遍历起始结点
 91    BitNode*  GoFarLeft(BitNode* T, LinkStack ls)
 92    {
 93        if (T == NULL)
 94            return NULL;
 95        while (T->lchild != NULL) //左子树不为空,就一直往下寻找
 96        {
 97            Push(ls,T);
 98            T = T->lchild;
 99        }
 100        return T;
 101    }
 102    
 103    //非递归中序遍历函数
 104    void MyOrder(BitNode* T)
 105    {
 106        LinkStack ls = Create();               //创建栈
 107        BitNode* t = GoFarLeft(T, ls);          //寻找遍历起始结点
 108        while (t != NULL)
 109        {
 110            printf("%c", t->data);                 //打印起始结点的值
 111            //若结点有右子树,则访问其右子树
 112            if (t->rchild != NULL)
 113                t = GoFarLeft(t->rchild, ls); //寻找右子树中的起始结点
 114            else if (!IsEmpty(ls)) //如果栈不为空
 115            {
 116                t = getTop(ls)->data;             //回退到栈顶元素结点
 117                Pop(ls);                         //栈顶元素弹出
 118            }
 119            else
 120                t = NULL;
 121        }
 122    }
 123    int main()
 124    {
 125        BitNode nodeA, nodeB, nodeD, nodeF, nodeI, nodeL; //创建6个结点
 126        //将结点都初始,这样可以保证没有孩子的结点相应指针批向空
 127        memset(&nodeA, 0, sizeof(BitNode));
 128        memset(&nodeB, 0, sizeof(BitNode));
 129        memset(&nodeD, 0, sizeof(BitNode));
 130        memset(&nodeF, 0, sizeof(BitNode));
 131        memset(&nodeI, 0, sizeof(BitNode));
 132        memset(&nodeL, 0, sizeof(BitNode));
 133        //给结点赋值
 134        nodeA.data = 'A';
 135        nodeB.data = 'B';
 136        nodeD.data = 'D';
 137        nodeF.data = 'F';
 138        nodeI.data = 'I';
 139        nodeL.data = 'L';
 140        //存储结点之间的逻辑关系
 141        nodeA.lchild = &nodeB; //A结点左孩子是B
 142        nodeA.rchild = &nodeD; //A结点的右孩子是D
 143        nodeB.rchild = &nodeF; //B结点的右孩子是F
 144        nodeF.lchild = &nodeL; //F结点的左孩子是L
 145        nodeD.lchild = &nodeI; //D结点的左孩子是I
 146    
 147        printf("二叉树构建成功!\n");
 148    
 149        printf("非递归中序遍历:");
 150        MyOrder(&nodeA);
 151    
 152        printf("\n");
 153        system("pause");
 154        return 0;
 155    }

运行结果如图11所示。

图11 例1运行结果

例1的头文件linkstack.h中定义了二叉树结点结构与栈的存储结点结构。注意:在栈的存储结点结构中,数据域的数据类型为BitNode*类型,即存储的是二叉树结点指针。在树的遍历过程中只用到栈的创建、入栈、获取栈顶元素、出栈、判断栈空的操作,因此只保留了Create()、Push()、getTop()、Pop()与IsEmpty()五个函数。

在linkstack.c文件中,函数的实现与第三章中例3-2中的实现相同,基本没有作任何改动,只是Push()函数的第二个参数变了BitNode*类型。

在main.c测试文件中,代码104-122行实现了非递归中序遍历算法MyOrder();

代码106行调用Create()函数创建了一个栈;

107行代码调用GoFarLeft()函数寻找遍历起始结点,关于GoFarLeft()函数见代码91-101行,函数实现较简单,不再细说;

代码108-121行是该算法的核心部分:如果起始结点不为空,则打印起始结点值;然后判断结点右子树是否为空,不为空则在右子树中寻找起始结点;如果右子树为空,则判断栈是否为空,如果栈不为空,则根据栈顶指示回退到栈顶元素结点,然后弹出栈顶元素;如果结点右子树为空且栈也为空,则表示遍历完成,令t=NULL即可。

本案例中,大量代码在其他案例中都有出现,但为了使读者能够完整的接触到非递归遍历过程的代码,本案例将树的构建、栈的实现等又重新给出,读者在学习时要认真练习并理解。

点击此处
隐藏目录