先序遍历构建二叉树c语言

先序遍历是一种常用的二叉树遍历方式，它按照“根节点 -> 左子树 -> 右子树”的顺序访问每个节点。在C语言中，如果你有一个递归函数用于先序遍历，其结构通常如下：

typedef struct TreeNode {
    int val;         // 节点值
    struct TreeNode *left; // 左子节点指针
    struct TreeNode *right; // 右子节点指针
} TreeNode;

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

在这个函数里，首先检查根节点是否为空，如果不为空就打印其值，然后递归地对左右子树进行相同的操作。

相关问题

输入中序遍历和先序遍历构建二叉树的c语言代码

以下是根据输入的中序遍历序列和先序遍历序列构建二叉树的 C 语言实现：

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

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

// 递归构建二叉树函数
struct TreeNode* buildTreeHelper(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return NULL;
    }

    // 构建当前节点，即先序遍历序列的第一个元素
    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = preorder[preStart];
    root->left = NULL;
    root->right = NULL;

    // 在中序遍历序列中寻找当前节点的位置，以区分左右子树
    int index = inStart;
    while (index <= inEnd && inorder[index] != preorder[preStart]) {
        index++;
    }

    int leftSize = index - inStart; // 左子树的节点个数
    int rightSize = inEnd - index; // 右子树的节点个数

    // 递归构建左右子树
    root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
    root->right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);

    return root;
}

// 构建二叉树函数的入口
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    return buildTreeHelper(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1);
}

// 中序遍历函数（测试用）
void inorderTraversal(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    int preorder[] = {1,2,4,5,3,6,7}; // 先序遍历序列
    int inorder[] = {4,2,5,1,6,3,7}; // 中序遍历序列
    int size = sizeof(preorder) / sizeof(int);

    struct TreeNode *root = buildTree(preorder, size, inorder, size);
    inorderTraversal(root);

    return 0;
}

输出结果：

4 2 5 1 6 3 7

用C语言编写一下用先序遍历构建二叉树链表

在C语言中，我们可以使用结构体表示二叉树节点，并结合递归来实现先序遍历构建二叉树链表。这里是一个简单的示例：

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

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

// 创建新的节点
TreeNode* newNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (!node) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    node->val = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 先序遍历函数
TreeNode* buildTreePreorder(int arr[], int start, int end) {
    if (start > end)
        return NULL;

    // 选取第一个元素作为根节点
    TreeNode* root = newNode(arr[start]);
    
    // 找到根节点的子节点
    int i;
    for (i = start + 1; i <= end && arr[i] < arr[start]; i++) {
        root->left = buildTreePreorder(arr, start + 1, i);
    }

    for (; i <= end && arr[i] >= arr[start]; i++) {
        root->right = buildTreePreorder(arr, i, end);
    }

    return root;
}

// 测试函数
void printInOrder(TreeNode* root) {
    if (root == NULL)
        return;

    printInOrder(root->left);
    printf("%d ", root->val);
    printInOrder(root->right);
}

int main() {
    int arr[] = {3, 9, 20, 15, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    TreeNode* root = buildTreePreorder(arr, 0, n - 1);

    printf("In-order traversal of the binary tree: ");
    printInOrder(root);

    return 0;
}

这个程序会根据给定的数组`arr`中的值进行先序遍历，构建一棵二叉搜索树，然后打印出按照中序遍历的顺序。请注意，这个版本假设输入的数组已经按照升序排序，如果实际应用中不是这样的情况，需要先对数组进行排序。