小编给大家分享一下如何实现二叉查找树,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
二叉查找树又叫二叉排序树,其特点有:
对于每一棵子树,若左子树不为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进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。