二叉排序树的建立代码

二叉排序树（Binary Search Tree，BST），也称为二叉查找树或二叉搜索树，是一种特殊的二叉树。它具有以下性质：

1. 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的节点值；
2. 若任意节点的右子树不为空，则右子树上所有节点的值均大于或等于它的节点值；
3. 任意节点的左、右子树也分别为二叉排序树；
4. 没有键值相等的节点。

这些性质确保了二叉排序树可以被用来进行高效的数据查找、插入和删除操作。下面，我们将探讨如何建立一棵二叉排序树，并提供相应的代码实现。

二叉排序树的节点结构

首先，我们需要定义二叉排序树的节点结构。在C语言中，可以这样定义：

typedef struct BST_Node {
    int data; // 节点存储的数据
    struct BST_Node* left; // 指向左子树的指针
    struct BST_Node* right; // 指向右子树的指针
} BST_Node;

建立二叉排序树

建立二叉排序树的过程实际上就是按照一定的顺序插入节点的过程。对于每个要插入的节点，我们从根节点开始，比较节点的值：

• 如果节点值小于当前节点的值，就向左子树进发；
• 如果节点值大于或等于当前节点的值，就向右子树进发。

重复这个过程，直到找到一个空位置（即遇到NULL指针），然后在这个位置创建新节点。

以下是建立二叉排序树的C语言函数实现：

#include 
#include 

// 创建新节点的函数
BST_Node* createNode(int data) {
    BST_Node* newNode = (BST_Node*)malloc(sizeof(BST_Node));
    if (!newNode) {
        return NULL;
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点的函数
BST_Node* insertNode(BST_Node* root, int data) {
    // 如果树为空，创建新节点作为根节点
    if (root == NULL) {
        return createNode(data);
    }
    // 否则，递归地在左子树或右子树中插入节点
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data >= root->data) {
        root->right = insertNode(root->right, data);
    }
    return root; // 返回根节点
}

// 主函数，用于测试插入节点
int main() {
    BST_Node* root = NULL;
    int data[] = {50, 30, 20, 40, 70, 60, 80};
    for (int i = 0; i < sizeof(data) / sizeof(data[0]); i  ) {
        root = insertNode(root, data[i]);
    }
    // 树已经建立完成
    return 0;
}

二叉排序树的遍历

一旦二叉排序树建立完成，我们可以通过遍历来查看它的结构。常见的遍历方式有：

• 前序遍历：先访问根节点，然后左子树，最后右子树；
• 中序遍历：先左子树，然后根节点，最后右子树；
• 后序遍历：先左子树，然后右子树，最后根节点。

每种遍历方式都有其递归和非递归的实现方法。中序遍历特别重要，因为它能按照键值的递增顺序访问所有节点。

结语

二叉排序树是一种简单而强大的数据结构，它在组织和检索数据方面非常有效。通过递归地插入节点，我们可以轻松地构建出一棵二叉排序树。然而，需要注意的是，二叉排序树的性能高度依赖于其结构的平衡性。在最坏的情况下，如果二叉排序树严重不平衡，其操作的时间复杂度会退化到O(n)。因此，在实际应用中，有时需要考虑使用平衡二叉树或其他更高级的数据结构来保证性能。