在本文中，我们将介绍在C/C ++中实现二进制搜索树的方法。

二进制搜索树(BST)是一种二进制树，其中左子树的每个元素都小于根节点，而右子树中的每个元素都大于根节点。

从根节点开始，此定义适用于树中的每个节点。

二进制搜索树

其中从根开始的左子树包含比其小的元素，而右子树具有比其大的元素。
如您所见，这也适用于树中的每个节点。

因此，BST通常称为"排序二叉树"，因为按顺序遍历(请参阅本文以了解其含义)将给出元素的排序列表。

现在，让我们在实施之前理解其中涉及的一些概念。

在C/C ++中为二进制搜索树创建数据结构

让我们为BST编写结构和一些辅助功能。

任何Binary Search Tree节点都有一个data元素，以及指向它的left和right子代的指针。
它还具有一个标记" is_leaf"，以检查其是否为叶节点。

让我们现在写我们的结构

typedef struct TreeNode {
  //TreeNode structure for the Binary Search Tree (BST)
  //A BST has the left subtree being less than the root,
  //while the right subtree is greater than the root
  int data; //A Node contains data
  struct TreeNode* left, *right; //As well as pointers to the left and right children
  int is_leaf; //Check whether a node is a leaf node or not
}TreeNode;

现在，我们将创建一个用于创建新树节点的函数，以初始化参数。

TreeNode* make_treenode(int data) {
  //Construct a treenode pointer using data
  TreeNode* node = (TreeNode*) calloc (1, sizeof(TreeNode));
  node->data = data;
  node->left = node->right = NULL;
  node->is_leaf = 1;
  return node;
}

我们还要编写一个函数，以从内存中释放C/C ++中完整的二进制搜索树。

void free_bst(TreeNode* root) {
  //Frees the complete BST from memory
  if (!root)
      return;
  free_bst(root->left);
  free_bst(root->right);
  free(root);
}

现在让我们进入" insert_bst()"方法，该方法将一个节点插入BST。

将数据插入二叉搜索树

任何二进制搜索树(BST)具有以下属性：

• 左子树的元素值小于根节点
• 右子树的元素大于根节点

因此，如果要插入节点，则必须通过将节点的键与当前根进行比较来确保节点必须具有正确的位置。

为了展示插入的完成方式，我们来看一个例子。

考虑下面的树，其中只有一个节点。

第一步

我们在这棵树中插入20。
由于45> 20，因此必须将其插入左侧的子树中。
由于我们的子树是空的，因此我们可以直接添加它。

第二步

现在，我们插入15。
由于15 <45，我们将插入到左子树并更新当前根。
现在，再次检查当前根(20)。
15 <20，因此我们再次移至左侧并将其插入。

第三步

现在插入60。
由于60> 45，因此我们在右侧插入。

第四步

同样，您可以插入元素40、50和70以获取最终的BST。

例1

插入算法如下：

• 从树的根节点开始。
  如果它不存在，只需将新节点作为根节点并返回它即可！

• 否则，我们必须比较要插入的节点的密钥和根的密钥。

• 如果节点的键小于根，则需要将其插入到左子树中

• 否则，在其右子树中插入。

我们的方法具有以下特征：

TreeNode* insert_bst(TreeNode* root, int data);

这将指针指向根节点，并将"数据"插入其中。

如果根节点为" NULL"(不存在)，我们只需使用" data"创建一个新节点，并将其分配为新的根节点。

TreeNode* insert_bst(TreeNode* root, int data) {
  //Inserts data into it's appropriate position
  //in the BST
  if (!root) {
      //Make the root node
      root = make_treenode(data);
      return root;
  }
  else {
      //TODO: Insert to the existing root
      return root;
  }
}

现在，如果需要将其插入到现有节点中，请继续到" else"部分。
我们只需遵循上述算法，并对叶节点基本情况进行另外检查。

代码中的注释应该是不言自明的。
如果data<root-> data，我们在左边的子树中插入；如果data>root-> data，我们在右边的子树中。

TreeNode* insert_bst(TreeNode* root, int data) {
  //Inserts data into it's appropriate position
  //in the BST
  if (!root) {
      //Make the root node
      root = make_treenode(data);
      return root;
  }
  else {
      //We need to insert to the existing root
      TreeNode* node = make_treenode(data);
      TreeNode* temp = root;
      while (temp) {
          if (temp->is_leaf) {
              //Inserting at a leaf node
              if (temp->data > data) {
                  //Insert to the left
                  temp->left = node;
                  temp->is_leaf = 0;
                  break;
              }
              else {
                  //Insert to the right
                  temp->right = node;
                  temp->is_leaf = 0;
                  break;
              }
          }
          else {
              //Non leaf node
              if (temp->data > data) {
                  //Go to the left subtree
                  if (temp->left == NULL) {
                      //If the left subtree is empty, add it here
                      //and break, since we've finished insertion
                      temp->left = node;
                      break;
                  }
                  temp = temp->left;
              }
              else {
                  //Go to the right subtree
                  if (temp->right == NULL) {
                      //If the left subtree is empty, add it here
                      //and break, since we've finished insertion
                      temp->right = node;
                      break;
                  }
                  temp = temp->right;
              }
          }
      }
  }
  return root;
}

