C语言实现二叉树遍历的递归和非递归算法

偏执的太偏执、 2022-02-23 05:34 235阅读 0赞

本文主要介绍**二叉树的各种遍历方法**。

## 二叉树的遍历 ##

所谓二叉树的遍历，是指**按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次**。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对**根结点 N N N**、**左子树 L L L** 和 **右子树 R R R** 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有：

1.  前序遍历：（N L R）
2.  中序遍历：（L N R）
3.  后序遍历：（L R L）

这里的**序**指的是**根结点何时被访问**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70]

**在介绍3种遍历算法前，我们先给出二叉树的存储结构和建立二叉树的代码**：

**所有代码均来自**[c(c++)实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序）][c_c]

1.  二叉树的存储结构（二叉链表）

//二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
    typedef  struct BiTNode
    {
        
        ElemType data;
        struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;

1.  建立二叉树（**此处以前序遍历的方式建立**）

//二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树
    void CreateBiTree(BiTree *T)
    {
        
        ElemType ch;
        cin >> ch;
        if (ch == '#')
            *T = NULL;  //保证是叶结点
        else
        {
        
            *T = (BiTree)malloc(sizeof(BiTNode));
            //if (!*T)
                //exit(OVERFLOW); //内存分配失败则退出。
            (*T)->data = ch;//生成结点
            CreateBiTree(&(*T)->lchild);//构造左子树
            CreateBiTree(&(*T)->rchild);//构造右子树    
        }
    }

**下面给出2种算法，分别实现三种遍历方式**

## 递归算法 ##

### 程序实现 ###

/递归方式前序遍历二叉树
    void PreOrderTraverse(BiTree T, int level)
    {
        
        if (T == NULL)
            return;
    
    /*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
        //operation1(T->data);
        operation2(T->data, level); //输出了层数
    
        PreOrderTraverse(T->lchild, level + 1);
        PreOrderTraverse(T->rchild, level + 1);
    }
    
    //递归方式中序遍历二叉树
    
    void InOrderTraverse(BiTree T,int level)
    {
        
    	if(T==NULL)
    		return;
    	InOrderTraverse(T->lchild,level+1);
    
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    
    	InOrderTraverse(T->rchild,level+1);
    }
    
    //递归方式后序遍历二叉树
    
    void PostOrderTraverse(BiTree T,int level)
    {
        
    	if(T==NULL)
    		return;
    	PostOrderTraverse(T->lchild,level+1);
    	PostOrderTraverse(T->rchild,level+1);
    
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    }

**下面是完整的实现代码**

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    
    typedef char ElemType;
    
    //二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
    
    typedef  struct BiTNode
    {
        
        ElemType data;
        struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    //二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树
    void CreateBiTree(BiTree *T)
    {
        
        ElemType ch;
        cin >> ch;
        if (ch == '#')
            *T = NULL;  //保证是叶结点
        else
        {
        
            *T = (BiTree)malloc(sizeof(BiTNode));
            //if (!*T)
                //exit(OVERFLOW); //内存分配失败则退出。
            (*T)->data = ch;//生成结点
            CreateBiTree(&(*T)->lchild);//构造左子树
            CreateBiTree(&(*T)->rchild);//构造右子树    
        }
    }
    //表示对遍历到的结点数据进行的处理操作,此处操作是将树结点前序遍历输出
    void operation1(ElemType ch)
    {
        
        cout << ch << " ";
    }
    //此处在输出的基础上，并输出层数
    void operation2(ElemType ch, int level)
    {
        
           cout << ch << "在第" << level << "层" << endl;
    }
    
    
    //递归方式前序遍历二叉树
    void PreOrderTraverse(BiTree T, int level)
    {
        
        if (T == NULL)
            return;
    /*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
        //operation1(T->data);
        operation2(T->data, level); //输出了层数
        PreOrderTraverse(T->lchild, level + 1);
        PreOrderTraverse(T->rchild, level + 1);
    }
    
    //递归方式中序遍历二叉树
    
    void InOrderTraverse(BiTree T,int level)
    {
        
    	if(T==NULL)
    		return;
    	InOrderTraverse(T->lchild,level+1);
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    	InOrderTraverse(T->rchild,level+1);
    }
    
    //递归方式后序遍历二叉树
    
    void PostOrderTraverse(BiTree T,int level)
    {
        
    	if(T==NULL)
    		return;
    	PostOrderTraverse(T->lchild,level+1);
    	PostOrderTraverse(T->rchild,level+1);
    	//operation1(T->data);
    	operation2(T->data, level); //输出了层数
    }
    
    
    int main()
    {
        
        int level = 1; //表示层数
        BiTree T = NULL;
        cout << "请以前序遍历的方式输入扩展二叉树："; //类似输入AB#D##C##
        CreateBiTree(&T);// 建立二叉树，没有树，怎么遍历
    
        cout << "递归前序遍历输出为：" << endl;
        PreOrderTraverse(T, level);//进行前序遍历，其中operation1()和operation2()函数表示对遍历的结点数据进行的处理操作
        cout << endl;
    
        cout << "递归中序遍历输出为：" << endl;
        InOrderTraverse(T, level);
        cout << endl;
    
        cout << "递归后序遍历输出为：" << endl;
        PostOrderTraverse(T, level);
        cout << endl;
    
        return 0;
    }

**注意：**

1.  建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“\#”时，指针指向NULL，说明是叶结点。

如下图为扩展二叉树：（前序遍历为：ABDG\#\#H\#\#\#CE\#I\#\#F\#\#）

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tDym9p2U-1583935067741)(http://liufan.vip/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2019-4-6-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B9%8B%E6%A0%912/2.png)\]

1.  `operation1( )`函数只是对各个结点的输出；
2.  `operation2( )`函数不仅输出了各个结点，同时输出了结点所在的层数。

### 运行结果 ###

1.  只是运行了`operation2( )`函数，有层数输出：

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d1C9zEB6-1583935067742)(http://liufan.vip/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2019-4-6-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B9%8B%E6%A0%912/3.png)\]

1.  只是运行了`operation1( )`函数，输出值：

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aEqNAhKP-1583935067742)(http://liufan.vip/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2019-4-6-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B9%8B%E6%A0%912/4.png)\]

## 非递归算法 ##

1.  我们可以**借助栈**，**实现3种遍历的非递归算法**
2.  除此之外，还给出了二叉树的**层次遍历**算法，所谓层次遍历，就是**自顶向下、自左至右**的遍历二叉树中的元素，可以**借助队列实现**。

### 程序实现 ###

//非递归方式前序遍历
    /* 思路：将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。*/
    void PreOrder(BiTree T){
        
        stack<BiTree> stack;
        //p是遍历指针  
        BiTree p = T;
        //p不为空或者栈不空时循环
        while (p || !stack.empty())
    {
        
            if (p != NULL)
                     {
        
                //存入栈中  
                stack.push(p);
                //对树中的结点进行操作
                operation1(p->data);
                 //遍历左子树  
                p = p->lchild;
             }
            else
                    {
        
                     //退栈  
                p = stack.top();
                stack.pop();
                //访问右子树  
                p = p->rchild;
            }
        } 
    }
    //非递归中序遍历
    void InOrder(BiTree T)
    {
        
        stack<BiTree> stack;
        //p是遍历指针  
        BiTree p = T;
        //p不为空或者栈不空时循环  
        while (p || !stack.empty())
           {
        
            if (p != NULL)
                      {
        
                //存入栈中  
                stack.push(p);
                //遍历左子树  
                p = p->lchild;
             }
            else
                    {
        
                //退栈
                p = stack.top();
                operation1(p->data); //对树中的结点进行操作
                stack.pop();
                //访问右子树  
                p = p->rchild;
            }
        } 
    }
    //非递归后序遍历
    typedef struct BiTNodePost{
        
        BiTree biTree;
        char tag;
    }BiTNodePost, *BiTreePost;
    
    void PostOrder(BiTree T)
    {
        
        stack<BiTreePost> stack;
        //p是遍历指针  
        BiTree p = T;
        BiTreePost BT;
        //栈不空或者p不空时循环  
        while (p != NULL || !stack.empty())
            {
        
            //遍历左子树  
            while (p != NULL)
                   {
        
                BT = (BiTreePost)malloc(sizeof(BiTNodePost));
                BT->biTree = p;
                //访问过左子树  
                BT->tag = 'L';
                stack.push(BT);
                p = p->lchild;
            }
            //左右子树访问完毕访问根节点  
            while (!stack.empty() && (stack.top())->tag == 'R')
                    {
        
                BT = stack.top();
                //退栈  
                stack.pop();
                p=BT->biTree;
                cout<<BT->biTree->data<<" ";
            }
            //遍历右子树  
            if (!stack.empty())
                    {
        
                BT = stack.top();
                //访问过右子树  
                BT->tag = 'R';
                p = BT->biTree;
                p = p->rchild;
            }
        }
    }
    //层次遍历  
    void LevelOrder(BiTree T)
    {
        
        BiTree p = T; 
        queue<BiTree> queue;
        //根节点入队  
        queue.push(p);
        //队列不空循环  
        while (!queue.empty())
           {
        
            //对头元素出队  
            p = queue.front();
            //访问p指向的结点  
            operation1(p->data);
            //退出队列  
            queue.pop();
            //左孩子不为空，将左孩子入队  
            if (p->lchild != NULL)
                    {
        
                queue.push(p->lchild);
            }
            //右孩子不空，将右孩子入队  
            if (p->rchild != NULL)
                    {
        
                queue.push(p->rchild);
            }
        }
    }

**下面是完整的实现代码**

#include<iostream>
    #include<stdlib.h>
    #include<stack>
    #include<queue>
    using namespace std;
    
    typedef char ElemType;
    
    //二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
    
    typedef  struct BiTNode
    {
        
        ElemType data;
        struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    //二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树
    void CreateBiTree(BiTree *T)
    {
        
        ElemType ch;
        cin >> ch;
        if (ch == '#')
            *T = NULL;  //保证是叶结点
        else
        {
        
            *T = (BiTree)malloc(sizeof(BiTNode));
            //if (!*T)
                //exit(OVERFLOW); //内存分配失败则退出。
            (*T)->data = ch;//生成结点
            CreateBiTree(&(*T)->lchild);//构造左子树
            CreateBiTree(&(*T)->rchild);//构造右子树    
        }
    }
    
    //表示对遍历到的结点数据进行的处理操作,此处操作是将树结点前序遍历输出
    void operation1(ElemType ch)
    {
        
        cout << ch << " ";
    }
    //此处在输出的基础上，并输出层数
    void operation2(ElemType ch, int level)
    {
        
           cout << ch << "在第" << level << "层" << "  ";
    }
    
    
    //递归方式前序遍历二叉树
    void PreOrderTraverse(BiTree T, int level)
    {
        
        if (T == NULL)
            return;
    /*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
        operation1(T->data);
        //operation2(T->data, level); //输出了层数
    
        PreOrderTraverse(T->lchild, level + 1);
        PreOrderTraverse(T->rchild, level + 1);
    }
    
    //递归方式中序遍历二叉树
    
    void InOrderTraverse(BiTree T,int level)
    {
        
    if(T==NULL)
    return;
    InOrderTraverse(T->lchild,level+1);
    
    operation1(T->data);
    //operation2(T->data, level); //输出了层数
    
    InOrderTraverse(T->rchild,level+1);
    }
    
    //递归方式后序遍历二叉树
    
    void PostOrderTraverse(BiTree T,int level)
    {
        
    if(T==NULL)
    return;
    PostOrderTraverse(T->lchild,level+1);
    PostOrderTraverse(T->rchild,level+1);
    
    operation1(T->data);
    //operation2(T->data, level); //输出了层数
    }
    
    //非递归方式前序遍历
    /* 思路：将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。*/
    void PreOrder(BiTree T){
        
        stack<BiTree> stack;
        //p是遍历指针  
        BiTree p = T;
        //p不为空或者栈不空时循环
        while (p || !stack.empty())
    {
        
            if (p != NULL)
                     {
        
                //存入栈中  
                stack.push(p);
                //对树中的结点进行操作
                operation1(p->data);
                 //遍历左子树  
                p = p->lchild;
             }
            else
                    {
        
                     //退栈  
                p = stack.top();
                stack.pop();
                //访问右子树  
                p = p->rchild;
            }
        } 
    }
    //非递归中序遍历
    void InOrder(BiTree T)
    {
        
        stack<BiTree> stack;
        //p是遍历指针  
        BiTree p = T;
        //p不为空或者栈不空时循环  
        while (p || !stack.empty())
           {
        
            if (p != NULL)
                      {
        
                //存入栈中  
                stack.push(p);
                //遍历左子树  
                p = p->lchild;
             }
            else
                    {
        
                //退栈
                p = stack.top();
                operation1(p->data); //对树中的结点进行操作
                stack.pop();
                //访问右子树  
                p = p->rchild;
            }
        } 
    }
    //非递归后序遍历
    typedef struct BiTNodePost{
        
        BiTree biTree;
        char tag;
    }BiTNodePost, *BiTreePost;
    
    void PostOrder(BiTree T)
    {
        
        stack<BiTreePost> stack;
        //p是遍历指针  
        BiTree p = T;
        BiTreePost BT;
        //栈不空或者p不空时循环  
        while (p != NULL || !stack.empty())
            {
        
            //遍历左子树  
            while (p != NULL)
                   {
        
                BT = (BiTreePost)malloc(sizeof(BiTNodePost));
                BT->biTree = p;
                //访问过左子树  
                BT->tag = 'L';
                stack.push(BT);
                p = p->lchild;
            }
            //左右子树访问完毕访问根节点  
            while (!stack.empty() && (stack.top())->tag == 'R')
                    {
        
                BT = stack.top();
                //退栈  
                stack.pop();
                p=BT->biTree;
                cout<<BT->biTree->data<<" ";
            }
            //遍历右子树  
            if (!stack.empty())
                    {
        
                BT = stack.top();
                //访问过右子树  
                BT->tag = 'R';
                p = BT->biTree;
                p = p->rchild;
            }
        }
    }
    //层次遍历  
    void LevelOrder(BiTree T)
    {
        
        BiTree p = T; 
        queue<BiTree> queue;
        //根节点入队  
        queue.push(p);
        //队列不空循环  
        while (!queue.empty())
           {
        
            //对头元素出队  
            p = queue.front();
            //访问p指向的结点  
            operation1(p->data);
            //退出队列  
            queue.pop();
            //左孩子不为空，将左孩子入队  
            if (p->lchild != NULL)
                    {
        
                queue.push(p->lchild);
            }
            //右孩子不空，将右孩子入队  
            if (p->rchild != NULL)
                    {
        
                queue.push(p->rchild);
            }
        }
    }
    int main()
    {
        
        int level = 1; //表层数
        BiTree T = NULL;
        cout << "请以前序遍历的方式输入扩展二叉树："; //类似输入AB#D##C##
        CreateBiTree(&T);// 建立二叉树，没有树，怎么遍历
        cout << "递归前序遍历输出为：" << endl;
        PreOrderTraverse(T, level);//进行前序遍历，其中operation1()和operation2()函数表示对遍历的结点数据进行的处理操作
        cout << endl;
        cout << "递归中序遍历输出为：" << endl;
        InOrderTraverse(T, level);
        cout << endl;
        cout << "递归后序遍历输出为：" << endl;
        PostOrderTraverse(T, level);
        cout << endl;
            cout<<"非递归前序遍历输出为："<<endl;
            PreOrder(T);
            cout<<endl;
            cout<<"非递归前序遍历输出为："<<endl;
            InOrder(T);
            cout<<endl;
            cout<<"非递归前序遍历输出为："<<endl;
            PostOrder(T);
            cout<<endl;
            cout<<"层序遍历输出为："<<endl;
            LevelOrder(T);
            cout<<endl;
        return 0;
    }

### 运行结果 ###

只是运行了`operation1( )`函数，输出值：

![format_png][]  
补充：**另外一种实现二叉树后序遍历的非递归算法**。

void PostOrder(BiTree T){
        
        InitStack(s);
        p=T;
        r=NULL;                                  //辅助判断右子树是否被访问过
        while(p||!IsEmpty(s)){
        
            if(p){
                                       //走到最左边
                push(s,p);
                p=p->lchild;
            }
            else{
                                        //向右
                GetTop(s,p);                     //取栈顶结点
                if(p->rchild&&p->rchild!=r){
             //如果右子树存在且未被访问过
                    p=p->rchild;                 //转向右
                    push(s,p);                   //压入栈
                    p=p->lchild;                 //再转向左
                }
                else{
                                    //否则，弹出结点并访问
                    pop(s,p);                    //结点出栈
                    visit(p->data);              //访问该结点
                    r=p;                         //记录最近访问过的结点
                    p=NULL;                      //结点访问完后，重置p指针
                }
            }
        }
    }

**重要结论**：

1.  二叉树的**前序和中序**序列能**唯一确定**一棵二叉树
2.  二叉树的**后序和中序**序列能**唯一确定**一棵二叉树
3.  二叉树的**层次和中序**序列能**唯一确定**一棵二叉树

## 参考资料 ##

[c实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序）][c_c]  
[树（二叉树）的建立和遍历算法（二）][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JsdWVzbGl1Zg_size_16_color_FFFFFF_t_70]: /images/20220223/47a3306051b74692bc8929c1c00edf4d.png
[c_c]: https://www.cnblogs.com/liuamin/p/6269950.html
[format_png]: /images/20220223/0d82e0964a5e487c96ac5b853c2d9b81.png
[Link 1]: https://www.cnblogs.com/liuamin/p/6383315.html