数据结构 |
您所在的位置:网站首页 › 二叉排序树怎样得到递增序列 › 数据结构 |
二叉排序树概念
二叉排序树是动态查找表的一种,也是常用的表示方法。 其中,它具有如下性质: 1.若它的左子树非空,则其左子树的所有节点的关键值都小于根节点的关键值。 2.若它的右子树非空,则其右子树的所有节点的关键值都大于根结点的关键值。 3.它的左右子树也分别都是二叉排序树。 PS:对二叉排序树进行中序遍历,得到的序列,总会是一个升序的数列。 二叉排序树的建立我们使用C语言来建立。 其中我们对二叉排序树的结构体定义如下: typedef int ElemType; typedef struct BTNode{ ElemType key; struct BTNode *lchild,*rchild; }BTNode,*BSTree; 建立二叉排序树的代码如下: BSTree InsertBST(BSTree bst,BSTree s) //遍历二叉排序树,找到合适的位置 { if(bst==NULL) bst = s; else{ if(s->key < bst->key) bst->lchild = InsertBST(bst->lchild,s); if(s->key > bst->key){ bst->rchild = InsertBST(bst->rchild,s); } } return bst; } BSTree CreateBST() //建立二叉排序树 { BSTree bst,s; int key; bst = NULL; printf("请输入关键字值,输入-1结束.\n"); while(1){ scanf("%d",&key); if(key!=-1){ s = (BSTree)malloc(sizeof(BTNode)); s->key = key; s->lchild = NULL; s->rchild = NULL; bst = InsertBST(bst,s); printf("成功.\n"); } else break; } return bst; } 二叉排序树的插入 BSTree InsertBST(BSTree bst,BSTree s) //遍历二叉排序树,找到合适的位置 { if(bst==NULL) bst = s; else{ if(s->key < bst->key) bst->lchild = InsertBST(bst->lchild,s); if(s->key > bst->key){ bst->rchild = InsertBST(bst->rchild,s); } } return bst; } BSTree SearchBST(BSTree bst,int key) //查找关键值key的节点,并且返回这个节点 { if(bst == NULL) return NULL; else if(key == bst->key) return bst; else if(key > bst->key) return SearchBST(bst->rchild,key); else return SearchBST(bst->lchild,key); } BSTree InsertBST_key(BSTree bst,int key) //搜寻一个关键值,如果没有就插入 { BSTree s; s = SearchBST(bst,key); if(s) printf("该节点已经存在."); else{ s = (BSTree)malloc(sizeof(BTNode)); s->key = key; s->lchild = NULL; s->rchild = NULL; s = InsertBST(bst,s); } return s; } 查找二叉排序树指定节点的双亲 BSTree SearchBST_F(BSTree bst,int key,BSTree *F) //F存储key关键值节点的双亲节点,函数返回key关键值节点. { if(bst == NULL) return NULL; if(key == bst->key) return bst; else{ *F = bst; if(key < bst->key) return SearchBST_F(bst->lchild,key,F); else return SearchBST_F(bst->rchild,key,F); } } 删除二叉排序树中某个节点:对于删除二叉排序树的节点,我们有必要花大功夫来讨论一下。 对于删除二叉排序树的某个节点,大致有以下四种情况: 假设我们要删除的节点指定为P。 1.P节点的左右子树都为空此时删除P节点,只需要P节点的父节点的左/右子树赋值NULL,并且free掉P节点即可。 值得注意的是,还有一种特殊情况,那就是P节点本身就是根节点,也就是这个树只有P节点一个 节点。 那么此时,我们只需要返回NULL,并且free掉P节点即可。 在这种情况下,我们注意到P的右子树不是空的,如下图所示: 此时我们只需要令P节点的父节点C的右子树/左子树为P的右子树即可。 不过值得注意的是,此时仍有可能P是根节点,此时我们需要令根节点 = p的右子树,并且free掉p 节点即可。 此时我们注意到,这种情况根情况2(P节点的左子树为空)非常相似。 此时我们只需要令P的父节点C的左/右子树等于P的左子树即可。 不过此时P节点仍有可能作为根节点出现,此时我们只需要令根节点等于P的左子树即可。 这种情况无疑是最复杂的一种情况,因为此时我们要牵扯一个大小的排序。 因此,我们可以令P节点的Key值等于P节点的直接前驱(直接后驱)的Key值,之后删掉直接前驱(直 接后驱)即可。 注意到此时的P节点的直接前驱是G(即P节点的左子树的最右侧的一个节点)。 那么此时我们可以令P节点的Key值等于G节点的Key值,同时free掉G节点即可完成操作。 不过,比较重要的一点是,G节点的左子树不一定为空,此时我们仍需要让G节点的父节点的右子 树等于G节点的左子树。 注意到,当P节点作为根结点的时候并不会出现特殊的情况,但是当P节点的前驱节点就是P的左子 树,我们需要另外的讨论,如下图所示: 注意到此时P的直接前驱节点就是D,但是如果我们直接删除D,那么D的左子树此时应该给P的左 子树。 注意到P也是D的一个父节点,P同时还是D的一个直接后继节点,此时就是一种特殊情况,需要让 P的左子树等于D的左子树,而不是D的父节点的右子树等于D的左子树!!! 代码实现: BSTree SearchBST_F(BSTree bst,int key,BSTree *F) //查找Key值节点的父节点,*F存储父节点,函数返回Key节点 { if(bst == NULL) return NULL; if(bst->key == key) return bst; else{ *F = bst; if(bst->key > key) return SearchBST_F(bst->lchild,key,F); else return SearchBST_F(bst->rchild,key,F); } } BSTree DeleteBST(BSTree bst,BSTree p,BSTree f) { BSTree par,s; int kind; if(!p->lchild && !p->rchild) //左右子树全为空 kind = 1; else if(!p->lchild) //左子树为空 kind = 2; else if(!p->rchild) //右子树为空 kind = 3; else //左右子树都不为空 kind = 4; switch(kind){ case 1: if(!f) //没有父节点,p是根节点, return NULL; else{ if(f->lchild == p) f->lchild = NULL; else f->rchild = NULL; free(p); } break; case 2: if(!f) //p是根节点 bst = bst->rchild; else{ if(p == f->lchild) f->lchild = p->rchild; else f->rchild = p->rchild; free(p); } break; case 3: if(!f) //p是根节点 bst = bst->lchild; else{ if(p == f->lchild) f->lchild = bst->lchild; else f->rchild = bst->lchild; } free(p); break; case 4: par = p; //p节点前驱指针par s = p->lchild; //用来遍历p的直接前驱节点(左子树的最右侧) while(s->rchild != NULL){ //结束条件是s的右子树为空,此时s就是p的直接前驱节点 par = s; s = s->rchild; } p->key = s->key; //令p节点的值为s节点的值 if(par == p) //特殊情况,s节点刚好是p的左子树 par->lchild = s->lchild; else par->rchild = s->lchild; //par的右子树需要等于s节点的左子树 free(s); //释放p节点的直接前驱s break; } return bst; } BSTree SearchDeleteBST(BSTree bst,int key) { BSTree f = NULL,p; p = SearchBST_F(bst,key,&f); if(p){ bst = DeleteBST(bst,p,f); } else printf("该节点不存在.\n"); return bst; } 二叉排序树的所有代码汇总: #include #include typedef int ElemType; typedef struct BSNode{ ElemType key; struct BSNode *lchild,*rchild; }BSNode,*BSTree; BSTree SearchBST(BSTree bst,BSTree s) { if(bst == NULL) bst = s; else{ if(bst->key > s->key) bst->lchild = SearchBST(bst->lchild,s); if(bst->key < s->key) bst->rchild = SearchBST(bst->rchild,s); } return bst; } BSTree CreateBSTree() { int key; BSTree bst = NULL; printf("请输入节点关键值,输入-1结束.\n"); while(1){ scanf("%d",&key); if(key != -1){ BSTree s = (BSTree)malloc(sizeof(BSNode)); s->key = key; s->lchild = NULL; s->rchild = NULL; bst = SearchBST(bst,s); printf("创建节点成功.\n"); } else break; } return bst; } void PostTraverse(BSTree bst) { if(bst){ PostTraverse(bst->lchild); printf("%d ",bst->key); PostTraverse(bst->rchild); } } BSTree SearchBST_F(BSTree bst,int key,BSTree *F) //查找Key值节点的父节点,*F存储父节点,函数返回Key节点 { if(bst == NULL) return NULL; if(bst->key == key) return bst; else{ *F = bst; if(bst->key > key) return SearchBST_F(bst->lchild,key,F); else return SearchBST_F(bst->rchild,key,F); } } BSTree DeleteBST(BSTree bst,BSTree p,BSTree f) { BSTree par,s; int kind; if(!p->lchild && !p->rchild) //左右子树全为空 kind = 1; else if(!p->lchild) //左子树为空 kind = 2; else if(!p->rchild) //右子树为空 kind = 3; else //左右子树都不为空 kind = 4; switch(kind){ case 1: if(!f) //没有父节点,p是根节点, return NULL; else{ if(f->lchild == p) f->lchild = NULL; else f->rchild = NULL; free(p); } break; case 2: if(!f) //p是根节点 bst = bst->rchild; else{ if(p == f->lchild) f->lchild = p->rchild; else f->rchild = p->rchild; free(p); } break; case 3: if(!f) //p是根节点 bst = bst->lchild; else{ if(p == f->lchild) f->lchild = bst->lchild; else f->rchild = bst->lchild; } free(p); break; case 4: par = p; //p节点前驱指针par s = p->lchild; //用来遍历p的直接前驱节点(左子树的最右侧) while(s->rchild != NULL){ //结束条件是s的右子树为空,此时s就是p的直接前驱节点 par = s; s = s->rchild; } p->key = s->key; //令p节点的值为s节点的值 if(par == p) //特殊情况,s节点刚好是p的左子树 par->lchild = s->lchild; else par->rchild = s->lchild; //par的右子树需要等于s节点的左子树 free(s); //释放p节点的直接前驱s break; } return bst; } BSTree SearchDeleteBST(BSTree bst,int key) { BSTree f = NULL,p; p = SearchBST_F(bst,key,&f); if(p){ bst = DeleteBST(bst,p,f); } else printf("该节点不存在.\n"); return bst; } int main() { BSTree bst; bst = CreateBSTree(); SearchDeleteBST(bst,5); PostTraverse(bst); return 0; } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |