如何实现二叉查找树

小编给大家分享一下如何实现二叉查找树，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

        二叉查找树又叫二叉排序树，其特点有：

1. 对于每一棵子树，若左子树不为NULL，则左子树所有节点都小于它的根结点值。
   

2. 对于每一棵子树，若右子树不为NULL，则左子树所有节点都大于它的根结点值。

3. 没有键值相等的结点。

完成二叉查找树的基本操作有：

1. 插入结点。
   

2. 查找结点。

3. 查找最小关键字：根据二叉查找树的特点，应该是最左边的结点

4. 查找最大关键字：根据二叉查找树的特点，应该是最右边的结点

5. 删除结点。

以上操作中，难点在与插入和删除。分别说下其主要思想：

插入：根据插入数据与结点的比较，找寻它的插入位置，若比结点值大，则往结点的右子树继续寻找，直到其右孩子为空，将新结点作为其右孩子；若比结点值小，则往结点的左子树继续寻找，直到其左孩子为空，将新结点作为其左孩子。

删除：设要查找的结点为d

1. 若d有左子树，则用d的左孩子取代它，找到其左子树的最右边的结点r，把f的右孩子作为r的右子树。
   

2. 若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; }

以上是“如何实现二叉查找树”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！