二叉搜索树实现

2025年03月17日 | 阅读 9 分钟

本文介绍了一个使用 C 语言编写的二叉搜索树应用程序的多种操作。二叉搜索树是一种二叉树，其中每个节点的左子树值都小于该节点的值，而该节点的值又小于右子树中的每个值。

在本文中，我们将定义二叉搜索树，并展示如何使用 C 语言来实现各种二叉搜索树操作。

树是一种用于以分层格式表示数据的特定类型的数据结构。它可以被描述为一组节点——事物或实体的集合——它们相互连接以产生层次结构的错觉。树是非线性数据结构，因为它们的数据不是以线性或顺序方式组织的。

二叉搜索树中的项目是根据特定顺序排列的。二叉搜索树要求左节点的值小于父节点，右节点的值大于父节点。根节点的左分支和右分支都遵循此规则，并且是递归的。

建议在继续学习二叉搜索树之前，先快速了解一下树数据结构。

C 语言中的二叉搜索树基础

二叉搜索树是一种树状数据结构，它允许用户对信息进行排序和存储。由于每个节点最多只能有两个子节点，因此称为二叉树。它也称为搜索树，因为我们可以在 O(log(n)) 的时间内查找数字。

二叉树的典型特征是

根节点大于左子树中的所有节点。
根节点的数值小于右子树中的每个节点。
每个节点的两个子树也同样是二叉搜索树，因此它们也具有上述两个特征。

二叉搜索树示例

下图显示了两个二叉搜索树，其中一个符合二叉搜索树的所有要求，而另一个则偏离了标准。

节点 3 的右子树包含一个小于它的值，因此右边的二叉树不是二叉搜索树。

如何用 C 语言操作二叉搜索树

二叉搜索树可以通过三种基本操作来处理：

操作 1：搜索

在搜索中，我们需要在数据结构中找到一个特定的项。由于二叉搜索树中的元素是按排序顺序存储的，因此搜索过程变得更加简单。

以下是在二叉树中搜索元素的算法：

将要搜索的元素与树的根节点进行比较。
如果被搜索元素的数值等于根节点的数值，则返回根节点。
如果数值不相同，则检查它是否小于根元素，如果是，则导航到左子树。
如果大于根元素，则遍历右子树。
如果整个树中都没有该元素，则返回 NULL。

借助一个我们试图搜索值为 20 的项的示例，现在让我们探讨一下用 C 语言编写的二叉搜索树中的搜索操作。

步骤 1

步骤 2

操作 2：插入

在二叉搜索树中，元素始终插入到叶子节点。如果要插入的元素小于根节点的值或根节点本身，我们从根节点开始搜索操作，并在左子树中寻找一个空位置；否则，我们在右子树中寻找空位置。

以下是将元素添加到二叉树的算法：

C 代码

   if node == NULL 
        return creatingNode(data)
   if (data < node -> data)
        node -> left  = insert(node -> left, data)
   else if (data > node -> data)
        node -> right = insert(node -> right, data)
   return node

现在我们有一个特定的实例，其中我们试图插入一个值为 65 的项。让我们看看插入在二叉搜索树中是如何工作的。

操作 3：删除

在删除操作中，必须从二叉搜索树中删除一个节点，而不能违反其任何属性。删除可能发生在三种情况中的一种：

1. 要删除的第一个节点是叶子节点。

这是从二叉搜索树中删除节点的最简单情况。在这里，我们将叶子节点替换为 NULL 并释放分配的空间。

借助一个显示我们删除值为 90 的节点的示例，我们可以更好地理解二叉搜索树中的删除过程。

2. 被删除的节点只有一个子节点。

在这种情况下，目标节点将被其子节点替换，然后子节点将被删除。因此，要删除的值现在将存在于子节点中。因此，为了释放分配的空间，我们将子节点简单地替换为 NULL。

在下面的示例中，必须删除值为 79 的节点。由于此节点只有一个子节点，因此将用 55 替换它。

3. 要删除的节点有两个子节点。

与其他两种情况相比，这种情况更复杂。在这里，我们执行以下操作来删除节点：

我们将找到目标节点的“中序后继”以便将其删除。
一旦目标节点到达叶子节点，就用后继节点替换该节点。
用 NULL 替换目标节点以释放分配的空间。

