用c语言写二叉查找树的构造与遍历

二叉查找树（Binary Search Tree, BST）是一种常用的数据结构，它能够快速地进行查找、插入和删除操作。下面是使用C语言实现二叉查找树的构造和遍历的代码示例。

首先，定义一个二叉树节点的结构体：

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

接下来，定义二叉树的构造函数。二叉查找树的构造函数需要满足以下两个条件：

- 左子树的所有节点的值都小于根节点的值；
- 右子树的所有节点的值都大于根节点的值。

TreeNode* buildBST(int* nums, int numsSize) {
    if (numsSize == 0) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = nums[numsSize / 2];
    root->left = buildBST(nums, numsSize / 2);
    root->right = buildBST(nums + numsSize / 2 + 1, numsSize - numsSize / 2 - 1);
    return root;
}

上述代码中，我们使用了递归的方式构造二叉查找树。首先，找到数组的中间位置，将其作为根节点的值。然后，递归构造左子树和右子树。

接下来，定义二叉树的遍历函数。二叉查找树的遍历有三种方式：前序遍历、中序遍历和后序遍历。

前序遍历：先遍历根节点，然后递归遍历左子树和右子树。

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

中序遍历：先递归遍历左子树，然后遍历根节点，最后递归遍历右子树。

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

后序遍历：先递归遍历左子树和右子树，最后遍历根节点。

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

最后，我们可以使用以下代码来测试上述函数：

int main() {
    int nums[] = {1, 2, 3, 4, 5, 6, 7};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    TreeNode* root = buildBST(nums, numsSize);
    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\nInorder traversal: ");
    inorderTraversal(root);
    printf("\nPostorder traversal: ");
    postorderTraversal(root);
    printf("\n");
    return 0;
}