1. WIKI教程
2. 数据结构和算法
3. DSA - 二进制搜索树(Binary Search Tree)

DSA - 二进制搜索树(Binary Search Tree)

二进制搜索树（BST）是一个树，其中所有节点都遵循下面提到的属性 -

• 节点的左子树具有小于或等于其父节点密钥的密钥。

• 节点的右子树的密钥大于其父节点的密钥。

因此，BST将其所有子树划分为两个部分; 左子树和右子树可以定义为 -

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

表示 Representation

BST是节点的集合，以维护BST属性的方式排列。 每个节点都有一个密钥和一个相关的值。 在搜索时，将所需的密钥与BST中的密钥进行比较，如果找到，则检索相关的值。

以下是BST的图示 -

我们观察到根节点密钥（27）在左子树上具有所有较低值的密钥，在右子树上具有较高值的​​密钥。

基本操作 (Basic Operations)

以下是树的基本操作 -

• Search - 搜索树中的元素。

• Insert - 在树中插入元素。

• Pre-order Traversal - 以预订方式遍历树。

• In-order Traversal - 以有序方式遍历树。

• Post-order Traversal - 以后序方式遍历树。

Node

定义具有一些数据的节点，对其左右子节点的引用。

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

搜索操作 (Search Operation)

每当要搜索元素时，从根节点开始搜索。 然后，如果数据小于键值，则在左子树中搜索元素。 否则，搜索右子树中的元素。 对每个节点遵循相同的算法。

算法 (Algorithm)

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
   while(current->data != data){
      if(current != NULL) {
         printf("%d ",current->data);
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   return current;
}

插入操作 (Insert Operation)

无论何时插入元素，首先要找到其正确的位置。 从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索空位置并插入数据。 否则，在右子树中搜索空位置并插入数据。

算法 (Algorithm)

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {                
         parent = current;
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}