现在，我们已经完成了插入过程！现在，让我们快速完成" search_bst()"函数。

搜索二叉搜索树

这非常简单。
我们仅根据键比较移至左/右子树。
如果到达" NULL"节点，或者当前根节点密钥与我们的目标匹配，我们将停止。

int search_bst(TreeNode* root, int target) {
  //Searches for target in the BST
  if (!root)
      return 0;
  if (root->data == target)
      return 1;
  else if (root->data > target)
      return search_bst(root->left, target);
  else
      return search_bst(root->right, target);
  return 0;
}

现在，我们已经实现了插入和搜索，现在让我们测试一下程序是否正常运行。

到目前为止，我将发布完整的代码，并提供用于按顺序遍历BST的其他功能。

/**
  Code for https://theitroad.local article
  Purpose: A Binary Search Tree Implementation
  @author: Vijay Ramachandran
  @date: 08-03-2017
*/

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

typedef struct TreeNode {
  //TreeNode structure for the Binary Search Tree (BST)
  //A BST has the left subtree being less than the root,
  //while the right subtree is greater than the root
  int data; //A Node contains data
  struct TreeNode* left, *right; //As well as pointers to the left and right children
  int is_leaf; //Check whether a node is a leaf node or not
}TreeNode;

TreeNode* make_treenode(int data) {
  //Construct a treenode pointer using data
  TreeNode* node = (TreeNode*) calloc (1, sizeof(TreeNode));
  node->data = data;
  node->left = node->right = NULL;
  node->is_leaf = 1;
  return node;
}

TreeNode* insert_bst(TreeNode* root, int data) {
  //Inserts data into it's appropriate position
  //in the BST
  if (!root) {
      //Make the root node
      root = make_treenode(data);
      return root;
  }
  else {
      //We need to insert to the existing root
      TreeNode* node = make_treenode(data);
      TreeNode* temp = root;
      while (temp) {
          if (temp->is_leaf) {
              //Inserting at a leaf node
              if (temp->data > data) {
                  //Insert to the left
                  temp->left = node;
                  temp->is_leaf = 0;
                  break;
              }
              else {
                  //Insert to the right
                  temp->right = node;
                  temp->is_leaf = 0;
                  break;
              }
          }
          else {
              //Non leaf node
              if (temp->data > data) {
                  //Go to the left subtree
                  if (temp->left == NULL) {
                      //If the left subtree is empty, add it here
                      //and break, since we've finished insertion
                      temp->left = node;
                      break;
                  }
                  temp = temp->left;
              }
              else {
                  //Go to the right subtree
                  if (temp->right == NULL) {
                      //If the left subtree is empty, add it here
                      //and break, since we've finished insertion
                      temp->right = node;
                      break;
                  }
                  temp = temp->right;
              }
          }
      }
  }
  return root;
}

int search_bst(TreeNode* root, int target) {
  //Searches for target in the BST
  if (!root)
      return 0;
  if (root->data == target)
      return 1;
  else if (root->data > target)
      return search_bst(root->left, target);
  else
      return search_bst(root->right, target);
  return 0;
}

void free_bst(TreeNode* root) {
  //Frees the complete BST from memory
  if (!root)
      return;
  free_bst(root->left);
  free_bst(root->right);
  free(root);
}

void print_search(TreeNode* root, int target) {
  if (search_bst(root, target) == 1) {
      printf("Value: %d found in the BST!\n", target);
  }
  else {
      printf("Value: %d is not found in the BST.\n", target);
  }
}

void print_bst(TreeNode* root) {
  //Prints the BST in an inorder traversal
  if (!root)
      return;
  print_bst(root->left);
  printf("Node: %d -> ", root->data);
  print_bst(root->right);
}

int main() {
  //Driver function for performing Binary Search Tree
  //operations
  TreeNode* root = make_treenode(45);
  root = insert_bst(root, 20);
  root = insert_bst(root, 15);
  root = insert_bst(root, 60);
  root = insert_bst(root, 40);
  root = insert_bst(root, 50);
  root = insert_bst(root, 70);
  print_bst(root);
  printf("\n");
  print_search(root, 15);
  print_search(root, 70);
  print_search(root, 35);
  free_bst(root);
  return 0;
}

输出

