中序遍历代码
中序遍历是二叉树遍历的一种方式，它的遍历顺序为：先遍历左子树，然后访问根节点，最后遍历右子树。在实现中序遍历时，我们需要使用递归或者非递归的方式进行实现。下面我们将分别介绍这两种方式的实现方法。
一、递归实现中序遍历
递归是一种简单而常用的算法思想，在二叉树中序遍历中也可以使用递归来实现。具体实现步骤如下：
1. 如果当前节点为空，则返回。
2. 递归访问当前节点的左子树。
3. 访问当前节点。
4. 递归访问当前节点的右子树。
下面是使用C++语言实现中序遍历的代码：
```c++
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}
```
二叉树中序遍历非递归算法
在上面的代码中，我们首先判断了当前节点是否为空，如果为空则直接返回。否则，我们先递归访问当前节点的左子树，然后输出当前节点的值，并且最后再递归访问右子树。
二、非递归实现中序遍历
除了使用递归的方式，我们还可以使用栈来实现非递归的中序遍历。具体实现步骤如下：
1. 初始化一个空栈和一个指向根节点的指针。
2. 如果当前节点不为空或者栈不为空，则执行以下操作：
  1. 如果当前节点不为空，则将当前节点入栈，并将指针移动到当前节点的左子树。
  2. 如果当前节点为空，则弹出栈顶元素，并输出它的值，并将指针移动到该元素的右子树。
下面是使用C++语言实现中序遍历的代码：
```c++
void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* p = root;
    while (p != nullptr || !st.empty()) {
        if (p != nullptr) {
            st.push(p);
            p = p->left;
        } else {
            p = st.top();
            st.pop();
            cout << p->val << " ";
            p = p->right;
        }
    }
}
```
在上面的代码中，我们首先初始化了一个空栈和一个指向根节点的指针。然后，如果当前节点不为空或者栈不为空，则进行循环操作。在循环中，我们首先判断当前节点是否为空，如果不为空则将其入栈，并且将指针移动到其左子树。否则，我们弹出栈顶元素并输出其值，并且将指针移动到该元素的右子树。
总结
中序遍历是二叉树遍历的一种方式，它的遍历顺序为：先遍历左子树，然后访问根节点，最后遍历右子树。在实现中序遍历时，我们可以使用递归或者非递归的方式进行实现。无论是
哪种方式，都需要注意空指针的情况，并且要保证访问节点的顺序符合中序遍历的规则。

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