c++二叉树中序遍历

以下是C++中二叉树中序遍历的实现方法：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    Solution s;
    s.inorderTraversal(root); // 输出：1 3 2

    return 0;
}

相关问题

c++二叉树中序遍历输出

在 C++ 中，二叉树的中序遍历是一种按照“左-根-右”顺序访问节点的方式。如果你有一个递归实现，可以这样做：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        // 首先遍历左子树
        inorderTraversal(root->left);
        // 然后访问根节点
        std::cout << root->val << " ";
        // 最后遍历右子树
        inorderTraversal(root->right);
    }
}

如果你想通过迭代的方式来完成中序遍历，你可以使用一个栈辅助：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr || !s.empty()) {
        // 如果当前节点不为空，将其入栈并继续处理其左子树
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }

        // 弹出栈顶元素并访问它，然后移动到右子树
        curr = s.top();
        s.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

C++二叉树的中序遍历

二叉树的中序遍历可以通过递归实现。具体实现过程如下：

1.如果树为空，则返回。

2.对根节点的左子树进行递归遍历。

3.输出根节点的值。

4.对根节点的右子树进行递归遍历。

代码实现如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

在实际使用中，我们可以将中序遍历的结果存储在一个数组中，然后进行后续的操作。