Node: 15 -> Node: 20 -> Node: 40 -> Node: 45 -> Node: 50 -> Node: 60 -> Node: 70 -> 
Value: 15 found in the BST!
Value: 70 found in the BST!
Value: 35 is not found in the BST.

好的！这似乎按预期工作，并且我们按顺序遍历得到了元素的排序列表。

现在，让我们进入delete方法。

从二叉搜索树中删除

与其余的相比，这有点棘手。
由于迭代版本不太直观，因此我们将为此提供一种递归算法。

我们有多种情况需要删除。
以下算法是从BST中删除的最常用版本。

• 如果节点没有子节点，只需将其从树中删除。

• 否则，它有一个子节点，删除该节点并替换为其子节点。
  不管是左孩子还是右孩子。

• 如果它有2个孩子，这种情况比较棘手。
  其中我们不删除该节点。
  相反，我们将密钥复制到当前节点后，找到该节点的有序后继节点，并删除该节点。

节点的有序后继是在有序遍历之后的下一个节点。

例如，根节点(45)的有序后继者是节点50，因为它是大于它的下一个节点。

由于它是排序顺序中的下一个节点，因此它是该节点的右子树中的最左节点！

TreeNode* get_inorder_successor(TreeNode* node) {
  //Returns the inorder successor of the current node
  //But this is simply the leftmost node in the right subtree!
  //Assume that the right subtree of node exists
  TreeNode* temp = node->right;
  while(temp->left) {
      temp = temp->left;
  }
  return temp;
}

假定存在正确的子树，此方法将返回树中节点的有序后继。

现在，我们可以使用上述算法编写delete_bst()方法。
代码如下所示。

TreeNode* delete_bst(TreeNode* root, int target) {
  //Deletes the node corresponding to target, from the BST
  if (!root)
      return root;
  else {
      TreeNode* temp = root;
      if (temp->data > target) {
          //Search in the left subtree and delete there
          root->left = delete_bst(root->left, target);
      }
      else if (temp->data < target) {
          //Search in the right subtree and delete there
          root->right = delete_bst(root->right, target);
      }
      else {
          //We've found the node
          if (temp->left == NULL) {
              //No problem, as the left subtree is NULL
              //Update the node to it's right subtree
              //Even if it does not exist, it is the same!
              //We simply need to free the temp node
              TreeNode* del_node = temp;
              temp = temp->right;
              del_node->right = NULL;
              free(del_node);
              return temp;
          }
          else if (temp->right == NULL) {
              //If the right subtree is NULL, take the same
              //logic for the previous case
              TreeNode* del_node = temp;
              temp = temp->left;
              del_node->left = NULL;
              free(del_node);
              return temp;
          }
          else {
              //This node has two children. We need to find the inorder
              //successor and copy the data to the current node.
              TreeNode* inorder_successor = get_inorder_successor(temp);
              temp->data = inorder_successor->data;
              //Remove the inorder_successor node, since we've copied it's data
              //to the current node
              root->right = delete_bst(root->right, inorder_successor->data);
          }
      }
      return root;
  }
}

我们还实现了delete_bst()方法！因此，我现在将下面的完整代码发布。

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

typedef struct TreeNode {
  //TreeNode structure for the Binary Search Tree (BST)
  //A BST has the left subtree being less than the root,
  //while the right subtree is greater than the root
  int data; //A Node contains data
  struct TreeNode* left, *right; //As well as pointers to the left and right children
  int is_leaf; //Check whether a node is a leaf node or not
}TreeNode;

TreeNode* make_treenode(int data) {
  //Construct a treenode pointer using data
  TreeNode* node = (TreeNode*) calloc (1, sizeof(TreeNode));
  node->data = data;
  node->left = node->right = NULL;
  node->is_leaf = 1;
  return node;
}

TreeNode* insert_bst(TreeNode* root, int data) {
  //Inserts data into it's appropriate position
  //in the BST
  if (!root) {
      //Make the root node
      root = make_treenode(data);
      return root;
  }
  else {
      //We need to insert to the existing root
      TreeNode* node = make_treenode(data);
      TreeNode* temp = root;
      while (temp) {
          if (temp->is_leaf) {
              //Inserting at a leaf node
              if (temp->data > data) {
                  //Insert to the left
                  temp->left = node;
                  temp->is_leaf = 0;
                  break;
              }
              else {
                  //Insert to the right
                  temp->right = node;
                  temp->is_leaf = 0;
                  break;
              }
          }
          else {
              //Non leaf node
              if (temp->data > data) {
                  //Go to the left subtree
                  if (temp->left == NULL) {
                      //If the left subtree is empty, add it here
                      //and break, since we've finished insertion
                      temp->left = node;
                      break;
                  }
                  temp = temp->left;
              }
              else {
                  //Go to the right subtree
                  if (temp->right == NULL) {
                      //If the left subtree is empty, add it here
                      //and break, since we've finished insertion
                      temp->right = node;
                      break;
                  }
                  temp = temp->right;
              }
          }
      }
  }
  return root;
}

