二叉排序树C完整实现代码
时间:2014-02-25 13:51作者:网络人气:7664
二叉排序树简介
二叉排序树(Binary Sort Tree,简称BST),又称二叉查找树,是红黑树、AVL树等的基础。它或是一棵空树,或者是具有下列性质的一棵二叉树:
1、若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
2、若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
3、它的左右子树也分别为二叉排序树。
下面的一棵树即为二叉排序树:
很明显,对二叉排序树进行中序遍历,便可得到一个有序序列,该有序序列中的各元素按照从小到大的顺序排列,因此一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。
二叉排序树相关操作
二叉排序树通常有查找、插入、删除等操作。查找操作很简单,无非就是递归查找,有点类似二叉树遍历的过程。插入操作也不难,一般是先在二叉排序树pTree中查找,看是否存在有等于给定值的元素,如果查找不到,则将给定值插入到该二叉排序树中,但是要保证插入后的树依然是二叉排序树。这样,新节点插入的位置便是唯一的,而且新插入的节点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子。正是由于其在查找过程中插入节点的特性,二叉排序树是一种动态树。
在给出各操作实现的具体代码前,要详细看下二叉排序树的删除操作,删除操作相比于二叉排序树的其他操作要难些,但也只是相对于其本身的其他操作而已,真正理解了也就很容易了。闲话少说,下面就来具体分析二叉排序树的删除操作。
我们假设在二叉排序树中要被删除的节点为p(即p指向的节点,下同),其父节点为f,当然节点p可能是节点f的的左孩子或右孩子,但在下面各种情况的分析中,你会发现,无论是左孩子还是右孩子,都不影响删除操作的通用性。很明显,删除操作要分为如下3种情况:
1、若待删节点p为叶子节点,则删除p后,并不会破坏整棵树的结构,因此只需令p=NULL即可。
2、若待删节点p只有左子树或右子树,则只需将左子树或右子树重接到p的父节点上即可,即执行如下操作:p=p->lchild或p=p->rchild。
3、若待删节点p既有左子树又有右子树,显然就不如上面两种情况那么简单了。我们要使节点p被删除后,二叉排序树的结构不变,就需要对它的子树做一些操作,而且只需操作一个子树即可,操作左子树和操作右子树的思路相似,我们这里以操作左子树为例来实现节点p的删除操作,并结合下图做具体分析(图中三角形代表节点的左子树或右子树)。
我们这里将图a展开为更详细的图b进行分析,则在删除节点p前,中序遍历该二叉排序树的结果为:...CL C...QL Q SL S P PR F ...,删除节点p后,我们要保持其他元素在该序列中的先后顺序不变,观察图b,我们可以采取如下两种做法:
1)将节点p的左子树直接接到其父节点f上,作为f的左子树,将节点p的右子树接到节点s上,作为s的右子树(这里s为p的前驱节点,即p在有序序列中紧接在s的前面),而后删除节点p。采用这种方法删除节点p后,得到的二叉排序树的形状如下图中的图c所示:
采取该方法删除节点的实现代码如下:
-
-
-
-
-
- void delete_Node1(BSTree &p)
- {
- BSTree q,s;
- if(!p->lchild)
- {
-
- q = p;
- p = p->rchild ;
- free(q);
- }
- else if(!p->rchild)
- {
- q = p;
- p = p->lchild;
- free(q);
- }
- else
- {
-
- s = p->lchild;
-
-
-
-
- while(s->rchild)
- s = s->rchild;
- s->rchild = p->rchild;
- q = p;
- p = p->lchild;
- free(q);
- }
- }
2)将节点s的右子树重接到其父节点上,作为其父节点的右子树,而后用s替换掉带删节点p。采取这种方法删除节点p后,得到的二叉排序树的形状如上图中的图d所示。采用该方法删除节点的实现代码如下:
-
-
-
-
-
- void delete_Node2(BSTree &p)
- {
- BSTree q,s;
- if(!p->lchild)
- {
-
- q = p;
- p = p->rchild ;
- free(q);
- }
- else if(!p->rchild)
- {
- q = p;
- p = p->lchild;
- free(q);
- }
- else
- {
-
- q = p;
- s = p->lchild;
- while(s->rchild)
- {
-
-
- q = s;
- s = s->rchild;
- }
-
- p->data = s->data;
-
- if(p != q)
- q->rchild = s->lchild;
- else
- q->lchild =s->lchild;
- free(s);
- }
- }
完整源码
上面重点分析了删除节点的思路和过程,下面给出二叉排序树各种操作实现的完整C代码(含测试代码并加有详细注释):
-
-
-
-
-
- #include<stdio.h>
- #include<stdlib.h>
-
- typedef struct Node
- {
- int data;
- struct Node *lchild;
- struct Node *rchild;
- }NODE,*BSTree;
-
-
-
-
-
-
- BSTree search(BSTree pTree,int key)
- {
- if(!pTree || pTree->data == key)
- return pTree;
- else if(key < pTree->data)
- return search(pTree->lchild,key);
- else
- return search(pTree->rchild,key);
- }
-
-
-
-
-
-
-
-
-
-
- bool search_BSTree(BSTree pTree,int key,BSTree parent,BSTree &p)
- {
- if(!pTree)
- {
- p = parent;
- return false;
- }
- else
- {
- if(key == pTree->data)
- {
- p = pTree;
- return true;
- }
- else if(key < pTree->data)
- return search_BSTree(pTree->lchild,key,pTree,p);
- else
- return search_BSTree(pTree->rchild,key,pTree,p);
- }
- }
-
-
-
-
-
-
- bool insert(BSTree &pTree,int key)
- {
- BSTree p;
- if(!search_BSTree(pTree,key,NULL,p))
- {
-
- BSTree pNew = (BSTree)malloc(sizeof(NODE));
- pNew->data = key;
- pNew->lchild = pNew->rchild = NULL;
-
- if(!p)
- pTree = pNew;
- else if(key < p->data)
- p->lchild = pNew;
- else
- p->rchild = pNew;
- }
- else
- return false;
- }
-
-
-
-
-
-
- void delete_Node1(BSTree &p)
- {
- BSTree q,s;
- if(!p->lchild)
- {
-
- q = p;
- p = p->rchild ;
- free(q);
- }
- else if(!p->rchild)
- {
- q = p;
- p = p->lchild;
- free(q);
- }
- else
- {
-
- s = p->lchild;
-
-
-
-
- while(s->rchild)
- s = s->rchild;
- s->rchild = p->rchild;
- q = p;
- p = p->lchild;
- free(q);
- }
- }
-
-
-
-
-
-
- void delete_Node2(BSTree &p)
- {
- BSTree q,s;
- if(!p->lchild)
- {
-
- q = p;
- p = p->rchild ;
- free(q);
- }
- else if(!p->rchild)
- {
- q = p;
- p = p->lchild;
- free(q);
- }
- else
- {
-
- q = p;
- s = p->lchild;
- while(s->rchild)
- {
-
-
- q = s;
- s = s->rchild;
- }
-
- p->data = s->data;
-
- if(p != q)
- q->rchild = s->lchild;
- else
- q->lchild =s->lchild;
- free(s);
- }
- }
-
-
-
-
-
-
- bool delete_BSTree(BSTree &pTree,int key)
- {
-
- if(!pTree)
- return false;
- else
- {
- if(key == pTree->data)
- {
- delete_Node1(pTree);
-
- return true;
- }
- else if(key < pTree->data)
- return delete_BSTree(pTree->lchild,key);
- else
- return delete_BSTree(pTree->rchild,key);
- }
- }
-
-
-
-
- BSTree create_BSTree(int *arr,int len)
- {
- BSTree pTree = NULL;
- int i;
-
- for(i=0;i<len;i++)
- insert(pTree,arr[i]);
- return pTree;
- }
-
-
-
-
- void in_traverse(BSTree pTree)
- {
- if(pTree)
- {
- if(pTree->lchild)
- in_traverse(pTree->lchild);
- printf("%d ",pTree->data);
- if(pTree->rchild)
- in_traverse(pTree->rchild);
- }
- }
-
-
- int main()
- {
- int i;
- int num;
- printf("请输入节点个数:");
- scanf("%d",&num);
-
-
- int *arr = (int *)malloc(num*sizeof(int));
- printf("请依次输入这%d个整数(必须互不相等):",num);
- for(i=0;i<num;i++)
- scanf("%d",arr+i);
-
-
- BSTree pTree = create_BSTree(arr,num);
- printf("中序遍历该二叉排序树的结果:");
- in_traverse(pTree);
- printf("n");
-
-
- int key;
- printf("请输入要查找的整数:");
- scanf("%d",&key);
- if(search(pTree,key))
- printf("查找成功n");
- else
- printf("查找不到该整数n");
-
-
- printf("请输入要插入的整数:");
- scanf("%d",&key);
- if(insert(pTree,key))
- {
- printf("插入成功,插入后的中序遍历结果:");
- in_traverse(pTree);
- printf("n");
- }
- else
- printf("插入失败,该二叉排序树中已经存在整数%dn",key);
-
-
- printf("请输入要删除的整数:");
- scanf("%d",&key);
- if(delete_BSTree(pTree,key))
- {
- printf("删除成功,插入后的中序遍历结果:");
- in_traverse(pTree);
- printf("n");
- }
- else
- printf("删除失败,该二叉排序树中不存在整数%dn",key);
-
- return 0;
- }
测试结果如下:
转自:http://blog.csdn.net/ns_code/article/details/19823463
标签二叉,排序,完整,实现,代码,二叉,排序,简介,Binary
网友评论