c语言实现二叉排序树的查找、插入、建立、删除和打印

好的，我来为您介绍一下如何使用C语言实现二叉排序树的查找、插入、建立、删除和打印。

1. 建立二叉排序树

我们可以通过以下代码来建立一棵二叉排序树：

typedef struct node {
    int data;           // 数据域
    struct node *left;  // 左子树
    struct node *right; // 右子树
} Node, *Tree;

// 插入节点
void insertNode(Tree *t, int data) {
    if (*t == NULL) {
        *t = (Node*)malloc(sizeof(Node));
        (*t)->data = data;
        (*t)->left = NULL;
        (*t)->right = NULL;
    } else if (data < (*t)->data) {
        insertNode(&((*t)->left), data);
    } else if (data > (*t)->data) {
        insertNode(&((*t)->right), data);
    }
}

// 建立二叉排序树
void createTree(Tree *t, int data[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        insertNode(t, data[i]);
    }
}

这段代码中，我们定义了一个Node结构体表示二叉排序树的节点，其中包括数据域data和左右子树指针left和right。通过insertNode函数实现节点的插入，通过createTree函数实现二叉排序树的建立。

2. 查找节点

我们可以通过以下代码来查找二叉排序树中的某个节点：

// 查找节点
Node* searchNode(Tree t, int data) {
    if (t == NULL) {
        return NULL;
    } else if (data == t->data) {
        return t;
    } else if (data < t->data) {
        return searchNode(t->left, data);
    } else {
        return searchNode(t->right, data);
    }
}

这段代码中，我们通过递归的方式实现了查找节点的功能，如果节点为空则返回NULL，如果节点数据等于查找数据则返回该节点，如果查找数据小于节点数据则继续在左子树中查找，如果查找数据大于节点数据则继续在右子树中查找。

3. 插入节点

我们可以通过以下代码来向二叉排序树中插入一个新节点：

// 插入节点
void insertNode(Tree *t, int data) {
    if (*t == NULL) {
        *t = (Node*)malloc(sizeof(Node));
        (*t)->data = data;
        (*t)->left = NULL;
        (*t)->right = NULL;
    } else if (data < (*t)->data) {
        insertNode(&((*t)->left), data);
    } else if (data > (*t)->data) {
        insertNode(&((*t)->right), data);
    }
}

这段代码中，我们通过递归的方式实现了节点的插入功能，如果节点为空则创建一个新节点，如果插入数据小于节点数据则继续在左子树中插入，如果插入数据大于节点数据则继续在右子树中插入。

4. 删除节点

我们可以通过以下代码来删除二叉排序树中的某个节点：

// 删除节点
void deleteNode(Tree *t, int data) {
    Node *p;
    if (*t == NULL) {
        return;
    } else if (data < (*t)->data) {
        deleteNode(&((*t)->left), data);
    } else if (data > (*t)->data) {
        deleteNode(&((*t)->right), data);
    } else if ((*t)->left && (*t)->right) {
        p = findMax((*t)->left);
        (*t)->data = p->data;
        deleteNode(&((*t)->left), (*t)->data);
    } else {
        p = *t;
        if ((*t)->left == NULL) {
            *t = (*t)->right;
        } else if ((*t)->right == NULL) {
            *t = (*t)->left;
        }
        free(p);
    }
}

// 查找最大节点
Node* findMax(Tree t) {
    if (t == NULL) {
        return NULL;
    } else if (t->right == NULL) {
        return t;
    } else {
        return findMax(t->right);
    }
}

这段代码中，我们通过递归的方式实现了节点的删除功能，如果节点为空则返回，如果删除数据小于节点数据则继续在左子树中删除，如果删除数据大于节点数据则继续在右子树中删除，如果节点同时存在左右子树，则找到左子树中的最大节点并替换要删除的节点，然后在左子树中删除该节点，否则直接删除该节点。

5. 打印二叉排序树

我们可以通过以下代码来打印二叉排序树：

// 中序遍历打印二叉排序树
void printTree(Tree t) {
    if (t != NULL) {
        printTree(t->left);
        printf("%d ", t->data);
        printTree(t->right);
    }
}

这段代码中，我们通过中序遍历的方式实现了打印二叉排序树的功能，按照左子树、根节点、右子树的顺序打印节点数据。