编写中序遍历二叉树的程序

中序遍历是一种常见的二叉树遍历算法，它按照“左-根-右”的顺序访问节点。在递归版本的中序遍历中，对于每个节点，我们首先遍历它的左子树，然后访问当前节点，最后遍历其右子树。

以下是一个简单的 Python 代码示例，使用递归实现中序遍历：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    if root is not None:
        # 遍历左子树
        inorder_traversal(root.left)
        # 访问当前节点
        print(root.val, end=" ")
        # 遍历右子树
        inorder_traversal(root.right)

# 使用示例
root = TreeNode(1, TreeNode(2), TreeNode(3))
inorder_traversal(root)  # 输出: 2 1 3

如果你想要非递归的方式实现，可以使用栈数据结构，但是代码会稍微复杂一些。非递归中序遍历的基本思路是：将待访问节点入栈，同时处理左子树，直到遇到空节点，然后出栈并访问该节点，再继续处理右子树。

相关问题

用c编写中序遍历二叉树的程序

在C语言中，中序遍历二叉树通常会采用递归的方式来实现。首先，你需要定义一个结构体表示二叉树节点，然后提供函数来进行遍历。以下是简单的中序遍历的代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        // 先遍历左子树
        inorderTraversal(root->left);
        
        // 访问当前节点
        printf("%d ", root->val);
        
        // 再遍历右子树
        inorderTraversal(root->right);
    }
}

int main() {
    // 创建并初始化一个二叉树...（这里省略具体的创建过程）
    
    // 调用中序遍历函数
    inorderTraversal(root);

    return 0;
}

在这个例子中，`inorderTraversal`函数会先访问左子节点，然后访问根节点，最后访问右子节点，这就是典型的"左-根-右"顺序，也就是中序遍历。

1、用前序方法建立一棵二叉树。 2、编写前序遍历二叉树的程序。 3、编写中序遍历二叉树的程序。 4、编写后序遍历二叉树的程序。 5、编写统计二叉树叶子结点个数的程序

1. 前序建立二叉树的方法：

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

TreeNode createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return nullptr; // -1 表示该结点为空
    }
    TreeNode* root = new TreeNode);
    root->left = createTree();
    root->right = createTree();
    return root;
}

2. 前序遍历二叉树的程序：

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

3. 中序遍历二叉树的程序：

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

4. 后序遍历二叉树的程序：

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

5. 统计二叉树叶子结点个数的程序：

int countLeaf(TreeNode* root) {
    if (!root) {
        return 0;
    }
    if (!root->left && !root->right) {
        return 1;
    }
    return countLeaf(root->left) + countLeaf(root->right);
}