C语⾔实现⼆叉树的中序遍历
⼆叉树是⼀种重要的数据结构，对⼆叉树的遍历也很重要。这⾥简单介绍三种⼆叉树中序遍历的⽅法。⼆叉树的中序遍历就是⾸先遍历左⼦树，然后访问当前节点，最后遍历右⼦树。对于下⾯的⼆叉树，中序遍历结果如下：
结果：[5,10,6,15,2]
直观来看，⼆叉树的中序遍历就是将节点投影到⼀条⽔平的坐标上。如图：
1、递归法
这是思路最简单的⽅法，容易想到并且容易实现。递归的终⽌条件是当前节点是否为空。⾸先递归调⽤遍历左⼦树，然后访问当前节点，最后递归调⽤右⼦树。代码如下：
void inorder(struct TreeNode* root,int* res,int* resSize){
if(!root){
return;
}
//递归到最后⼀定是⼀个左右⼦树都为空的节点
inorder(root->left, res, resSize);//先左
res[(*resSize)++]= root->val;//然后中间节点
inorder(root->right, res, resSize);//最后右边
}
int*inorderTraversal(struct TreeNode* root,int* returnSize){
int* res =malloc(sizeof(int)*501);
*returnSize =0;
inorder(root, res, returnSize);
return res;
}
复杂度分析
时间复杂度：O(n)，其中 nn 为⼆叉树节点的个数。⼆叉树的遍历中每个节点会被访问⼀次且只会被访问⼀次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，⽽栈深度在⼆叉树为⼀条链的情况下会达到 O(n) 的级别。
2、迭代法-栈
先序中序后序遍历二叉树在迭代⽅法中，从根节点开始⼆叉树的最左节点，将⾛过的节点保存在⼀个栈中，到最左节点后访问，对于每个节点来说，它都是以⾃⼰为根的⼦树的根节点，访问完之后就可以转到右⼦上了。代码如下：
int*inorderTraversal(struct TreeNode* root,int* returnSize){
//初始化
*returnSize =0;
//为返回的的数组分配空间
int* res =malloc(sizeof(int)*501);
//创建⼀个存储TreeNode指针的指针数组，也就是栈
struct TreeNode** stk =malloc(sizeof(struct TreeNode*)*501);
int top =0;//栈的指⽰位，⼀开始指向0
//最后跳出⼤循环的时候，root==NULL，top == 0
while(root !=NULL|| top >0){
//压栈操作，将当前节点以及所有其左⼦树全部压⼊
while(root !=NULL){
stk[top++]= root;
root = root->left;
}
//将栈顶的数据弹出
root = stk[--top];
res[(*returnSize)++]= root->val;
root = root->right;
}
return res;
}
复杂度分析
时间复杂度：O(n)，其中 nn 为⼆叉树节点的个数。⼆叉树的遍历中每个节点会被访问⼀次且只会被访问⼀次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，⽽栈深度在⼆叉树为⼀条链的情况下会达到 O(n) 的级别。
3、Morris法
这种⽅法是Morris发明的，看完之后感觉精妙⽆⽐。这种⽅法不使⽤递归，不使⽤栈，O(1)的空间复杂度完成⼆叉树的遍历。这种⽅法的基本思路就是将所有右⼉⼦为NULL的节点的右⼉⼦指向后继节点（对于右⼉⼦不为空的节点，右⼉⼦就是接下来要访问的节点）。这样，对于任意⼀个节点，当访问完它后，它的右⼉⼦已经指向了下⼀个该访问的节点。对于最右节点，不需要进⾏这样的操作。注意，这样的操作是在遍历的时候完成的，完成访问节点后会把树还原。整个循环的判断条件为当前节点是否为空。例如上⾯的⼆叉树，遍历过程如下（根据当前节点c的位置）：
（1）当前节点为10，因为左⼉⼦⾮空，不能访问，到c的左⼦树的最右节点p：
结果：[]
（2）节点c的左⼦树的最右节点有两种终⽌条件，⼀种右⼉⼦为空，⼀种右⼉⼦指向当前节点。下⾯是右⼉⼦为空的情况，这种情况先要构造，将节点p的右⼉⼦指向后继节点c，然后c下移：
结果：[]
（3）当前节点c的左⼉⼦为空，进⾏访问。访问后将c指向右⼉⼦（即后继节点）：
结果：[5]
（4）继续寻左⼦树的最右节点，这次的终⽌条件是最右节点为当前节点。这说明当前节点的左⼦树遍历完毕，访问当前节点后，还原⼆叉树，将当前节点指向后继节点：
结果：[5,10]
（5）重复上述过程，直到c指向整棵⼆叉树的最右节点：
左⼉⼦为空，进⾏访问，c转到右⼉⼦。右⼉⼦为空，不满⾜判断条件，循环结束，遍历完成。结果如下：
[5,10,6,15,2]
这就是Morris⽅法，时间复杂度为O(n)，空间复杂度是O(1)。代码如下：
int*inorderTraversal(struct TreeNode* root,int* returnSize){
int* res =malloc(sizeof(int)*501);
*returnSize =0;
struct TreeNode* predecessor =NULL;
while(root !=NULL){
if(root->left !=NULL){
// predecessor 节点就是当前 root 节点向左⾛⼀步，然后⼀直向右⾛⾄⽆法⾛为⽌
predecessor = root->left;
while(predecessor->right !=NULL&& predecessor->right != root){
predecessor = predecessor->right;
}
// 让 predecessor 的右指针指向 root，继续遍历左⼦树
if(predecessor->right ==NULL){
predecessor->right = root;
root = root->left;
}
/
/ 说明左⼦树已经访问完了，我们需要断开链接
else{
res[(*returnSize)++]= root->val;
predecessor->right =NULL;
root = root->right;
}
}
// 如果没有左孩⼦，则直接访问右孩⼦
else{
res[(*returnSize)++]= root->val;
root = root->right;
}
}
return res;
}
时间复杂度：O(n)，其中 nn 为⼆叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总 时间复杂度为O(2n)=O(n)。
空间复杂度：O(1)O(1)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。