在下面的示例中，必须删除根节点 45。因此，节点 55 将作为根节点的直接后继节点被添加到其中。节点 45 现在将靠近树的叶子节点，易于删除。

用于实现二叉搜索树的 C 程序

现在，让我们使用 C 语言来实现二叉树节点的创建和遍历。在这里，我们将重点关注影响二叉搜索树的操作，例如节点的插入、删除和搜索。

C 语言程序

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

struct node {
  int data;
  struct node *right_child;
  struct node *left_child;
};

struct node* new_node(int x){
  struct node *temp;
  temp = malloc(sizeof(struct node));
  temp->data = x;
  temp->left_child = NULL;
  temp->right_child = NULL;

  return temp;
}

struct node* search(struct node * root, int x){
  if (root == NULL || root->data == x)
    return root;
  else if (x > root->data)
    return search(root->right_child, x);
  else
    return search(root->left_child, x);
}

struct node* insert(struct node * root, int x){
  if (root == NULL)
    return new_node(x);
  else if (x > root->data)
    root->right_child = insert(root->right_child, x);
  else 
    root -> left_child = insert(root->left_child, x);
  return root;
}
struct node* find_minimum(struct node * root) {
  if (root == NULL)
    return NULL;
  else if (root->left_child != NULL)
    return find_minimum(root->left_child);
  return root;
}

struct node* delete(struct node * root, int x) {

  if (root == NULL)
    return NULL;
  if (x > root->data)
    root->right_child = delete(root->right_child, x);
  else if (x < root->data)
    root->left_child = delete(root->left_child, x);
  else {
    if (root->left_child == NULL && root->right_child == NULL){
      free(root);
      return NULL;
    }
    else if (root->left_child == NULL || root->right_child == NULL){
      struct node *temp;
      if (root->left_child == NULL)
        temp = root->right_child;
      else
        temp = root->left_child;
      free(root);
      return temp;
    }
    else {
      struct node *temp = find_minimum(root->right_child);
      root->data = temp->data;
      root->right_child = delete(root->right_child, temp->data);
    }
  }
  return root;
}

void inorder(struct node *root){
  if (root != NULL) 
  {
    inorder(root->left_child); 
    printf(" %d ", root->data); 
    inorder(root->right_child); 
  }
}

int main() {
  struct node *root;
  root = new_node(20);
  insert(root, 5);
  insert(root, 1);
  insert(root, 15);
  insert(root, 9);
  insert(root, 7);
  insert(root, 12);
  insert(root, 30);
  insert(root, 25);
  insert(root, 40);
  insert(root, 45);
  insert(root, 42);

  inorder(root);
  printf("\n");

  root = delete(root, 1);

  root = delete(root, 40);

  root = delete(root, 45);

  root = delete(root, 9);

  inorder(root);
  printf("\n");

  return 0;
}

输出

1  5  7  9  12  15  20  25  30  40  42  45 
 5  7  12  15  20  25  30  42

C 语言编写的二叉搜索树中的数组表示和遍历

我们现在将使用数组来创建一个二叉搜索树程序（C 语言）。将使用数组表示在 C 语言中创建二叉树，然后实现中序、前序和后序遍历。

考虑以下数组并尝试从中创建一棵树

在上图中，0 代表 NULL。例如，节点 B 的左右子节点都是 NULL，这表明 B 是一个叶子节点。

C 语言程序

#include <stdio.h>

int max_node = 15;
char tree[] = {'\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L'};

int get_right_child(int index){
  if (tree[index] != '\0' && ((2 * index) + 1) <= max_node)
    return (2 * index) + 1;
  return -1;
}

int get_left_child(int index){
  if (tree[index] != '\0' && (2 * index) <= max_node)
    return 2 * index;
  return -1;
}

void preorder(int index){
  if (index > 0 && tree[index] != '\0'){
    printf(" %c ", tree[index]);
    preorder(get_left_child(index));
    preorder(get_right_child(index));
  }
}

void postorder(int index){
  if (index > 0 && tree[index] != '\0'){
    postorder(get_left_child(index));
    postorder(get_right_child(index));
    printf(" %c ", tree[index]);
  }
}

