二叉树的四种遍历之C语言实现

作者 : 开心源码 本文共1141个字,预计阅读时间需要3分钟 发布时间: 2022-05-13 共259人阅读

现在有这样一颗二叉树:

image.png

先序遍历

思路与代码

按照:本节点,左子树,右子树 的顺序遍历

void PriorOrder(BTNode* b) {    if(b)    {        printf("%c", b->data);        PriorOrder(b->lchild);        PriorOrder(b->rchild);      }} 

过程分析

一开始,我们会先遍历最顶上的树(红色方框内)
这个数的三个部分:根节点,左子树,右子树,分别由蓝色方框圈起来
我们首先访问本节点A,而后访问左子树,也就是蓝色方框内的左边的整体

image.pngimage.png

现在单独把左子树提出来看,也是一样的方法:先访问B,而后访问左节点,D,而后再访问右子树。

image.png

我们再把右子树提出来:还是一样,先访问E再访问H,而后现在,最开始ABC组成的数的根节点和左子树都访问完了,所以现在开始去访问ABC这个数的右节点

image.png

ABC树的右节点:

image.png

同理像上面那样访问就可。
最终访问顺序:A B D E H C F I J G

中序遍历

思路与代码

按照:左节点,本节点,右节点 的顺序遍历

void InOrder(BTNode* b) {    if(b)    {        InOrder(b->lchild);        printf("%c", b->data);        InOrder(b->rchild);     }} 

过程还是和上面一样,只不过先把左子树访问完。
输出顺序:D B H E A F J I C G

后续遍历

思路与代码

按照:左节点,右节点 ,本节点 的顺序遍历

void PostOrder(BTNode* b) {    if(b)    {        PostOrder(b->lchild);        PostOrder(b->rchild);        printf("%c", b->data);      }} 

输出顺序:D H E B J I F G C A

层次遍历

思路与代码

按照:根节点,第一层,第二层…的顺序遍历

void LevelTraversal(BTNode* b){    if(b)    {        //定义队列         BTNode* queue[MaxSize];        int top=0;        queue[top] = b;        int i = 0;                //只需队列里有元素         while(i<=top)        {            //将左右子树加入队列             if(queue[i]->lchild)            {                top++;                queue[top] = queue[i]->lchild;              }            if(queue[i]->rchild)            {                top++;                queue[top] = queue[i]->rchild;              }            i++;        }        //现在这个队列按层次顺序容纳了二叉树的每个节点            for(i=0;i<=top;i++)        {            //挨个打出来就可             printf("%c", queue[i]->data);        }                   //我比较懒所以就没写出队,这其实当成个栈也可以     }           } 

很显然,是一层一层的访问,所以顺序就是A B C D E F G H I J

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 二叉树的四种遍历之C语言实现

发表回复