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

时间:2022-10-07 12:05:00

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

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

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

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

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

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

二叉排序树查询过程分析:
首先我们把根节点和需要查询的元素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地址,也就是没有找到,那么我们该怎么办,二叉树里没有我们就不做处理了吗,并不是,我们是把这个元素插入二叉树中去,并且还是二叉排序树,我们知道二叉排序树是支持动态查找的,什么是动态查找呢,比如我们查的元素不在当前集合中,我们就插入进去,那么数组支持动态查询吗,肯定不行,数组内存是静态分配的,不能进行动态分配,那么二叉树是链表形式是支持动态分配内存的。

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

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

//插入节点到二叉排序树中 规则返回值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;    //把根节点返回去
}