当线性表作为查找表的组织形式时,可以有三种查找法,其中以二分查找效率最高。但由于二分查找要求表中结点按其关键字有序组织,且不能用链表作为存储结构,因此,当表的元素插入或删除操作频繁时,为维护表的有序性,势必要移动表中大量的结点,这种由移动结点引起的额外的时间开销,就会抵消二分查找的优点。在这种情况下,可采用二叉树作为存储结构,在此将它们统称为树表。
(1)二叉排序树又称为二叉查找树,是一种特殊的二叉树。其定义为:
(1)若它的左子树非空,则左子树上所有的结点的值均小于根结点的值
(2)若它的右子树非空,则右子树上所有的结点的值均大于根结点的值
(3)左、右子树本身又各是一棵二叉排序树
(2)二叉排序树定义:
typedef struct node{
KeyType key;Datatype other;
struct node *lchild,*rchild;
}BSTNode;
①在二叉排序树中插入新的结点,只要保证插入后仍符合二叉排序树的定义即可。插入过程如下:
(1)若二叉排序树为空,则待插入结点*s作为根结点插入到空树中
(2)当二叉树非空,将待插入结点的关键字s->key和树根的关键字t->key进行比较,若s->key=t->key,则说明此树中已有此结点,无需插入;若s->key
key,则将待插入结点*s插入到根的左子树中,否则将*s插入根的右子树中 (3)子树中的插入过程与步骤(1)(2)相同,直到把结点*s作为新的结点插入二叉排序树中,或直到发现该树中已有此*s结点为止。
②二叉排序树的插入算法
BSTNode *INSERTBST(BSTNode *s,BSTNode t){
BSTNode *f,*p;
if(t==NULL) return s;
p=t;
while(p!=NULL){
f=p;
if(s->key==p->key) return t;
if(s->keykey) p=p->lchild;
else p=p->rchild;
}
if(s->keykey) f->lchild=s;
else f->rchild=s;
return t;
}
③二叉排序树的生成算法
BSTNode *CREATBST(){
BSTNode *t,*s;
KeyType key,endflag=0;
DataType data;
t=NULL;
scanf("%d",&key);
while(k!=endflag){
s=malloc(BSTNode *)malloc(sizeof(BSTNode));
s->lchild=s->rchild=NULL;
s->key=key;
scanf("%d",data);
s->other=data;
t=INSERTBST(t,s);
scanf("%d",&key);
}
return 0;
}
①二叉排序树的查找算法
BSTNode *BSTSearch(BSTNode *t,KeyType t){
BSTNode *p=t;
while(p!=NULL){
if(p->key==k) return p;
if(p->key>k)
p=p->lchild;
else p=p->rchild;
}
}
②显然,在二叉排序树上进行查找,若查找成功,则是从根结点出发走一条从根到待查结点的路径;若查找不成功,则是从根结点出发走一条从根到某个叶子结点的路径。因此,与二分法类似,和关键字比较的次数不超过树的深度。
上一篇:有方N58CA和EA差异