對分查找演算法雙叉樹顯示

1. 二叉樹查找樹演算法實現

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef int ElemType;
typedef int Status;
typedef struct TElemType{
int key;
int num;
}TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

Status SearchBST(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) { p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status SearchBST1(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) {
printf("%d %d",p->data.key,p->data.num);
p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status InsertBST(BiTree &T,TElemType e){
BiTree s,p;
if(!SearchBST(T,e.key,NULL,p)){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if(LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return OK;
}
}
Status Output(TElemType e){
printf("%d ",e.key);
printf("%d\n",e.num);
}
Status PreOrderTraver( BiTree T){//二叉樹先序遍歷
if(T==NULL) return ERROR;
else{
Output(T->data);
PreOrderTraver(T->lchild);
PreOrderTraver(T->rchild);}
return OK;
}
int main()
{
BiTree T,f=NULL,q;
TElemType a;
int i,n,b;
printf("請輸入你要創建的二叉排序樹的結點個數:\n");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",a.key);
scanf("%d",a.num);
InsertBST(T,a);
}
printf("請輸入你要查找的關鍵字: ");{
scanf("%d",b);
if(SearchBST1(T,b,f,q)) printf("查找成功！\n");
else printf("查找失敗！\n");}
printf("二叉樹的先序遍歷:\n");
PreOrderTraver(T);
system("pause");
return 0;
}
這個就是！希望可以幫助你！

2. 實驗四 二叉排序樹查找

#include<iostream.>
using namespace std;
typedef int KeyType;
typedef struct tree//聲明樹的結構
{
struct tree *left; //存放左子樹的指針
struct tree *right; //存放又子樹的指針
KeyType key; //存放節點的內容
} BSTNode, * BSTree; //聲明二叉樹的鏈表
BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序樹中插入結點
{ //若二叉排序樹tptr中沒有關鍵字為key的結點，則插入，否則直接返回
BSTree f,p=tptr; //p的初值指向根結點
while(p) //查找插入位置，循環結束時，p是空指針，f指向待插入結點的雙親
{
if(p->key==key) //樹中已有key，無須插入
return tptr;
f=p; //f保存當前查找的結點，即f是p的雙親
p=(key<p->key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode)); //生成新結點
p->key=key; p->left=p->right=NULL;
if(tptr==NULL) //原樹為空，新插入的結點為新的根
tptr=p;
else
if(key<f->key)
f->left=p;
else
f->right=p;
return tptr;
}
BSTree createBST()//建立二叉樹
{
BSTree t=NULL; //根結點
KeyType key;
cin>>key;
while(key!=-1)
{
t=insertBST(t,key);
cin>>key;
}
return t;
}
void inorder_btree(BSTree root)// 中序遍歷列印二叉排序樹
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
cout<<" "<<p->key<<" ";
inorder_btree(p->right );
}
}
int searchBST(BSTree t,KeyType key)//查找
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(key<t->key)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}
BSTree deleteBST(BSTree tptr,KeyType key)//刪除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key<p->key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子樹都為空*/
{
if(!parent) //要刪根，須修改根指針
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子樹為空，則重接p的左子樹
{
p=p->left;
if(!parent) //要刪根，須修改根指針
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子樹為空，則重接p的左子樹
{
p=p->right;
if(!parent) //要刪根，須修改根指針
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子樹和右子樹，用p的後繼覆蓋p然後刪去後繼
{ //另有方法：用p的前驅覆蓋p然後刪去前驅||合並p的左右

parent=p; //由於用覆蓋法刪根，則不必特殊考慮刪根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
do
{
cout<<"\n\n"<<endl;
cout<<"\t\t*******請選擇你要執行的操作:********"<<endl;
cout<<"\n"<<endl;
cout<<"\t\t C.創建一棵二叉排序樹\n";
cout<<"\t\t E.結束本程序\n";
cout<<"\n\n\t\t************************************"<<endl;
flag=0;
do
{
if(flag!=0)
cout<<"選擇操作錯誤！請重新選擇！\n";
fflush(stdin);
cin>>cmd;
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
cout<<"請輸入你所要創建的二叉樹的結點的值，以-1結束：\n";
root=createBST();
do
{
flag=0;
cout<<"\n\n中序遍歷二叉樹："<<endl;
inorder_btree(root);
cout<<"\n"<<endl;
cout<<"\t\t************請選擇你要對這棵二叉樹所做的操作:**************"<<endl;
cout<<"\t\t** **"<<endl;
cout<<"\t\t** S......查找你想要尋找的結點 **"<<endl;
cout<<"\t\t** I......插入你想要插入的結點 **"<<endl;
cout<<"\t\t** D......刪除你想要刪除的結點 **"<<endl;
cout<<"\t\t** Q......結束對這棵二叉樹的操作 **"<<endl;
cout<<"\t\t** **"<<endl;

cout<<"\t\t***********************************************************"<<endl;
do{
if(flag!=0)
cout<<"選擇操作錯誤！請重新選擇！\n";
fflush(stdin);
scanf("%c",&cmd);
flag++;

}while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{

case 's':
case 'S':
cout<<"請輸入你要查找結點的關鍵字：\n";
cin>>key;
test=searchBST(root,key);
if(test==0)
cout<<"\n對不起，你所查找的結點 "<<key<<"不存在!";
else
cout<<"\n成功找到結點\n"<<key<<" ";
break;
case 'i':
case 'I':
cout<<"請輸入你要插入結點的關鍵字：\n";
cin>>key;
root=insertBST(root,key); //注意必須將值傳回根
break;
case 'd':
case 'D':
cout<<"請輸入你要刪除結點的關鍵字：\n";
cin>>key;
root=deleteBST(root,key); //注意必須將值傳回根
if(root==NULL)
cout<<"\n對不起，你所刪除的結點 "<<key<<" 不存在!\n";
else
cout<<"\n成功刪除結點 "<<key<<" ";
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='e'&&cmd!='E');
return 0;
}

3. 二叉樹演算法是什麼

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。

二叉樹的第i層至多有2^（i 1）個結點；深度為k的二叉樹至多有2^k 1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

(3)對分查找演算法雙叉樹顯示擴展閱讀：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

1、空二叉樹——(a)

2、只有一個根結點的二叉樹——(b);

3、右子樹為空的二叉樹——(c);

4、左子樹為空的二叉樹——(d);

5、完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

4. 平衡二叉樹的各種演算法實現

多值結點平衡二叉樹的結構及演算法研究
1引言
傳統的AV1.樹是一種應用較為廣泛的數據結構，適合」幾組織在內存中的較小索引.它的
每個結l從上存儲有一個關鍵字、一個平衡因子和兩個指針項，山」幾它是一棵接近」幾理想狀態的
平衡二叉樹，所以AV1.樹具有很高的查詢效率.但正如任何事物都具有兩而性一樣，AV1.樹同
樣存在比較嚴重的缺l從，一是存儲效率比較低:真正有用的關鍵字在結l從上所，片的空間比例較
小，而作為輔助信息的平衡因子和指針卻，片據較大的空間;二是額外運算量比較大:當有結l從
被插入或刪除而導致AV1.樹不平衡時，AV1.樹就需要進行調整而保持它的平衡性，山」幾每個
結l從上只有一個關鍵字，所以任何一次的數據插入或刪除都有可能導致AV1.樹的平衡調整，
這種頻繁的調整運算將大大降低AV1.樹的存取效率.為解決以上問題，結合T3樹每個結l從可
以存儲多個關鍵字項的優l側}l，木文提出了多值結l從平衡二叉樹(簡稱MAV1.樹)，它的主要特
點在」幾每個MAV1.樹的結l從都存儲有多個關鍵字項，而其它信息仍與AV1.樹一樣，即一個平
衡因子和兩個指針項.
2 MAV1.樹結構描述
MAV1.樹仍舊是一種平衡二叉樹，它的整體樹型結構和演算法也是建立在傳統的平衡二叉
樹基礎之上的.MAV1.樹的特徵在」幾它的每個結l從都可以存儲多個關鍵字(較理想的取值大約
在20} 50個之間).用C++語言描述的MAV1.樹結l從結構如卜:
struct NodeStruct
int IJ1emsOnNode;
int bf:
struct NodPStruct*lch;ld:
//一結點中項的數目
//平衡因子
//夕.子
struct NodeStruct * rchild:
}lemType }lemsi Max}lem} ;//結點中的項數組
Node T:
在這種結構中.ElemsOnNode反映的是「當前狀態卜」該結l從中關鍵字項的個數.當在此結
點插入一個關鍵字時.FlemsOnNode值加1.當刪除一個關鍵字時.則FlemsOnNode值減1.每個
結l從上可存儲的關鍵字個數介J幾1 } M axElem之間.bf為平衡因r.其作用等同J幾AV1.樹的平
衡因r. MAV1.樹的任一結l從的平衡因r只能取一1 ,0和1.如果一個結l從的平衡因r的絕對
值大」幾1.則這棵樹就失去了平衡.需要做平衡運算保持平衡.lehild和:child分別為指向左右
J"樹根結0的指針.Flems[ i]為結0中第i個關鍵字項.Flems} MaxFlem」是一個按升序排列的
關鍵字數組.具體的MAV1.樹結l從結構如圖1所示.
}lemsOnNode一h『一* leh;ld一
圖1
reh擊3
}lemsi 0}一
樹結點結構
}lemsi Max}lem}
MAVT
MAV1.樹的結構特l從使它比AV1.樹具有更高的存儲效率.在AV1.樹或MAV1.樹中.實際
有用的信急只有關鍵字.1f1! ElemsOnNode ,bf ,lehild和:child都是為了構建樹型結構If1J不得不添
加的輔助信急. MAV1.樹就是通過減小這些輔助信急的比例來獲得較高的存儲效率.山MAV1.
樹結l從的定義可以看出:FlemsOnNode和bf為int型.各，片4個位元組長度.指針型的lchild和
rchild也各，片4個位元組長度.在以上四項信急中.AV1.樹結l從除了沒有ElemsOnNode外.其餘和
MAV1.樹相同.現假設關鍵字長度為24位元組.M axFl二值定為50.則對AV1.樹來說.它的結l從
長度為36位元組.其中輔助信h,長度為12位元組;If}J MAV1.樹的結l從長度是1. 2K位元組.其中輔助
信急長度為16位元組.山此可以看出.MAV1.樹在存儲時.結l從中輔助信急長度，片整個結l從長度
的比例是很小的.它對存儲空間的利用效率比 AV1.樹要高.這一l從對」幾主要而向內存應用的
MAV1.樹來說是非常重要的.
在實際的應用中.當MAV1.樹作為資料庫索引結構時.為進一步節約內存空間.結l從中Fl-
emType的結構可根據實際需要作不同的定義.
( 1)當排序關鍵字較短時.可以直接將資料庫中的關鍵字值拷貝到索引文件中.這樣
MAV1.樹既有較快的運行速度又不會，片用太大的空間.此時ElemType定義如卜
struct IdxRlemStruct
{
int RecPos://金己錄號
KeyType Key://關鍵字
}R1emType;
( 2}當排序關鍵字較長時.如果直接將資料庫中的關鍵字值拷貝到索引文件中會，片據較大
的空間.此時可以採用只存儲關鍵字地址的形式.這樣不管關鍵字有多長.映射到MAV1.樹後
都只，片據一個指針的固定長度.這種以時間換空間的方法比較適合內存容量有限的情況.此時
ElemType定義如卜
struct Tdxl?lemStruct
int RecPos:
char * Key
R1emType;
//記錄號
//關鍵字指釗
3基於MAUI.樹的運算
MAUI.樹的基木運算.包括MAUI.樹的建立、記錄的插入、刪除、修改以及查詢.這些演算法
與基J幾AVI.樹的演算法相似.都建立在一叉查詢和平衡演算法基礎上.
3. 1 MAVI,樹的平衡運算
如果在一棵原木是平衡的MAUI.樹中插入一個新結l從.造成了不平衡.此時必須調整樹的
結構.使之平衡化「21 .MAUI.樹的平衡演算法與AVI.樹的平衡演算法是相同的.但山J幾MAUI.樹的
每個結l從中都存儲有多個關鍵字.所以在關鍵字個數相同的情況卜. MAUI.樹的應用可以大大
減少平衡運算的次數.例如.假設具有n個關鍵字的待插入序列在插入過程中有5%(根據隨
機序列特l從的不同.此數值會有所差異.這里以比較保守的5%為例)的新產生結l從會導致一
叉樹出現不平衡.對AVI.樹來說.山」幾需要為每個關鍵字分配一個結l從.所以在整個插入過程
中做平衡的次數為n * 5%;對J幾MAUI.樹.設MAUI.樹中M axFl二的值被定義為k(k為大J幾1
的正整數少，則平均每k次的數據插入才會有一個新結l從產生，所以在整個插入過程中需做平
衡的次數僅為(nlk) * 5%.即在M axFl二取值為k的情況卜.對」幾相同的待插入關鍵字序列.
在插入過程中MAUI.樹用J幾平衡運算的開銷是AVI.樹的1/ k.
3. 2數據查找
在MAUI.樹上進行查找.是一個從根結l從開始.沿某一個分支逐層向卜進行比較判等的過
程.假設要在MAUI.樹上查找的值為GetKey.查找過程從根結l從開始.如果根指針為NU1.1..則
查找失敗;否則把要查找的值GetKey與根結l從關鍵字數組中的最小項Elems [ 0]進行比較.如
果GetKev小」幾當前結i最小關鍵字.則遞歸查找左r樹;如果GetKey'大」幾Elems [ 0].則將
GetKey'與根結0關鍵字數組中的最大項Fletns} MaxFl二一1]進行比較.如果GetKey'大」幾當前
結l從最大關鍵字.則遞歸查找右r樹;否則.對當前結l從的關鍵字數組進行查找(山」幾是有序序
列.可以採用折半查找以提高效率).如果有與GetKey'相匹配的值.則查找成功.返回成功信
息,7{報告查找到的關鍵字地址.
3. 3數據插入
數據插入是構建MAV1.樹的基礎.設要在MAV1.樹*T上插入一個新的數據兀素GetKev,
其遞歸演算法描述如卜:
(1)若*T為空樹.則申清一新結} ' Elems} MaxElem}.將GetKey'插入到Flems[ 0]的位置.樹
的深度增1.
(2)若*T未滿.則在*T中找到插入位置後將GetKey'插入.JI在插入後保持結l從中的各
關鍵項有序遞增.若己存在與GetKev相同的項.則不進行插入.
(3)如果*T為滿結l從目一GetKey'值介」幾Flems[ 0]和Flems} MaxFlem]之間.則在*T中找到
GetKev的插入位置posit ion.山」幾*T木身就是滿結l從.所以GetKev的插入必然會將原來*T中
的某個數據擠出去JI卜降到r樹中.根據插入位置position的不同.分以卜幾種情況處理:若*
T中存在與C etl} e`'相同的項.則不進行插入;若插入位置在*T結ii的前半部分(即position <
=MaxFlem/ 2).則將Flems[ 1]到Fletns} position」的數據依次左移一位.再把GetKey插入到Elems
} MaxFlem」中position的位置.Ifn原來*T中最左邊項數據將被擠入到*T的左r樹中.考察此
數據的特l從.它必然大」幾*T左r樹中的任一數據項.所以此時不需要作任何的額外運算.直
接將此數據插入到*T左r樹根結i從的最右r孫位置處就可以了(見圖2中插入，}} 11"後「1,>
的位置變化);若插入位置在*T結ii的後半部分(即position> MaxFlem/ 2).則將Fletns} posi-
tion}到Fletns} MaxFl二一2}的數據依次右移一位.再把GetKev插入到*T結0中position的位
置.與前一種情況類似.結l從中最右邊被擠出的項將被插入到*T的右r樹根結l從的最左r孫
的位置(見圖2中插入「25"後" 30"的位置變化).
插入，"}i」插入」zs0
}o i is i }a
s}土 s
圖2
滿結點插入數據的過程
(4)若GetKey的值小」幾T的最小項值.則將GetKey遞歸插入到T的左r樹中.即在遞歸調
用時GetKey值不變Ifn T= T->lehild.
(5)若GetKey的值大」幾T的最大項值.則將GetKey遞歸插入到T的右r樹中.即在遞歸調
用時GetKey值不變Ifn T= T->rehild.
4結束語
山J幾MAV1.樹的結l從中存儲有多個關鍵字值.所以它具有較高的存儲效率;對MAV l樹進
行查找是_分查找和順序查找的結合.其查詢效率只略低」幾AV1.樹.血山」幾MAV1.樹的平衡
運算比AV1.樹要少得多.所以MAV1.樹有很優秀的綜合運算效率.綜上所述.在數據量大、內
存容量相對較小、數據增刪運算比較頻繁的情況卜.用MAV1.樹作為常駐內存的索引結構是一
種理想的選擇.