C语言递归实现二叉树的遍历

二叉树的遍历分为三种：前序遍历、中序遍历和后序遍历。递归实现二叉树的遍历是比较简单的方法之一，下面以前序遍历为例，给出C语言递归实现二叉树的遍历的代码：

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

// 前序遍历
void preorderTraversal(struct TreeNode* root){
    if(root == NULL) return;
    printf("%d ",root->val); // 先访问根结点
    preorderTraversal(root->left); // 再访问左子树
    preorderTraversal(root->right); // 最后访问右子树
}

在上面的代码中，我们定义了二叉树结点的结构体，包括结点值和左右子树指针。然后，我们定义了一个前序遍历函数`preorderTraversal`，它接受一个指向二叉树根结点的指针作为参数。

在函数内部，我们首先判断当前结点是否为空，如果为空，则直接返回。否则，我们先访问当前结点的值，然后递归访问左子树和右子树。这样就可以完成前序遍历了。

当然，中序遍历和后序遍历的递归实现与前序遍历类似，只需要改变访问结点的顺序即可。

相关问题

用c语言采用二叉树递归遍历算法编程实现二叉树遍历（采用先序、中序和后序三遍历算法），用键盘输入二叉树

在C语言中，我们可以使用结构体来表示二叉树节点，并利用递归的方式实现先序（根-左-右）、中序（左-根-右）和后序（左-右-根）遍历。首先，我们需要定义二叉树节点的数据结构：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

接下来，我们分别编写三种遍历函数：

1. 先序遍历 (Preorder):

void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->val); // 访问当前节点
        preorderTraversal(root->left); // 递归遍历左子树
        preorderTraversal(root->right); // 递归遍历右子树
    }
}

2. 中序遍历 (Inorder):

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

3. 后序遍历 (Postorder):

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->val); // 访问当前节点
    }
}

为了获取用户输入构建二叉树，你需要提供一个函数接收用户输入并创建节点，这通常需要额外的输入处理逻辑。你可以询问用户输入数字以及左、右孩子的索引等信息。

构建二叉树示例：

// 用户输入部分（假设已有一个读取用户输入并构造树的函数buildTree()）
TreeNode* inputTree = buildTree(); // 根据实际需求实现这个函数

完整的程序应该包含输入处理、构建二叉树和遍历功能的整合。

c语言递归函数二叉树的遍历

以下是C语言递归函数实现二叉树的遍历的代码示例：

1.先序遍历

void PreOrder(BiTree T) {
    if (T ! NULL) {
        printf("%d ", T->key); // 先访问根节点
        PreOrder(T->left); // 再遍历左子树
        PreOrder(T->right); // 最后遍历右子树
    }
}

2.中序遍历

void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->left); // 先遍历左子树
        printf("%d ", T->key); // 再访问根节点
        InOrder(T->right); // 最后遍历右子树
    }
}

3.后序遍历

void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->left); // 先遍历左子树
        PostOrder(T->right); // 再遍历右子树
        printf("%d ", T->key); // 最后访问根节点
    }
}