小编给大家分享一下如何实现二叉查找树，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
二叉查找树又叫二叉排序树，其特点有：
对于每一棵子树，若左子树不为NULL，则左子树所有节点都小于它的根结点值。
对于每一棵子树，若右子树不为NULL，则左子树所有节点都大于它的根结点值。
没有键值相等的结点。
完成二叉查找树的基本操作有：
插入结点。
查找结点。
查找最小关键字：根据二叉查找树的特点，应该是最左边的结点
查找最大关键字：根据二叉查找树的特点，应该是最右边的结点
删除结点。
以上操作中，难点在与插入和删除。分别说下其主要思想：
插入：根据插入数据与结点的比较，找寻它的插入位置，若比结点值大，则往结点的右子树继续寻找，直到其右孩子为空，将新结点作为其右孩子；若比结点值小，则往结点的左子树继续寻找，直到其左孩子为空，将新结点作为其左孩子。
删除：设要查找的结点为d
若d有左子树，则用d的左孩子取代它，找到其左子树的最右边的结点r，把f的右孩子作为r的右子树。
若d无左子树，则直接用它的右孩子取代它。
但执行删除操作时要注意要删除的结点是否是几个特殊的结点：空结点、根结点、叶子节点。
代码示例：
//插入结点
//查找元素
//查找最小关键字
//查找最大关键字
//删除节点
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node* lchild;
struct Node* rchild;
struct Node* parent;
}Node;
//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针
void insert_node(Node** root,int _data)
{
Node* newnode=(Node*)malloc(1*sizeof(Node));
newnode->data=_data;
newnode->lchild=NULL;
newnode->rchild=NULL;
newnode->parent=NULL;
if(*root==NULL)
{
*root=newnode;
return ;
}
if((*root)->lchild==NULL && _data < (*root)->data)
{
(*root)->lchild=newnode;
newnode->parent=*root;
return ;
}
if((*root)->rchild==NULL && _data > (*root)->data)
{
(*root)->rchild=newnode;
newnode->parent=*root;
return ;
}
if( _data < (*root)->data )
{
insert_node(&(*root)->lchild,_data);
}
else
{
if( _data > (*root)->data)
{
insert_node(&(*root)->rchild,_data);
}
else
{
return ;
}
}
}
//输出节点元素
void print_tree(Node* root)
{
if(root==NULL)
return ;
printf("%d\t",root->data);
print_tree(root->lchild);
print_tree(root->rchild);
}
//查找元素,找到返回关键字的结点指针，没找到返回NULL
Node* find_node(Node* root,int _data)
{
if(root==NULL || ( _data == root->data))
{
return root;
}
if( _data < root->data )
{
return find_node(root->lchild,_data);
}
if(_data > root->data)
{
return find_node(root->rchild,_data);
}
}
//查找最小关键字,空树时返回NULL
Node* search_min(Node* root)
{
if(root==NULL)
{
return NULL;
}
if(root->lchild==NULL)
{
return root;
}
search_min(root->lchild);
}
//查找最大关键字
Node* search_max(Node* root)
{
if(root==NULL)
{
return NULL;
}
if(root->rchild==NULL)
{
return root;
}
search_max(root->rchild);
}
//根据关键字删除某个结点,删除成功返回1,否则返回0 如果把根结点删掉，那么要改变根结点的地址，所以传二级指针
/*思想： 1。若p有左子树，p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r的右子树。
2。若p没有左子树，直接用p的右孩子取代它。
*/
void delete_node(Node** root,int _data)
{
if(root==NULL)
return ;
Node* dnode=find_node(*root,_data);
if(dnode==NULL)
{
return ;
}
if(dnode->lchild==NULL && dnode->rchild==NULL && dnode!=*root)
{
if(dnode->parent->lchild==dnode)
{
dnode->parent->lchild=NULL;
}
if(dnode->parent->rchild==dnode)
{
dnode->parent->rchild=NULL;
}
free(dnode);
dnode=NULL;
return ;
}
//如没有左子树
if(dnode->lchild==NULL)
{
//若这个节点是根节点
if(dnode==*root)
{
*root=(*root)->rchild;
(*root)->parent=NULL;
free(dnode);
return ;
}
//若这个节点是父节点的左孩子
if(dnode->parent->lchild==dnode)
{
dnode->parent->lchild=dnode->rchild;
dnode->rchild->parent=dnode->parent;
free(dnode);
return ;
}
//若这个节点是父节点的右孩子
if(dnode->parent->rchild==dnode)
{
dnode->parent->rchild=dnode->rchild;
dnode->rchild->parent=dnode->parent;
free(dnode);
return ;
}
}
if(dnode->lchild!=NULL)
{
//找到其左子树的最右边的叶子结点r，把p的右子树作为r的右子树。
Node* r=dnode->lchild;
while(r->rchild!=NULL)
{
r=r->rchild;
}
r->rchild=dnode->rchild;
dnode->rchild->parent=r->rchild;
//用dnode的左节点来取代ta
if(dnode==*root)
{
*root=dnode->lchild;
(*root)->parent=NULL;
}
else
{
if(dnode->parent->lchild==dnode)
{
dnode->parent->lchild=dnode->lchild;
dnode->lchild->parent=dnode->parent;
}
if(dnode->parent->rchild==dnode)
{
dnode->parent->rchild=dnode->lchild;
dnode->lchild->parent=dnode->parent;
}
}
free(dnode);
dnode=NULL;
}
}
int main(int argc, char const *argv[])
{
Node* root=NULL;
insert_node(&root,15);
insert_node(&root,6);
insert_node(&root,18);
insert_node(&root,3);
insert_node(&root,7);
insert_node(&root,17);
insert_node(&root,20);
print_tree(root);
printf("\n");
Node* f=find_node(root,6);
if(f!=NULL)
{
printf("%d\n",f->parent->data);
}
delete_node(&root,3);
print_tree(root);
printf("\n");
return 0;
}以上是“如何实现二叉查找树”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
