树的查找-->二叉排序树的查找算法全解

浅浅的花香味﹌ 2022-06-05 03:56 128阅读 0赞

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

分析二叉排序树的定义：根节点25 的左右子树， 18左子树的全部节点大小是小于25的，右子树的全部节点是大于25的。  
同样46作为根节点的左右子树也是满足上述性质。

那么这样的二叉树就是二叉排序树。特别注意二叉排序树里面不存在2个相同的节点数据

那么二叉排序树查询元素的过程是什么样的呢，其实如果你们看过我写的二分查找的博客，你们会很清楚，每次查询都是将元素查询范围减少1半，其实是比较类似的。因此我们的二叉排序树查找过程，我们可以把链表形式的存储结构看成有序的顺序表存储结构。

![这里写图片描述][SouthEast 2]

二叉排序树查询过程分析：  
首先我们把根节点和需要查询的元素k给查询算法，查询算法先得到根节点元素和需要查询的元素比较，看看是不是想到的元素，找到话就返回当前节点的指针，

如果我们的待查询的元素k大于当前根节点里面的元素，那么根据二叉排序的性质，这个待查询节点的位置一定在当前根节点元素的右子树里面，不过查询之前先判断有没有右子树存在，如果没有的话，查询肯定就失败了那么就给你一个null.否则就接着干吧。

下面上针对二叉排序树查找关键字k的算法
    二叉排序树节点数据类型设置
    typedf strcut BSTNode 
    {
          int data;                       //节点数据元素     
          strcut BSTNode* lChild,rChild;  //左右孩子节点指针域
    }
    
    // BSTNode   节点数据类型  用递归算法
    BSTNode * SearchBST(BSTNode *bt, int key)
    {
            //由于我们得到了二叉排序树的根节点地址，和需要查询的元素key
           //开始可以直接比较是不是就是根节点元素
           if(!bt)
           {
                  //找到了
                if( bt->data == key) 
                {
                     return bt;
                }else if(bt->data > key)
                {
                      //没有找到我们就递归在左子树里找
                      return SearchBST(bt->lChild,key);    lChild是保存了当前节点的左孩子地址
                }else
                {
                 //没有找到我们就递归在右子树里找
                      return SearchBST(bt->rChild,key);    lChild是保存了当前节点的右孩子地址
                }
           }
    
        //但是一直递归没有出口咋可以呢，因此啥时候结束递归呢 ，当父函数给我的孩子节点地址是空的时候，
        //就直接退出没有必须巡查了
        //刚好代码跑到这里说明 bt == null 也就是没有孩子了
        return null;
    }

但是现实中，我们查询的数据一定在二叉树中吗，你看到了可能会返回null地址，也就是没有找到，那么我们该怎么办，二叉树里没有我们就不做处理了吗，并不是，我们是把这个元素插入二叉树中去，并且还是二叉排序树，我们知道二叉排序树是支持动态查找的，什么是动态查找呢，比如我们查的元素不在当前集合中，我们就插入进去，那么数组支持动态查询吗，肯定不行，数组内存是静态分配的，不能进行动态分配，那么二叉树是链表形式是支持动态分配内存的。

![这里写图片描述][SouthEast 3]

现在来谈假如我们查找的元素不在二叉树里面的情况，那么我们需要往空树里面插入节点。  
现在来实现插入算法 用递归实现

//插入节点到二叉排序树中  规则返回值1表示插入功能 0插入失败，说明当前元素已经存在
    //bt是二叉排序树的根节点指针  key是想插入的节点元素
    //BSTNode是我们设计的节点数据类型
    int InsertBST(BSTNode *bt, int key)
    {
          /*二叉排序树中不能重复插入相同元素*/
          //先判断是不是空树是的话直接造一个节点保存就可以
          if(bt == null)  
          {
                //空树  开始造节点数据
                bt = (BSTNode *)malloc(sizeof(BSTNode));
    
                if(bt == null) exit(0); //说明没有足够内存分配了，我们直接退出应用程序
                //分配成功了 开始写入数据到节点当中
                bt->data = key;
                bt->lChild = bt->rChild = null;
                //开始返回插入成功的标识数据
                return 1;
          }
          else  //不是空树
          {
                //开始测试当前根节点元素是不是就是我们想插入的元素呢
                if(bt->data == key)  //确实有相同元素
                {
                      //那么我们啥都不要干，但是要返回插入失败的标志
                      return 0;
                } 
                else if(bt->data > key) //插入节点比当前数据小  我们需要去当前节点左子树去找位置
                {
                      //开始递归 在左子树处开始继续寻找位置
                      return InsertBST(bt->lChild,key);
                }
                else
                {
                     //转右子树
                     return InsertBST(bt->rChild,key);
                }
          }
    }

实际情况，可能给我们的一组数，比如一个数组，有上面对单个数的插入算法，那么实现针对数组的生成二叉排序树是不是非常简单呢。是。下面贴代码

//实数组转二叉排序树的算法   array需要转二叉排序树的数组  n数组的元素个数
    //返回值是二叉树根节点地址，这样我们就可以通过返回值拿到二叉排序树
    BSTNode* CreateBST(int[] array,int n)
    {
          //准备二叉树节点数据指针 打算保存二叉排序树的根节点地址
          BSTNode* bt = null;
    
          //开始通过循环遍历数组中的元素开始一一插入二叉排序树中
          int i; //遍历数组索引用
          for(i = 0; i < n; i++)
          {
               //调用现成函数插入节点
               InsertBST(bt,array[i]); 
          }
    
          //循环完毕后说明插入完毕
          return bt;    //把根节点返回去
    }

[SouthEast]: /images/20220605/c60bb59ad69d4623afad25cf35bb2eff.png
[SouthEast 1]: /images/20220605/2cf8b0ef15c54470b5463334172a06be.png
[SouthEast 2]: /images/20220605/8555ecd71ed542a1ac2e52a979d51817.png
[SouthEast 3]: /images/20220605/5ab375ec41b94e4e8cfef46c6fcb9f6c.png