1.二叉排序树的概念:
二叉排序树是一种动态树表。 二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有例如以下性质的二叉树： ⑴ 若它的左子树非空，则左子树上全部结点的值均小于根结点的值； ⑵ 若它的右子树非空，则右子树上全部结点的值均大于根结点的值； ⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列2.二叉排序树的插入:
在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。 插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中； 当非空时，将待插结点keywordS->key和树根keywordt->key进行比較， 若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中， 若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程同样， 如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有同样keyword的结点为止。3. 二叉排序树生成： 从空的二叉排序树開始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。 说明： ① 每次插入的新结点都是二叉排序树上新的叶子结点。 ② 由不同顺序的keyword序列，会得到不同二叉排序树。 ③ 对于一个随意的keyword序列构造一棵二叉排序树，事实上质上对keyword进行排序。4.二叉排序树查找的程序实现: #include<malloc.h>#include<iostream.h>#include<stdio.h>typedef struct BiTNode{ int data; int flag; struct BiTNode *lchild,*rchild;}BTNode,BTree;//二叉排序树的查找非递归算法//在二叉排序树T中查找keyword为key的元素，若找到返回true,//否则返回false.bool SearchBST(BTree *T,int key){ BTree *p=T; while(p){ if(p->data==key) return true; p=(key<p->data)? p->lchild:p->rchild; } return false;}//二叉排序树的查找递归算法//在二叉排序树T中查找keyword为key的元素，若找到返回true,//否则返回false.bool SearchBST2(BTree *T,int key){ BTree *p=T; if(!p) return false; else if(p->data==key) return true; else if(key>p->data) return SearchBST2(p->rchild,key); else return SearchBST2(p->lchild,key);}//建立二叉排序树//当二叉排序树T中不存在keyword为key的元素时，插入key,并返回树的根，//否则不插入,并返回树的根。 BTree* InsertBST(BTree *T,int key){ BTree *f=T,*p=T; while(p){ if(p->data==key) return T; f=p;//用f记下查找路径上的最后一个訪问的节点 p=(key<p->data)? p->lchild:p->rchild; } p=(BTNode*)malloc(sizeof(BTNode)); p->data=key; p->lchild=p->rchild=NULL; if(T==NULL) T=p; else if (key<f->data) f->lchild=p; else f->rchild=p; return T;}//递归中序遍历void InOrderDisplay(BTree *T){ if(T){ InOrderDisplay(T->lchild); cout<<T->data; InOrderDisplay(T->rchild); }}//test:
int main(){ int i; int data; BTree *tree=NULL; for(i=0;i<4;i++){ cout<<"input data"<<endl; cin>>data; tree=InsertBST(tree,data); } InOrderDisplay(tree); bool find=SearchBST2(tree,24); cout<<find<<endl; return 0;}5. 二叉排序树的删除:
如果被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，以下分三种情况讨论：⑴ 若结点*p是叶子结点，则仅仅需改动其双亲结点*f的指针就可以。⑵ 若结点*p仅仅有左子树PL或者仅仅有右子树PR，则仅仅要使PL或PR 成为其双亲结点的左子树就可以。⑶ 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。② 以*p的中序前趋结点*s取代*p（即把*s的数据拷贝到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。(在以下的演示算法中用的就是此方法)6. 删除算法演示 ://删除二叉排序树中的一个节点//在二叉排序树T中删除keyword为key的结点void DelBST(BTree *T,int key){ BTree *p=T,*f,*q,*s,*root=T; while(p){ if(p->data==key) break; //找到keyword为key的结点 f=p;//记下keywordkey节点的父节点 p=(key<p->data)?p->lchild:p->rchild;//分别在*p的左、右子树中查找 } if(!p) return;//二叉排序树中无keyword为key的结点 if(p->lchild==NULL&&p->rchild==NULL){//p没有左右子树 if(p==T) T=NULL;//删除的是根节点 else if(p==f->lchild) f->lchild=NULL; else f->rchild=NULL; free(p); } else if(p->lchild==NULL&&p->rchild!=NULL)//p无左子树有右子树 { if(f->lchild==p) f->lchild=p->rchild; //将p的右子树链接到其父结点的左链上 else f->rchild=p->rchild; //将p的右子树链接到其父结点的右链上 free(p); } else if(p->rchild==NULL&&p->lchild!=NULL)//p有左子树无右子树 { if (f->lchild==p) f->lchild=p->lchild; //将p的左子树链接到其父结点的左链上 else f->rchild=p->lchild; //将p的左子树链接到其父结点的右链上 free(p); } else if(p->lchild!=NULL&&p->rchild!=NULL)//p既有左子树又有右子树 { q=p; s=p->lchild;//转左 while(s->rchild){//然后向右到尽头 q=s; s=s->rchild;//s指向被删节点的“前驱”(中序前驱) } p->data=s->data;//以p的中序前趋结点s取代p（即把s的数据拷贝到p中） if(q!=p) q->rchild=s->lchild;//重接q的右子树 else q->lchild=s->lchild;//重接q的左子树。 free(s); }}
7. 二叉排序树的查找: 在二叉排序树中进行查找的过程和二分查找相似，也是一个逐步缩小查找范围的过程。若查找成功，则是走了一条从根结点到待查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和keyword比較的次数不超过树的深度。 因为含有n个结点的二叉排序树不唯一，形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。 最好的情况是： 二叉排序树和二叉判定树形态同样。 最坏的情况是： 二叉排序树为单支树，这时的平均查找长度和顺序查找时同样。 最坏情况演示样例 就平均性能而言，二叉排序树上的查找和二分查找相差不大，而且二叉排序树上的插入和删除结点十分方便，无须大量移动结点。