c++实现中序遍历二叉树的递归算法和非递归算法

以下是中序遍历二叉树的递归算法和非递归算法的实现代码，供您参考：

递归算法：

void inorder_recursive(TreeNode* root) {
    if (root) {
        inorder_recursive(root->left);
        cout << root->val << " ";
        inorder_recursive(root->right);
    }
}

非递归算法：

void inorder_nonrecursive(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top();
        stk.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

请注意，这里的 `TreeNode` 结构体是二叉树节点的定义，其中包含了节点的值、左子节点和右子节点。如果您需要使用这些代码，请先自行定义 `TreeNode` 结构体。

相关问题

用C++语言实现 实验内容 1．输入字符序列，建立二叉链表。 2．中序遍历二叉树:递归算法。 3．中序遍历二叉树:非递归算法。 4.先序遍历二叉树 5.后序遍历二叉树 4．求二叉树的高度 。 5．求二叉树的叶子个数。 6．编写一个主函数,调试上述算法。

好的，下面是一个用C++语言实现二叉树相关操作的完整代码，包括建立二叉链表、中序遍历（递归和非递归）、先序遍历、后序遍历、求二叉树高度和求二叉树叶子个数。

#include <iostream>
#include <stack>
using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 建立二叉链表
TreeNode* createTree() {
    char val;
    cin >> val;
    if (val == '#') return nullptr;
    TreeNode* node = new TreeNode(val);
    node->left = createTree();
    node->right = createTree();
    return node;
}

// 中序遍历二叉树:递归算法
void inorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversalRecursive(root->left);
    cout << root->data << " ";
    inorderTraversalRecursive(root->right);
}

// 中序遍历二叉树:非递归算法
void inorderTraversalIterative(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;
    while (current != nullptr || !s.empty()) {
        while (current != nullptr) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        cout << current->data << " ";
        current = current->right;
    }
}

// 先序遍历二叉树
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << " ";
}

// 求二叉树的高度
int treeHeight(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 求二叉树的叶子个数
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

// 编写一个主函数,调试上述算法
int main() {
    cout << "请输入二叉树的节点（使用#表示空节点）: ";
    TreeNode* root = createTree();
    
    cout << "中序遍历（递归）: ";
    inorderTraversalRecursive(root);
    cout << endl;
    
    cout << "中序遍历（非递归）: ";
    inorderTraversalIterative(root);
    cout << endl;
    
    cout << "先序遍历: ";
    preorderTraversal(root);
    cout << endl;
    
    cout << "后序遍历: ";
    postorderTraversal(root);
    cout << endl;
    
    cout << "二叉树的高度: " << treeHeight(root) << endl;
    
    cout << "二叉树的叶子个数: " << countLeaves(root) << endl;
    
    return 0;
}

用c++语言写二叉树中序遍历的递归算法

二叉树的中序遍历是指先遍历左子树，再遍历根节点，最后遍历右子树。

递归算法的核心思想是先递归遍历左子树，然后输出根节点，最后递归遍历右子树。

下面是用 C++ 语言写二叉树中序遍历的递归算法的代码：

#include <iostream>
using namespace std;

// 二叉树结点的定义
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);  // 递归遍历右子树
}

int main() {
    // 创建二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 中序遍历二叉树
    inorderTraversal(root);
    cout << endl;

    return 0;
}

输出结果为：

4 2 5 1 3

说明递归算法实现了二叉树的中序遍历。