int search_bst(TreeNode* root, int target) {
  //Searches for target in the BST
  if (!root)
      return 0;
  if (root->data == target)
      return 1;
  else if (root->data > target)
      return search_bst(root->left, target);
  else
      return search_bst(root->right, target);
  return 0;
}

TreeNode* get_inorder_successor(TreeNode* node) {
  //Returns the inorder successor of the current node
  //But this is simply the leftmost node in the right subtree!
  //Assume that the right subtree of node exists
  TreeNode* temp = node->right;
  while(temp->left) {
      temp = temp->left;
  }
  return temp;
}

TreeNode* delete_bst(TreeNode* root, int target) {
  //Deletes the node corresponding to target, from the BST
  if (!root)
      return root;
  else {
      TreeNode* temp = root;
      if (temp->data > target) {
          //Search in the left subtree and delete there
          root->left = delete_bst(root->left, target);
      }
      else if (temp->data < target) {
          //Search in the right subtree and delete there
          root->right = delete_bst(root->right, target);
      }
      else {
          //We've found the node
          if (temp->left == NULL) {
              //No problem, as the left subtree is NULL
              //Update the node to it's right subtree
              //Even if it does not exist, it is the same!
              //We simply need to free the temp node
              TreeNode* del_node = temp;
              temp = temp->right;
              del_node->right = NULL;
              free(del_node);
              return temp;
          }
          else if (temp->right == NULL) {
              //If the right subtree is NULL, take the same
              //logic for the previous case
              TreeNode* del_node = temp;
              temp = temp->left;
              del_node->left = NULL;
              free(del_node);
              return temp;
          }
          else {
              //This node has two children. We need to find the inorder
              //successor and copy the data to the current node.
              TreeNode* inorder_successor = get_inorder_successor(temp);
              temp->data = inorder_successor->data;
              //Remove the inorder_successor node, since we've copied it's data
              //to the current node
              root->right = delete_bst(root->right, inorder_successor->data);
          }
      }
      return root;
  }
}

void free_bst(TreeNode* root) {
  //Frees the complete BST from memory
  if (!root)
      return;
  free_bst(root->left);
  free_bst(root->right);
  free(root);
}

void print_search(TreeNode* root, int target) {
  if (search_bst(root, target) == 1) {
      printf("Value: %d found in the BST!\n", target);
  }
  else {
      printf("Value: %d is not found in the BST.\n", target);
  }
}

void print_bst(TreeNode* root) {
  //Prints the BST in an inorder traversal
  if (!root)
      return;
  print_bst(root->left);
  printf("Node: %d -> ", root->data);
  print_bst(root->right);
}

int main() {
  //Driver function for performing Binary Search Tree
  //operations
  TreeNode* root = make_treenode(45);
  root = insert_bst(root, 20);
  root = insert_bst(root, 15);
  root = insert_bst(root, 60);
  root = insert_bst(root, 40);
  root = insert_bst(root, 50);
  root = insert_bst(root, 70);
  print_bst(root);
  printf("\n");
  print_search(root, 15);
  print_search(root, 70);
  print_search(root, 35);
  root = delete_bst(root, 50);
  printf("Deleted 50 from the BST\n");
  print_bst(root);
  printf("\n");
  root = delete_bst(root, 45);
  printf("Deleted 45 from the BST\n");
  print_bst(root);
  printf("\n");
  free_bst(root);
  return 0;
}

输出

Node: 15 -> Node: 20 -> Node: 40 -> Node: 45 -> Node: 50 -> Node: 60 -> Node: 70 -> 
Value: 15 found in the BST!
Value: 70 found in the BST!
Value: 35 is not found in the BST.
Deleted 50 from the BST
Node: 15 -> Node: 20 -> Node: 40 -> Node: 45 -> Node: 60 -> Node: 70 -> 
Deleted 45 from the BST
Node: 15 -> Node: 20 -> Node: 40 -> Node: 60 -> Node: 70 -> 

万岁！在删除50和45之后，这似乎按预期工作。
我们终于完成了所有程序，我们完成了！

实施的时间复杂度

下表列出了主要程序的时间复杂度

使用BST的缺点

BST的问题在于，由于插入可以任意发生，因此树可能会倾斜，BST的高度可能与元素数量成正比！

因此，现在，在绝对最坏的情况下，插入，搜索和删除操作等效于O(n)，而不是预期的O(logn)

为了避免这个问题，提出了对BST模型的一些修改，并且将一种流行的数据结构称为AVL树。
我们将在下一篇文章中为您提供更多详细信息，请继续关注！