树(Tree)——(三)搜索二叉树(BST)插入、查找
程序员文章站
2022-03-24 16:05:32
...
目录
之前用到的二叉树是基本不用的,只是具备了二叉树的样子。二叉树的作用是为了方便查找,所以我们需要构建一个搜索二叉树。
二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树。
二叉搜索树不同于一般的二叉树,它是一种特殊的二叉树,如果对这棵树进行中序遍历,你就会得到一个递增的队列。
搜索树的创建和插入(C++)
迭代版 (未用递归):
#include <iostream>
using namespace std;
struct TreeNode
{
int _data;
TreeNode* _left;
TreeNode*_right;
};
void insertBst(TreeNode**root,int data)
{
TreeNode*t =*root;
// TreeNode***chen =&root;
/* 这里是我多想了个方法,因为二级指针想要访问内部的必须用更上一级的指针,这里我用了三级指针,这里的chen可以代替下面根初始化的(*root),实际上用(*root)更加便于理解一点 */
if((**chen)==NULL) //若为根节点,则是树的最初初始化 ,或者改成 (*root) == NULL
{
(*root)=(TreeNode*)malloc(sizeof(TreeNode));
(*root)->_data = data;
(*root)->_left = (*root)->_right = NULL;
}
else
{
while(1) //这里就在遍历这个加入的数在哪一边,判断在每一层深度的左边还是右边
{
if(data > t->_data) //若要加入的数比原来的大
{
if(t->_right==NULL)
{
TreeNode* ch=(TreeNode*)malloc(sizeof(TreeNode)); //开辟一个树节点
ch->_data=data;
t->_right=ch;
ch->_left = ch->_right = NULL;
break;
}
else
t=t->_right;
}
else //比原来的小于或等于
{
if(t->_left==NULL)
{
TreeNode* ch=(TreeNode*)malloc(sizeof(TreeNode));
ch->_data=data;
t->_left=ch;
ch->_left = ch->_right = NULL;
break;
}
else
t=t->_left;
}
}
}
}
//中序遍历
void midOrderTraverse(TreeNode*r)
{
if(r)
{
midOrderTraverse(r->_left);
printf("%d ",r->_data);
midOrderTraverse(r->_right);
}
}
/* 例子
* 30
*
* 8 36
*
* 15 32 100
*/
int main()
{
TreeNode *root=NULL; //树的初始化
insertBst(&root,30); //利用例子建造树
insertBst(&root,8);
insertBst(&root,15);
insertBst(&root,36);
insertBst(&root,100);
insertBst(&root,32);
midOrderTraverse(root); //中序递归遍历
return 0;
}
递归版:
void insertBstRecusive(TreeNode ** root, int data)
{
if((*root) == NULL)
{
(*root) = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->_data = data;
(*root)->_left = (*root)->_right = NULL;
}
else if(data >(*root)->_data)
{
insertBstRecusive(&(*root)->_right,data);
}
else
{
insertBstRecusive(&(*root)->_left,data);
}
}
//这里其他的就不贴了,主要就是把这个放入上面迭代版,函数名改一下就可以运行。
BST的查找:
//遍历版(非递归)
TreeNode* searchBst(TreeNode*r ,int find)
{
while(r)
{
if(r->_data == find)
return r;
else if(find> r->_data)
r=r->_right;
else
r=r->_left;
}
return NULL;
}
//递归版
TreeNode* searchBstRecursive(TreeNode*r ,int find)
{
if(r)
{
if(r->_data == find)
return r;
else if(find > r->_data)
return searchBstRecursive(r->_right,find);
else
return searchBstRecursive(r->_left,find);
}
return NULL;
}
这个在main函数中函数调用,加入寻找的数就可以了。
BST寻找最大最小值:
//找最小数(肯定在最左边)
TreeNode* getMinNodeBst(TreeNode*r)
{
if(r)
{
while(r->_left)
{
r=r->_left;
}
return r;
}
return NULL;
}
//找最大数(肯定在最右边)
TreeNode* getMaxNodeBst(TreeNode*r)
{
if(r)
{
while(r->_right)
{
r=r->_right;
}
return r;
}
return NULL;
}
查找父节点:
//递归版 查
TreeNode* getParentBst(TreeNode * r,TreeNode * child)
{
static TreeNode * parent = NULL; //这里使用了静态变量,静态变量的话在函数中只存在一个
if(r)
{
if(r->_left == child || r->_right== child)
parent = r;
getParentBst(r->_left,child);
getParentBst(r->_right,child);
}
return parent;
}
//非递归版用队列就可以解决,若要看代码点击这里。