6-1 中序遍历二叉树 C++

在C++中，六要素表示的是左孩子右兄弟（Left Child Right Sibling）的概念，而6-1中序遍历二叉树通常是指按照先遍历左子树，然后访问根节点，最后遍历右子树的方式。以下是使用递归实现的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); // 首先递归遍历左子树
        cout << root->val << " "; // 访问根节点值
        inorderTraversal(root->right); // 然后遍历右子树
    }
}

在这个函数里，我们首先检查根节点是否为空，如果不为空就先访问左子树，接着访问根节点，最后访问右子树。这个过程会一直持续到所有节点都被访问过为止。

相关问题

c++实现以下功能1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树1 4.中序遍历二叉树2 5.后序遍历二叉树 6.层序遍历二叉树 7.求二叉树的深度 8.退出

C++可以通过定义二叉树节点结构体以及相应的函数来实现以上功能：

1. 创建二叉树：可以通过递归或者非递归方式实现，具体实现方式可以根据需求选择。递归方式实现时，可以采用前序遍历的方式，先创建根节点，再分别创建左右子树；非递归方式可以采用层序遍历的方式，从上到下、从左到右依次创建节点。

2. 先序遍历二叉树：先输出当前节点的值，再遍历左子树，最后遍历右子树。

3. 中序遍历二叉树1：先遍历左子树，再输出当前节点的值，最后遍历右子树。

4. 中序遍历二叉树2：采用非递归方式实现时，需要借助栈数据结构。从根节点开始，将左子树节点依次入栈，然后出栈，输出当前节点的值，再将右子树入栈。

5. 后序遍历二叉树：先遍历左子树，再遍历右子树，最后输出当前节点的值。

6. 层序遍历二叉树：从上到下、从左到右依次遍历每一层节点。

7. 求二叉树的深度：可以采用递归方式求解，分别求出左子树和右子树的深度，然后取较大值加1即为二叉树的深度。

8. 退出：程序结束。

用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;
}