C语言中二叉树的后序遍历详解
首先我们从两个方面讲解二叉树的后序遍历(递归+迭代)
一.二叉树的后序遍历.(递归)
思想:
首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,②开始遍历其右孩子,如果其为NULL则访问该节点的值域,并返回其双亲节点重复第二步的操作,如果其不为NULL则以该节点为根节点重复第一步的操作.直到访问完所有节点时结束递归.
代码:
void BTreePostOrder(struct TreeNode* root,int* arry,int* Size){//后序遍历 if(NULL==root){//递归出口 return; } BTreePostOrder(root->left,arry,Size);//遍历左孩子 BTreePostOrder(root->right,arry,Size);//遍历右孩子 arry[(*Size)++]=root->val;//访问该节点 }
运行过程:(如图)
二.二叉树的后序遍历(迭代)
我们应该知道二叉树的前中后序遍历使用递归非常的简单,但是如果用迭代的话就比较有难度了,因此我思考了很久有没有一种迭代类型的算法与递归的框架相似(递归的三种算法框架非常相似只要会一个其他的便很好写出来),我们是否可以写出一种迭代算法:只用改变访问结点的次序便可以在迭代的方式下实现二叉树的前中后序遍历,因此我们使用数据结构中栈来模仿递归的形式实现了二叉树的前序遍历(在进栈时访问结点值域),中序遍历(在出栈时访问结点的值域),这种方法可以在同一种框架中实现迭代层面二叉树的前序遍历和中序遍历,但是到了后序遍历就没办法了,之后经过思考前序遍历与后序遍历的关系从而实现了同一种框架中实现前中后序遍历的迭代算法.
1.相信很多人在刚学习二叉树时都遇到过这种问题,选择题给定一颗二叉树,让我们给出二叉树的前中后序遍历的节点顺序.(每个人都有自己的计算方法),下面说一下我的计算方法.
前序:我们按图中红色箭头的顺序和其指向依次读取箭头上的结点便可得到其前序遍历.
中序:我们按图中红色箭头的顺序和其指向依次读取箭头上的结点便可得到其中序遍历.
后序:我们按图中红色箭头的顺序和其指向依次读取箭头上的结点便可得到其后序遍历.
经过上图我们可以看出二叉树的后序遍历刚好与从右孩子开始的前序遍历所得到的的值完全相反.因此我们可以使用前序遍历的代码从右孩子开始进行前序遍历,最后将得到的值反向打印即可.
代码:
typedef struct TreeNode BTNode; typedef struct Stack{//栈的结构体 BTNode* array[100]; int size; }Stack; void StackPush(Stack* a,BTNode* root){//入栈 a->array[(a->size)++]=root; } void StackPop(Stack* a){//出栈 (a->size)--; } void Reverse(int* a,int Long){//反向打印 int left_1=0; int right_1=Long-1; while(left_1 < right_1){ int temp=a[left_1]; a[left_1]=a[right_1]; a[right_1]=temp; left_1++; right_1--; } } int* postorderTraversal(struct TreeNode* root, int* returnSize){//从右孩子开始的前序遍历 int* b=(int*)malloc(sizeof(int)*100); if(NULL==b){ printf("申请节点失败!\n"); return NULL; } Stack a; a.size=0; BTNode* root_temp; int i=0; StackPush(&a,root); while(NULL != a.array[a.size-1]){ b[i++]=a.array[a.size-1]->val; StackPush(&a,a.array[a.size-1]->right); while(NULL == a.array[a.size-1]){ StackPop(&a); if(0 == a.size){ Reverse(b,i); (*returnSize)=i; return b; } root_temp=a.array[a.size-1]; StackPop(&a); StackPush(&a,root_temp->left); } } Reverse(b,i); (*returnSize)=i; return b; }
从右孩子开始的前序遍历:正常的前序遍历是先访问节点,然后遍历其左孩子,再遍历其右孩子.而该前序遍历是先访问节点,然后遍历其右孩子,再遍历其左孩子.
代码:
void BTreeInOrder(struct TreeNode* root,int* arry,int* Size){//前序遍历 if(NULL==root){//递归出口 return; } arry[(*Size)++]=root->val;//访问该节点 BTreeInOrder(root->right,arry,Size);//遍历右孩子 BTreeInOrder(root->left,arry,Size);//遍历左孩子 }
具体比较如图:
总结
到此这篇关于C语言中二叉树的后序遍历详解的文章就介绍到这了,更多相关C语言二叉树的后序遍历内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/weixin_49312527/article/details/122655
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04
- 这篇文章主要介绍了在C#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25