void inorder(int index){
  if (index > 0 && tree[index] != '\0'){
    inorder(get_left_child(index));
    printf(" %c ", tree[index]);
    inorder(get_right_child(index));
  }
}

int main() {
  printf("Preorder:\n");
  preorder(1);
  printf("\nPostorder:\n");
  postorder(1);
  printf("\nInorder:\n");
  inorder(1);
  printf("\n");
  return 0;
}

输出

Preorder:
 D  A  E  G  Q  B  F  R  V  T  J  L 
Postorder:
 G  Q  E  B  A  V  R  J  L  T  F  D 
Inorder:
 G  E  Q  A  B  D  V  R  F  J  T  L

具有遍历和链表表示的二叉搜索树的 C 程序

我们现在将使用链表在 C 语言中实现二叉树。将使用链表表示在 C 语言中创建二叉树，然后实现中序、前序和后序遍历。

C 语言程序

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

    struct node
    {
        char data;
        struct node *right_child;
        struct node *left_child;
    };

    struct node* new_node(char data)
    {
        struct node *temp;
        temp = malloc(sizeof(struct node));
        temp -> data = data;
        temp -> left_child = NULL;
        temp -> right_child = NULL;

        return(temp); 
    }

    void preorder(struct node *root)
    {
        if(root != NULL) 
        {
            printf(" %c ", root -> data); 
            preorder(root -> left_child);
            preorder(root -> right_child);
        }
    }

    void postorder(struct node *root)
    {
        if(root != NULL)
        {
            postorder(root -> left_child); 
            postorder(root -> right_child); 
            printf(" %c ", root -> data); 
        }
    }

    void inorder(struct node *root)
    {
        if(root != NULL) 
        {
            inorder(root -> left_child); 
            printf(" %c ", root -> data); 
            inorder(root -> right_child);
        }
    }

    int main()
    {
        struct node *root; 
        root = new_node('D'); 

        root -> left_child = new_node('A');
        root -> right_child = new_node('F'); 
        root -> left_child -> left_child = new_node('E'); 
        root -> left_child -> right_child = new_node('B');

        printf("Preorder:\n");
        preorder(root);
        printf("\n");
        printf("Postorder:\n");
        postorder(root);
        printf("\n");
        printf("Inorder:\n");
        inorder(root);
        printf("\n");

        return 0;
    }

输出

Preorder:
 D  A  E  B  F 
Postorder:
E  B  A  F  D 
Inorder:
 E  A  B  D  F

C 语言中的二叉搜索树复杂度

时间复杂度

插入

最佳情况： O(logn)
平均情况： O(logn)
最坏情况： O(n)

删除

最佳情况： O(logn)
平均情况： O(logn)
最坏情况： O(n)

搜索

最佳情况： O(logn)
平均情况： O(logn)
最坏情况： O(n)

空间复杂度

插入： O(n)
删除： O(n)
搜索： O(n)

[在这种情况下，树节点的数量是 n。]

C 语言中的二叉搜索树应用

数据库中使用二叉搜索树实现多级索引。
二叉搜索树可用于动态排序。
Unix 内核通过二叉搜索树控制虚拟内存区域。

结论

二叉搜索树是一种二叉树，其中每个节点的左子树值都小于该节点的值，而该节点的值又小于右子树中的每个值。
由于二叉搜索树中的项目以排序顺序保存，因此搜索变得更加容易。
在二叉搜索树中，插入操作始终在叶子节点执行。
二叉搜索树的删除过程包含三种情况，其中包括：
- 要删除的节点没有子节点。
- 被删除的节点只有一个子节点。
- 要删除的节点有两个子节点。

文章到此结束。我真诚地希望您觉得这篇文章内容丰富且有益。

下一主题查找替换给定范围内子数组的最大和

二叉搜索树实现

C 语言中的二叉搜索树基础

二叉搜索树示例

如何用 C 语言操作二叉搜索树

操作 1：搜索

操作 2：插入

操作 3：删除

用于实现二叉搜索树的 C 程序

C 语言编写的二叉搜索树中的数组表示和遍历

具有遍历和链表表示的二叉搜索树的 C 程序

C 语言中的二叉搜索树复杂度

时间复杂度

C 语言中的二叉搜索树应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树