二叉排序樹

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;

}//二叉排序樹的查找遞歸算法

bool SearchBST2(BTree *T,int key){

 if(!p)

  return false;

 else

   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;

  if(p->data==key) return T;

  f=p;//用f記下查找路徑上的最後一個訪問的節點

 p=(BTNode*)malloc(sizeof(BTNode));

 p->data=key;

 p->lchild=p->rchild=NULL;

 if(T==NULL)

  T=p;

  if (key<f->data)

   f->lchild=p;

   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;

 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;

  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;

    f->rchild=NULL;

 free(p);

 else if(p->lchild==NULL&&p->rchild!=NULL)//p無左子樹有右子樹

 {

  if(f->lchild==p)

   f->lchild=p->rchild; //将p的右子樹連結到其父結點的左鍊上

   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的左子樹連結到其父結點的左鍊上

   f->rchild=p->lchild; //将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個結點的二叉排序樹的平均查找長度和樹的形态有關。

   最好的情況是： 二叉排序樹和二叉判定樹形态同樣。

   最壞的情況是： 二叉排序樹為單支樹，這時的平均查找長度和順序查找時同樣。

   最壞情況示範樣例

   就平均性能而言，二叉排序樹上的查找和二分查找相差不大，而且二叉排序樹上的插入和删除結點十分友善，無須大量移動結點。