二叉树的中序遍历(C语言)
我们从两个方向讲解二叉树的中序遍历(递归+迭代)
一.递归
思想:
从根节点开始向其的左孩子遍历,一直访问每个节点的左孩子,当其走到NULL时返回,返回时记录每个节点的数值,然后访问该节点的右孩子,如果为NULL直接返回上一层,如果不为NULL则重复上面的操作,直到遍历完所有的节点为止.
代码如下:
void BTreeInOrder(struct TreeNode* root,int* arry,int* returnSize){//中序遍历 if(NULL==root){//判出条件 return; } BTreeInOrder(root->left,arry,returnSize); arry[(*returnSize)++]=root->val; BTreeInOrder(root->right,arry,returnSize); }
具体运行过程:(如图)
二. 迭代:
思想:(前序遍历是入栈时记录结点数值(具体可看我之前写的前序遍历),中序遍历是出栈时记录结点数值)
我们根据上面知道递归的过程是如何进行的,所以可以使用栈来模仿这个过程,从而使用迭代实现二叉树的中序遍历,第一个循环从根节点开始进行入栈,每次让栈顶元素的左孩子入栈直到栈顶元素为NULL时进入下一个循环,先将NULL出栈,然后记录栈顶元素的数值和地址再将其出栈,之后将这个记录的元素的右孩子入栈,为NULL则继续第二个循环,不为NULL则退出第二个循环,继续进行第一个循环,直到所有的结点访问完为止.
代码如下:
typedef struct TreeNode BTNode; typedef struct Stack{//C语言中没有栈,所以我自己定义个栈的结构体方便后面使用 BTNode* a_[100];//存储结点的指针数组 int size;//数组长度 }Stack; void StackPush(Stack* b,BTNode* root){//入栈 b->a_[b->size++]=root; } void StackPop(Stack* b){//出栈 b->size--; } int* inorderTraversal(struct TreeNode* root, int* returnSize){//中序遍历 int* a=(int*)malloc(sizeof(int)*100);//动态创建数组用来存储遍历时的结点数值 if(NULL==a){ printf("申请节点失败! "); return NULL; } Stack b;//创建栈变量 int i=0; BTNode* root_temp;//创建一个指针变量用来记录出栈时的栈顶元素 b.size=0;//初始化栈 StackPush(&b,root);//先将根节点入栈 while(NULL != b.a_[b.size-1]){//第一个循环 StackPush(&b,b.a_[b.size-1]->left);//将栈顶元素的左孩子入栈,直到栈顶为NULL时进入 //下一个循环 while(NULL == b.a_[b.size-1]){//第二个循环 StackPop(&b);//向将NULL出栈 if(0==b.size){//判断是否访问完所有结点 (*returnSize)=i; return a; } a[i++]=b.a_[b.size-1]->val;//记录栈顶元素的值 root_temp=b.a_[b.size-1];//记录栈顶元素的地址 StackPop(&b);//将栈顶元素出栈 StackPush(&b,root_temp->right);//将记录的元素的右孩子入栈,继续进行循环 } } (*returnSize)=i; return a; }
具体运行过程:(如图)
下一篇:
Python如何进行插入排序?