数据结构&算法 二叉搜索树

  • 二叉搜索树

    二叉搜索树(BST)是一棵树,其中所有节点都遵循以下提到的属性-
    • 节点的左子树的键小于或等于其父节点的键。
    • 节点的右子树的密钥大于其父节点的密钥。
    因此,BST将其所有子树分为两个部分:左子树和右子树,可以定义为-
    left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
  • 表示

    BST是以保持BST属性的方式排列的节点的集合。每个节点都有一个键和一个关联的值。在搜索时,将所需的密钥与BST中的密钥进行比较,如果找到,则会检索关联的值。以下是BST的图形表示-
    tree
    我们观察到,根节点键(27)在左子树上具有所有值较低的键,而在右子树上具有较高值的​​键。
  • 基本操作

    以下是树的基本操作-
    • 搜索 -搜索树中的元素。
    • 插入 -将元素插入树中。
    • 前序遍历 -以前序方式遍历树。
    • 中序遍历 -以中序方式遍历树。
    • 后序遍历 -以后序方式遍历树。
    节点
    定义一个包含一些数据的节点,并引用其左子节点和右子节点。
    
    struct node {
       int data;   
       struct node *leftChild;
       struct node *rightChild;
    };
    
  • 搜索操作

    每当要搜索元素时,都从根节点开始搜索。然后,如果数据小于键值,则在左侧子树中搜索元素。否则,在右子树中搜索该元素。每个节点遵循相同的算法。
    算法
    
    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;
    }
    
  • 插入操作

    每当要插入元素时,请先找到其正确位置。从根节点开始搜索,然后如果数据小于键值,则在左侧子树中搜索空位置并插入数据。否则,请在右侧子树中搜索空白位置并插入数据。
    
    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;
                }
             }
          }            
       }
    }        
    
    遍历示例:》》》》》》