二叉树的四种遍历之C语言实现
现在有这样一颗二叉树:
image.png
先序遍历
思路与代码
按照:本节点,左子树,右子树 的顺序遍历
void PriorOrder(BTNode* b) { if(b) { printf("%c", b->data); PriorOrder(b->lchild); PriorOrder(b->rchild); }} 过程分析
一开始,我们会先遍历最顶上的树(红色方框内)
这个数的三个部分:根节点,左子树,右子树,分别由蓝色方框圈起来
我们首先访问本节点A,而后访问左子树,也就是蓝色方框内的左边的整体
image.png
image.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语言实现
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 二叉树的四种遍历之C语言实现