中序遍历二叉树pta函数

中序遍历是一种常见的二叉树遍历方式，它按照“左-根-右”的顺序访问二叉树的节点。在C++中，如果你有一个二叉树结构（例如`struct TreeNode`），并且你想编写一个递归的中序遍历函数，你可以这样做：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    // 其他成员...
};

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) { // 当前节点不为空
        inorderTraversal(root->left); // 递归遍历左子树
        cout << root->val << " "; // 访问当前节点值
        inorderTraversal(root->right); // 递归遍历右子树
    }
}

这个`inorderTraversal`函数首先检查根节点是否为空，如果不为空，就先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。这样就可以得到中序遍历的结果。

相关问题

pta 中序遍历二叉树 黄龙军 要求实现函数，输出二叉树的中序遍历序列。二叉树采用二叉链表存储

在 C 语言中，对于给定的二叉树结构，黄龙军的要求是编写一个函数来实现中序遍历（Inorder Traversal）。二叉链表存储的二叉树，其节点通常包含两个指针，分别指向左孩子和右孩子。

下面是一个简单的中序遍历算法的示例实现：

#include <stdio.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() {
    // 创建并初始化二叉树...
    TreeNode* root = ...; // 填充实际的树结构

    inorderTraversal(root);

    return 0;
}

在这个代码片段中，`inorderTraversal` 函数按照"左-右"的顺序递归地访问每个节点，将节点值添加到结果序列中。

建立与遍历二叉树pta

建立与遍历二叉树通常涉及两个关键步骤：创建二叉树结构和实现遍历算法。

1. **创建二叉树**：
- 二叉树是一种数据结构，每个节点最多有两个子节点，分别称为左孩子和右孩子。可以使用递归或迭代的方式构建二叉树。例如，对于一个简单的节点类，可以有如下的定义：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    // 构造函数
    TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

2. **遍历二叉树**：
- **前序遍历（Preorder Traversal）**: 先访问根节点，然后遍历左子树，最后遍历右子树。
- **中序遍历（Inorder Traversal）**: 先遍历左子树，然后访问根节点，最后遍历右子树。这个顺序适合打印排序后的数值。
- **后序遍历（Postorder Traversal）**: 先遍历左子树，然后遍历右子树，最后访问根节点。
- 还有其他一些遍历方式，比如层序遍历（Level Order Traversal），从上到下逐层访问。

以下是几种常见遍历方法的示例代码（这里以递归为例）:

// 前序遍历
void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
}

// 中序遍历
void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }
}

// 后序遍历
void postorderTraversal(TreeNode root) {
    if (root != null) {
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}