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

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

二叉树的遍历

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

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

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

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

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

所有代码均来自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( )函数，输出值：


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

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实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序）
树（二叉树）的建立和遍历算法（二）

全部评论

相关推荐

11-23 12:35
澳门科技大学 品类运营
点赞 评论 收藏
分享
头像
11-24 10:46
山东大学 嵌入式软件工程师
刷到羊毛月，我想说：我们并不欠优绩主义什么
昨天刷到了羊毛月的视频，很绝啊，没想到这人非要插这么一嘴是图啥，嫌自己过得太好了？然后思考了一下，其实他和李佳琦有很多相似之处，甚至可以说他们算是一类人：努力过，并且努力有结果，有巨大的成功和回报，然后将这些成功归功于优绩主义并贯穿言行。这里说的优绩主义并不是说成绩好，而是&nbsp;Meritocracy&nbsp;--&nbsp;一种社会理念和管理理念，主张社会与经济的奖赏应当依据个人的才能、努力和成就来决定。他们往往认为在机会平等的条件下，人们通过公平竞争，成绩优异者应该获得更多的奖励和认可。优绩主义的核心思想是，能够者应该居上，即最有能力和努力的人应该获得更高的社会地位和经济回报。但起码此时此刻，作为非既得利益者，...
给一个offer求了：他也还好吧，跟大部分人比他算是很幸运的了，感觉他三句话离不开北大，但是如果他出生在距离北京八中50公里以外的河北省，他的人生会截然不同诶。京津冀总给人一种特别割裂的感觉。
牛客创作赏金赛 0offer是寒冬太冷还是我太菜
点赞 评论 收藏
分享
11-04 14:10
东南大学 Java
躺平了，这逼互联网谁爱卷谁卷吧
_可乐多加冰_：去市公司包卖卡的
点赞 评论 收藏
分享
11-21 23:17
门头沟学院 研发工程师
秋招可以暂告一个段落啦
上周腾讯开奖后，本来想这周把字节三面和叠纸的hr面面完再决定的，但是不是很想折腾了，叠纸后面还有高管面，感觉就算过了最后也不一定有鹅香，就直接不拖签三方了。七月底开始的秋招，投了将近百来家，初筛/笔试/复筛挂了将近一半，面试了应该有五六十场，也经历了不少压力面，其实早就倦怠了，8月高强度八股后就再也没看过八股，也不想刷题了，每天处于一种躺等面试的状态，就这样一直拖到11月，终于等到结果了。可以轮到鼠鼠来写经验分享咯：一、&nbsp;稳住心态整个秋招流程中一定会经历各种心态崩了的时刻，比如：为什么我这么匹配这个岗位结果初筛挂了？为什么我笔试都做出来了把我挂了？为什么我都答上来了还是没通过面试？其实都是正常...
查看6道真题和解析
点赞 评论 收藏
分享
1 1 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
304706次浏览 2705人参与
# 如果不工作真的会快乐吗 #
59566次浏览 520人参与
# 阿里云管培生offer #
18131次浏览 299人参与
# 地方国企笔面经互助 #
3939次浏览 11人参与
# 美团求职进展汇总 #
1328667次浏览 12454人参与
# 选完offer后，你后悔学本专业吗 #
20253次浏览 144人参与
# 百度开奖 #
164418次浏览 984人参与
# 正在实习的你，几点下班 #
52218次浏览 392人参与
# 国央企薪资爆料 #
8845次浏览 69人参与
# 如何一边实习一边秋招 #
992815次浏览 12640人参与
# 提前批简历挂麻了怎么办 #
146637次浏览 1948人参与
# 学历or实习经历，哪个更重要 #
51409次浏览 403人参与
# 海康威视求职进展汇总 #
399199次浏览 3406人参与
# 米哈游求职进展汇总 #
176251次浏览 1460人参与
# 求职遇到的搞笑事件 #
70953次浏览 577人参与
# 投递实习岗位前的准备 #
1180000次浏览 18399人参与
# 面试体验感最好的是哪家？ #
85206次浏览 846人参与
# 实习生应该准时下班吗 #
167529次浏览 1159人参与
# 得物求职进展汇总 #
66437次浏览 682人参与
# 网申一定要掌握的小技巧 #
5368次浏览 54人参与
# 招聘要求与实际实习内容不符怎么办 #
10334次浏览 273人参与
# 0offer是寒冬太冷还是我太菜 #
899459次浏览 8016人参与
牛客网
牛客企业服务