数据结构 ---- 搜索二叉树的基本操作(1)

时间:2022-01-24 17:31:57

关于搜索二叉树,我们先用递归版本完成,非递归版本请关注下一篇文章;

首先,什么是搜索二叉树?
定义:搜索二叉树是根结点的左子树的值比根结点小,右子树的值比根结点值大,所有子树都满足这个规则的就是搜索二叉树;
我们要完成关于搜索二叉树的如下操作:
search_tree.h

   #pragma once 
   #include <stddef.h>

   typedef char SearchNodeType;

   typedef struct SearchNode{
       SearchNodeType data;
       struct SearchNode* lchild;
       struct SearchNode* rchild;
  }SearchNode; 

  //有可能会对空树进行插入,从而就修改了root的指向
  //此处不能指定往那个位置插入,因为我们要保证不管怎么插,
  //树始终是一个二叉搜索树
  void SearchTreeInit(SearchNode** pRoot);

  void SearchTreeDestroy(SearchNode** pRoot);

  void SeachTreeInsert(SearchNode** root,SearchNodeType value);

 SearchNode* SearchTreeFind(SearchNode* root,SearchNodeType to_find);
  //按照值来进行删除
  void SearchTreeRemove(SearchNode** pRoot,SearchNodeType to_remove);

我们用孩子表示法,来表示树中的一个结点;

思路:

插入:我们要找到插入的位置,因为这里采用递归版本,所以整体思路为,当要插入的值比根结点的值小时,就递归的往左子树插,比根结点值大时,就递归的往右子树插,如果相等我们规定插入失败;

查找:与插入的思路相同,当要查找的值比根结点的值小就递归的找左子树,大就递归的找右子树,相等就找到了,返回结点指针即可;

删除:分两步,首先先找到要删除结点的位置,这步与上面的查找思路相同,找到之后,要分情况讨论:1).要删除的结点没有左右子树,直接将指向此结点的指针指向空,在销毁这个结点;2).要删除的结点有左子树,或者右子树,我们需要他们进行交付,进行管理不能删除完将左右子树丢失;3).要删除的结点有左右子树,我们要先找到要删除结点的右子树中的最小值,然后将要删除结点的值与最小值进行交换,然后在删掉最小值;
代码实现:

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

   void SearchTreeInit(SearchNode** pRoot){
       if(pRoot == NULL){
           //非法输入
           return;
       }
      *pRoot = NULL;
     return;
 }

  void DestroySearchNode(SearchNode* node){
     free(node);
  }
 void SearchTreeDestroy(SearchNode** pRoot){
     if(pRoot == NULL){
         //非法输入
          return;
      }
     if(*pRoot == NULL){
          //空树
          return;
     }
     //这里必须采用后续遍历进行销毁,这样才能找到根结点的左右子树
     SearchNode* root = *pRoot;
     SearchTreeDestroy(&root->lchild);
     SearchTreeDestroy(&root->rchild);
     DestroySearchNode(root);
     *pRoot = NULL;
     return;
  }

 SearchNode* CreateSearchNode(SearchNodeType value){
      SearchNode* new_node = (SearchNode*)malloc(sizeof(SearchNode));
     new_node->data = value;                                                                        
      new_node->lchild = NULL;
      new_node->rchild = NULL;
    return new_node;
  }

  #if 0
  void SeachTreeInsert(SearchNode** pRoot,SearchNodeType value){
      if(pRoot == NULL){
          //非法输入
          return;
      }
     if(*pRoot == NULL){
          //空树
        SearchNode* new_node = CreateSearchNode(value);
          *pRoot = new_node;
         return;
     }
      //对于这个树非空的情况 
      //采用递归的方式进行插入
     SearchNode* cur = *pRoot;
     if(value < cur->data){
         //递归的往左子树插入
         SeachTreeInsert(&cur->lchild,value);   
     }else if(value > cur->data){
        //递归的往右子树插入
        SeachTreeInsert(&cur->rchild,value);
     }else{
         //关于等于的处理有很多种,以下可以采用这么一种约束
         //我们约定这个二叉搜索树中,所有的元素不能重复
         //直接返回不做任何处理,插入失败
         return;
     }
 }

 SearchNode* SearchTreeFind(SearchNode* root,SearchNodeType to_find){
     if(root == NULL){
         //空树
         return NULL;
    }                                                                                              
    if(to_find < root->data){
        return SearchTreeFind(root->lchild,to_find);
     }else if(to_find > root->data){
         return SearchTreeFind(root->rchild,to_find);
     }else{
         return root;
    }
    return NULL;
 }
 void SearchTreeRemove(SearchNode** pRoot,SearchNodeType to_remove){
     if(pRoot == NULL){
         //非法输入
         return;
     }
     if(*pRoot == NULL){
         //空树
         return;
     }                                                                                              
     //1.找to_remove所在位置
     SearchNode* root = *pRoot;
     if(to_remove < root->data){
     }else if(to_remove > root->data){
         SearchTreeRemove(&root->rchild,to_remove);
     }else{
         //找到了
         SearchNode* to_remove_node = root;
        if(root->lchild == NULL && root->rchild == NULL){
             *pRoot = NULL;
             DestroySearchNode(to_remove_node);
             return;
         }else if(root->lchild != NULL && root->rchild == NULL){
             *pRoot = to_remove_node->lchild;
             DestroySearchNode(to_remove_node);
             return;
         }else if(root->lchild == NULL && root->rchild != NULL){
            *pRoot = to_remove_node->rchild;
             DestroySearchNode(to_remove_node);
            return;                                                                                
         }else{
             //要删除的元素有左右子树
             //需要先找到右子树中最小的节点 
             //把要删除节点的值和最小节点的值进行交换
             //从当前节点的右子树出发,尝试递归的删除刚刚被交换的值
             SearchNode* min = to_remove_node->rchild;
             while(min->lchild != NULL){
                 min = min->lchild;
             }
             //min已经指向了右子树中的最小值
             to_remove_node->data = min->data;
             //尝试递归删除min->data
             SearchTreeRemove(&to_remove_node->rchild,min->data);
             return;
         }
    }
    return;
 }