分析二叉排序树的定义:根节点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; //把根节点返回去
}