二叉查找樹演算法
㈠ c++二叉搜索樹演算法
#include<iostream>
usingnamespacestd;
typedefstruct_node
{
intdata;
struct_node*pLeftPtr;
struct_node*pRightPtr;
}BTreeNode;
classBinarySearchTree
{
public:
BinarySearchTree();
~BinarySearchTree();
boolCreate(int*pIntArray,intarrLength);
boolInsert(intdata);
//查找節點，searchLength為搜索長度，返回值為true表示指定的數據存在，否則不存在
boolFind(intdata,int*searchLength);
//中序輸出二叉樹
voidMidOutput();
//釋放內存
voidDestroy();
voidDelete(intdata);
protected:
boolInsert(BTreeNode*pRoot,intdata);
boolFind(BTreeNode*pRoot,intdata,int*searchLength);
voidDelete(BTreeNode*&pRoot,intdata);
voidMidOutput(BTreeNode*pRoot);
voidDestroy(BTreeNode*pRoot);
private:
BTreeNode*m_pRoot;//二叉搜索樹根節點
};
BinarySearchTree::BinarySearchTree()
{
m_pRoot=NULL;
}
BinarySearchTree::~BinarySearchTree()
{
Destroy();
}
boolBinarySearchTree::Create(int*pIntArray,intarrLength)
{
for(inti=0;i<arrLength;i++)
{
if(!Insert(*(pIntArray+i)))
returnfalse;
}
returntrue;
}
boolBinarySearchTree::Insert(BTreeNode*pRoot,intdata)
{
BTreeNode*pNewNode=newBTreeNode;
if(pNewNode==NULL)
returnfalse;
pNewNode->data=data;
pNewNode->pLeftPtr=NULL;
pNewNode->pRightPtr=NULL;
BTreeNode*pCurrentNode=pRoot;
BTreeNode*pParentNode=pCurrentNode;//保存父節點的指針
intflag=0;//標記插入節點的位置
if(pCurrentNode==NULL)
{
m_pRoot=pNewNode;
}else{
while(pCurrentNode)
{
if(data<pCurrentNode->data)
{
pParentNode=pCurrentNode;
pCurrentNode=pCurrentNode->pLeftPtr;
flag=0;
}elseif(data>pCurrentNode->data){
pParentNode=pCurrentNode;
pCurrentNode=pCurrentNode->pRightPtr;
flag=1;
}
}
if(flag==0)
{
pParentNode->pLeftPtr=pNewNode;
}else{
pParentNode->pRightPtr=pNewNode;
}
}
returntrue;
}
boolBinarySearchTree::Insert(intdata)
{
returnInsert(m_pRoot,data);
}
boolBinarySearchTree::Find(BTreeNode*pRoot,intdata,int*searchLength)
{
if(pRoot==NULL)
{
*searchLength=0;
returnfalse;
}
BTreeNode*pCurrentNode=pRoot;
staticintlength=0;
while(pCurrentNode!=NULL)
{
if(data==pCurrentNode->data)
{
*searchLength=length;
cout<<"數字"<<data<<"存在二叉樹中,查找長度為:"<<endl<<length<<endl;
returntrue;
}elseif(data<pCurrentNode->data)
{
length++;
pCurrentNode=pCurrentNode->pLeftPtr;
}else{
length++;
pCurrentNode=pCurrentNode->pRightPtr;
}
}
*searchLength=length;
cout<<"數字"<<data<<"不在二叉樹中,查找長度為:"<<endl<<length<<endl;
length=0;//每次查找結束，重新賦值為0
returnfalse;
}
boolBinarySearchTree::Find(intdata,int*searchLength)
{
returnFind(m_pRoot,data,searchLength);
}
voidBinarySearchTree::Destroy(BTreeNode*pRoot)
{
BTreeNode*pCurrentNode=pRoot;
if(pCurrentNode==NULL)
return;
Destroy(pCurrentNode->pLeftPtr);
Destroy(pCurrentNode->pRightPtr);
deletepCurrentNode;
m_pRoot=NULL;
}
voidBinarySearchTree::Destroy()
{
Destroy(m_pRoot);
}
voidBinarySearchTree::MidOutput(BTreeNode*pRoot)
{
if(pRoot)
{
MidOutput(pRoot->pLeftPtr);
cout<<pRoot->data<<"";
MidOutput(pRoot->pRightPtr);
}
}
voidBinarySearchTree::MidOutput()
{
MidOutput(m_pRoot);
}
voidBinarySearchTree::Delete(intdata)
{
Delete(m_pRoot,data);
}
voidBinarySearchTree::Delete(BTreeNode*&pRoot,intdata)
{
if(!pRoot)
return;
elseif(data==pRoot->data){
if(pRoot->pLeftPtr==NULL&&pRoot->pRightPtr==NULL)//葉子節點
{
deletepRoot;
pRoot=NULL;
}elseif(pRoot->pLeftPtr!=NULL&&pRoot->pRightPtr==NULL){//只有左子樹
BTreeNode*pNode=pRoot->pLeftPtr;
deletepRoot;
pRoot=pNode;
}elseif(pRoot->pLeftPtr==NULL&&pRoot->pRightPtr!=NULL){//只有右子樹
BTreeNode*pNode=pRoot->pRightPtr;
deletepRoot;
pRoot=pNode;
}else{//有左右子樹
//找到左子樹的最大節點
BTreeNode*pCurrentNode=pRoot->pLeftPtr;
BTreeNode*pParentNode=NULL;
while(pCurrentNode->pRightPtr!=NULL)
{
pParentNode=pCurrentNode;
pCurrentNode=pCurrentNode->pRightPtr;
}
pRoot->data=pCurrentNode->data;
if(pParentNode)
{
pParentNode->pRightPtr=pCurrentNode->pLeftPtr;
}else{
pRoot->pLeftPtr=pCurrentNode->pLeftPtr;
}
deletepCurrentNode;
}
}elseif(data<pRoot->data)
Delete(pRoot->pLeftPtr,data);
else
Delete(pRoot->pRightPtr,data);
}
voidmain()
{
intdata[8];
cout<<"請輸入整形數據,數據用空格隔開,回車鍵結束輸入"<<endl;
for(inti=0;i<8;i++)
cin>>data[i];
//intdata[8]={13,15,6,20,14,5,7,18};
BinarySearchTreetree;
tree.Create(data,sizeof(data)/sizeof(data[0]));
cout<<"插入數據後的二叉樹為:"<<endl;
tree.MidOutput();
cout<<endl;
intlen_1=0;
intlen_2=0;
tree.Find(14,&len_1);
tree.Find(21,&len_2);
tree.Delete(20);
cout<<"刪除數字20後的二叉樹結果:"<<endl;
tree.MidOutput();
cout<<endl;
tree.Delete(15);
cout<<"刪除數字15後的二叉樹結果:"<<endl;
tree.MidOutput();
cout<<endl;
}
㈡ 二叉排序樹定義
二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數據結構中的一類。在一般情況下，查詢效率比鏈表結構要高。
定義一：
一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的結點。
定義二：
一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹。
定義三：
一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於或等於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
【注】：以上的三種定義在不同的數據結構教材中均有不同的定義方式 但是都是正確的 在開發時需要根據不 同的需求進行進行選擇。
插入刪除：
與次優二叉樹相對，二叉排序樹是一種動態樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等於給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點，並且是查找不成功時查找路徑上訪問的最後一個結點的左孩子或右孩子結點。
㈢ 二叉查找樹演算法
#include <iostream>using namespace std;typedef struct _node{ int data; struct _node *pLeftPtr; struct _node *pRightPtr;}BTreeNode;class BinarySearchTree{public: BinarySearchTree(); ~BinarySearchTree(); bool Create(int* pIntArray,int arrLength); bool Insert(int data); // 查找節點，searchLength為搜索長度，返回值為true表示指定的數據存在，否則不存在 bool Find(int data, int* searchLength); // 中序輸出二叉樹 void MidOutput(); // 釋放內存 void Destroy(); void Delete(int data);protected: bool Insert(BTreeNode* pRoot, int data); bool Find(BTreeNode* pRoot,int data, int *searchLength); void Delete(BTreeNode* &pRoot, int data); void MidOutput(BTreeNode* pRoot); void Destroy(BTreeNode* pRoot);private: BTreeNode* m_pRoot; //二叉搜索樹根節點};BinarySearchTree::BinarySearchTree(){ m_pRoot = NULL;}BinarySearchTree::~BinarySearchTree(){ Destroy();}bool BinarySearchTree::Create(int* pIntArray,int arrLength){ for(int i=0; i<arrLength; i++) { if(!Insert(*(pIntArray+i))) return false; } return true;}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){ BTreeNode* pNewNode = new BTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->pLeftPtr = NULL; pNewNode->pRightPtr = NULL; BTreeNode* pCurrentNode = pRoot; BTreeNode* pParentNode = pCurrentNode;// 保存父節點的指針 int flag = 0;// 標記插入節點的位置 if(pCurrentNode == NULL) { m_pRoot = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pLeftPtr; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; flag = 1; } } if(flag == 0) { pParentNode->pLeftPtr = pNewNode; }else{ pParentNode->pRightPtr = pNewNode; } } return true; }bool BinarySearchTree::Insert(int data){ return Insert(m_pRoot,data);}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){ if(pRoot == NULL) { *searchLength = 0; return false; } BTreeNode* pCurrentNode = pRoot; static int length = 0; while(pCurrentNode != NULL) { if(data == pCurrentNode->data) { *searchLength = length; cout<<"數字"<<data<<"存在二叉樹中,查找長度為: "<<endl<<length<<endl; return true; }else if(data < pCurrentNode->data) { length ++; pCurrentNode = pCurrentNode->pLeftPtr; }else{ length ++; pCurrentNode = pCurrentNode->pRightPtr; } } *searchLength = length; cout<<"數字"<<data<<"不在二叉樹中,查找長度為: "<<endl<<length<<endl; length = 0; // 每次查找結束，重新賦值為0 return false;}bool BinarySearchTree::Find(int data, int* searchLength){ return Find(m_pRoot,data,searchLength);}void BinarySearchTree::Destroy(BTreeNode* pRoot){ BTreeNode* pCurrentNode = pRoot; if(pCurrentNode == NULL) return; Destroy(pCurrentNode->pLeftPtr); Destroy(pCurrentNode->pRightPtr); delete pCurrentNode; m_pRoot = NULL;}void BinarySearchTree::Destroy(){ Destroy(m_pRoot);}void BinarySearchTree::MidOutput(BTreeNode* pRoot){ if(pRoot) { MidOutput(pRoot->pLeftPtr); cout<<pRoot->data <<" "; MidOutput(pRoot->pRightPtr); }}void BinarySearchTree::MidOutput(){ MidOutput(m_pRoot);}void BinarySearchTree::Delete(int data){ Delete(m_pRoot,data);}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){ if(!pRoot) return; else if(data == pRoot->data){ if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr == NULL) // 葉子節點 { delete pRoot; pRoot = NULL; }else if(pRoot->pLeftPtr != NULL && pRoot->pRightPtr == NULL){ // 只有左子樹 BTreeNode* pNode = pRoot->pLeftPtr; delete pRoot; pRoot = pNode; }else if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr != NULL){ // 只有右子樹 BTreeNode* pNode = pRoot->pRightPtr; delete pRoot; pRoot = pNode; }else{ // 有左右子樹 // 找到左子樹的最大節點 BTreeNode* pCurrentNode = pRoot->pLeftPtr; BTreeNode* pParentNode = NULL; while(pCurrentNode->pRightPtr != NULL) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; } pRoot->data = pCurrentNode->data; if(pParentNode) { pParentNode->pRightPtr = pCurrentNode->pLeftPtr; }else{ pRoot->pLeftPtr= pCurrentNode->pLeftPtr; } delete pCurrentNode; } }else if(data < pRoot->data) Delete(pRoot->pLeftPtr, data); else Delete(pRoot->pRightPtr, data);}void main(){ int data[8]; cout<<"請輸入整形數據, 數據用空格隔開, 回車鍵結束輸入"<<endl; for(int i=0; i<8; i++) cin>>data[i]; // int data[8] = {13,15,6,20,14,5,7,18}; BinarySearchTree tree; tree.Create(data,sizeof(data)/sizeof(data[0])); cout<<"插入數據後的二叉樹為: "<<endl; tree.MidOutput(); cout<<endl; int len_1=0; int len_2=0; tree.Find(14,&len_1); tree.Find(21,&len_2); tree.Delete(20); cout<<"刪除數字20後的二叉樹結果: "<<endl; tree.MidOutput(); cout<<endl; tree.Delete(15); cout<<"刪除數字15後的二叉樹結果: "<<endl; tree.MidOutput(); cout<<endl;}
㈣ 實驗四 二叉排序樹查找
#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;
}
㈤ 二叉搜索樹的基本操作
哈哈，居然有人來提問了，城院的
我剛奮鬥了2小時做了下，你看看對不？
Test5.cpp:
#include<iostream.h>
#include<stdlib.h>
typedefdoubleElemType;
#defineMaxsize100
#include"BSTree.h"
voidmain()
{
inti,n;
ElemTypex;
ElemTypea[Maxsize];
BTreeNode*bst;
InitBSTree(bst);
cout<<"請輸入你所要測試的二叉搜索樹的結點的個數:";
cin>>n;
cout<<"請輸入你要測試的二叉搜索樹:"<<endl;
for(i=0;i<n;i++){
cin>>a[i];
}
CreateBSTree(bst,a,n);
cout<<"你輸入的二叉搜索樹的廣義表形式為:";
PrintBSTree(bst);
cout<<endl;
cout<<"輸入一個待插入結點的整數值:";
cin>>x;
Insert(bst,x);
cout<<"插入結點後的二叉搜索樹的廣義表形式為:";
PrintBSTree(bst);
cout<<endl;
cout<<"輸入一個待刪除結點的值:";
cin>>x;
if(Delete(bst,x))cout<<"刪除元素"<<x<<"成功!"<<endl;
elsecout<<"刪除元素"<<x<<"失敗!"<<endl;
PrintBSTree(bst);
cout<<endl;
cout<<"該二叉搜索樹中的最大值為:"<<MaxBSTree(bst)<<endl;
}
BSTree.h:
structBTreeNode{
ElemTypedata;
ElemTypecount;
BTreeNode*left;
BTreeNode*right;
};
voidInitBSTree(BTreeNode*&bst)//初始化二叉搜索樹
{
bst=NULL;
}
voidPrintBSTree(BTreeNode*bst)//以廣義表形式輸出二叉搜索樹
{
if(bst!=NULL){
cout<<bst->data;
cout<<'['<<bst->count<<']';
if(bst->left!=NULL||bst->right!=NULL){
cout<<'(';
PrintBSTree(bst->left);
if(bst->right!=NULL)
cout<<',';
PrintBSTree(bst->right);
cout<<')';
}
}
}
voidInsert(BTreeNode*&bst,ElemTypeitem)
{
BTreeNode*t=bst,*parent=NULL;
while(t!=NULL){
parent=t;
if(item<t->data)t=t->left;
elseif(item>t->data)t=t->right;
else{
t->count++;
break;
}
}
if((t==NULL)||item!=parent->data){
BTreeNode*p=newBTreeNode;
p->data=item;
p->count=1;
p->left=p->right=NULL;
if(parent==NULL)bst=p;
elseif(item<parent->data)parent->left=p;
elseparent->right=p;
}
}
voidCreateBSTree(BTreeNode*&bst,ElemTypea[],intn)//建立二叉搜索樹（用非遞歸演算法實現)
{
bst=NULL;
for(inti=0;i<n;i++)
Insert(bst,a[i]);
}
boolDelete(BTreeNode*&bst,ElemTypeitem)
{
BTreeNode*t=bst,*parent=NULL,*m,*n;
while((t!=NULL)&&(t->data!=item)){
if(item==t->data)break;
else{
if(item<t->data){
parent=t;
t=t->left;
}
else{
parent=t;
t=t->right;
}
}
}
if(t->count>1){
t->count--;
returntrue;
}
elseif(t==NULL){
cout<<"沒有找到待刪除結點!"<<endl;
returnfalse;
}
else{
if((t->left==NULL)&&(t->right==NULL)){
if(t==bst)
bst=NULL;
else{
if(t==parent->left)
parent->left=NULL;
else
parent->right=NULL;
}
}
elseif((t->left==NULL)||(t->right==NULL)){
if(t==bst){
if(t->left==NULL)
bst=t->right;
else
bst=t->left;
}
else{
if((t==parent->left)&&(t->left!=NULL))
parent->left=t->left;
elseif((t==parent->left)&&(t->right!=NULL))
parent->left=t->right;
elseif((t==parent->right)&&(t->left!=NULL))
parent->right=t->left;
elseif((t==parent->right)&&(t->right!=NULL))
parent->right=t->right;
}
}
else{
if((t->left!=NULL)&&(t->right!=NULL)){
m=t;
n=t->left;
while(n->right!=NULL){
m=n;
n=n->right;
}
t->data=n->data;
if(m==t)
t->left=n->left;
else
m->right=n->left;
t=n;
}
}
free(t);
returntrue;
}
}
ElemTypeMaxBSTree(BTreeNode*bst)//求二叉搜索樹的最大結點值（用非遞歸演算法實現）
{
ElemTypemax;
if(bst==NULL){
cout<<"該二叉搜索樹為空！"<<endl;
exit(1);
}
max=bst->data;
while(bst!=NULL){
if(max<bst->data)
max=bst->data;
bst=bst->right;
}
returnmax;
}
你試試吧，應該對的，選我做答案哈~
㈥ 二叉樹查找樹演算法實現
#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;
}
這個就是！希望可以幫助你！
㈦ 題目3． 平衡二叉樹演算法查找樹中某節點的時間復雜度是多少
平均查找的時間復雜度為O(log n)。
平衡樹的查找過程和排序樹的相同。在查找過程中和給定值進行比較關鍵字個數不超過樹的深度。
如果二叉樹的元素個數為n，那麼不管是對樹進行插入節點、查找、刪除節點都是log(n)次循環調用就可以了。它的時間復雜度相對於其他數據結構如數組等是最優的。
是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。
(7)二叉查找樹演算法擴展閱讀：
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：
(1)空二叉樹——(a)
(2)只有一個根結點的二叉樹——(b);
(3)右子樹為空的二叉樹——(c);
(4)左子樹為空的二叉樹——(d);
(5)完全二叉樹——(e)
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
㈧ 二叉搜索樹的演算法實現
1 二叉排序樹的查找演算法
2 在二叉排序樹插入結點的演算法
3 在二叉排序樹刪除結點的演算法
4 二叉排序樹性能分析 在二叉排序樹b中查找x的過程為：
若b是空樹，則搜索失敗，否則：
若x等於b的根結點的數據域之值，則查找成功；否則：
若x小於b的根結點的數據域之值，則搜索左子樹；否則：
查找右子樹。
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &*p){
//在根指針T所指二叉排序樹中遞歸地查找其關鍵字等於key的數據元素，若查找成功，
//則指針p指向該數據元素結點，並返回TRUE，否則指針指向查找路徑上訪問的最後
//一個結點並返回FALSE，指針f指向T的雙親，其初始調用值為NULL
if(!T){ p=f; return FALSE;} //查找不成功
else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功
else if LT(key,T->data.key)
return SearchBST(T->lchild, key, T, p); //在左子樹中繼續查找
else return SearchBST(T->rchild, key, T, p); //在右子樹中繼續查找
pascal語言實現
type
Link = ^tree;
Tree = record
D :longint;
Left :link;
Right :link;
End;
function search(n :longint;t :link):boolean;
Begin
If t^.d < n then begin
If t^.right = nil then exit(false) else exit(search(n,t^.right));
End;
If t^.d > n then begin
If t^.left = nil then exit(false) else exit(search(n,t^.left));
End;
Exit(true);
End; 向一個二叉排序樹b中插入一個結點s的演算法，過程為：
若b是空樹，則將s所指結點作為根結點插入，否則：
若s->data等於b的根結點的數據域之值，則返回，否則：
若s->data小於b的根結點的數據域之值，則把s所指結點插入到左子樹中，否則：
把s所指結點插入到右子樹中。
/*當二叉排序樹T中不存在關鍵字等於e.key的數據元素時，插入e並返回TRUE，否則返回FALSE*/
Status InsertBST(BiTree &T, ElemType e)
{
if(!SearchBST(T, e.key, NULL,p)
{
s=(BiTree *)malloc(sizeof(BiTNode));
s->data = e; s->lchild = s->rchild = NULL;
if(!p) T-s;
//被插結點*s為新的根結點
else if LT(e.key, p->data.key) p->lchld = s;
//被子插結點*s為左孩子
else ->rchild = s;
//被插結點*s為右孩子
return TRUE;
}
else
return FALSE;
//樹中已有關鍵字相同的結點，不再插入
}
pascal代碼:
procere push(n :longint;var t:link);
Var P,q :link;
Begin
If t^.d < n then begin
If t^.right = nil then begin
New(p);
P^.d := n;
P^.right := nil;
P^.left := nil;
T^.right := p;
End else push(n,t^.right);
End else begin
If t^.left = nil then begin
New(p);
P^.d := n;
P^.right := nil;
P^.left := nil;
T^.left := p;
End else push(n,t^.left);
End;
End; 在二叉排序樹刪去一個結點，分三種情況討論：
若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由於刪去葉子結點不破壞整棵樹的結構，則只需修改其雙親結點的指針即可。
若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹或右子樹即可，作此修改也不破壞二叉排序樹的特性。
若*p結點的左子樹和右子樹均不空。在刪去*p之後，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：其一是令*p的左子樹為*f的左子樹，*s為*f左子樹的最右下的結點，而*p的右子樹為*s的右子樹；其二是令*p的直接前驅（或直接後繼）替代*p，然後再從二叉排序樹中刪去它的直接前驅（或直接後繼）。在二叉排序樹上刪除一個結點的演算法如下：
Status DeleteBST(BiTree &T, KeyType key){
//若二叉排序樹T中存在關鍵字等於key的數據元素時，則刪除該數據元素，並返回
//TRUE；否則返回FALSE
if(!T) return FALSE; //不存在關鍵字等於key的數據元素
else{
if(EQ(key, T->data.key)) {return Delete(T)}; 找到關鍵字等於key的數據元素
else if(LT(key, T->data.key)) return DeleteBST(T->lchild, key);
else return DeleteBST(T->rchild, key);
}
}
Status Delete(BiTree &p){
//從二叉排序樹中刪除結點p，並重接它的左或右子樹
if(!p->rchild){ //右子樹空則只需重接它的左子樹
q=p; p=p->lchild; free(q);
}
else if(!p->lchild){ //左子樹空只需重接它的右子樹
q=p; p=p->rchild; free(q);
}
else{ //左右子樹均不空
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild
} //轉左，然後向右到盡頭
p->data = s->data; //s指向被刪結點的「前驅」
if(q!=p)
q->rchild = s->lchild; //重接*q的右子樹
else
q->lchild = s->lchild; //重接*q的左子樹
free(s);
}
return TRUE;
}
㈨ 求個二叉排序樹查找的遞歸演算法
#include<iostream> #include<string> #include<cstring> using namespace std; class BinaryTreeNode {public: string data; int w; BinaryTreeNode *leftchild; BinaryTreeNode *rightchild; BinaryTreeNode *parent; int pos[50]; BinaryTreeNode(string a,int postion) { data=a; w=1; leftchild=NULL; rightchild=NULL; parent=NULL; pos[0]=postion; } }; class BSTree {public: BinaryTreeNode *root; BSTree(){root=NULL;} void Insert(string a,int postion); void Delete(string key); BinaryTreeNode *Search(string key,BinaryTreeNode*& pr,BinaryTreeNode *&parent); void InOrder(BinaryTreeNode *&root); void PreOrder(BinaryTreeNode *&root); }; void BSTree::InOrder(BinaryTreeNode *&root) { if(root) { InOrder(root->leftchild); cout<<root->data; cout<<" "<<root->w<<endl; InOrder(root->rightchild); } } void BSTree::PreOrder(BinaryTreeNode*& root) { if(root) { cout<<root->data; cout<<" "<<root->w<<endl; PreOrder(root->leftchild); PreOrder(root->rightchild); } } BinaryTreeNode *BSTree::Search(string key,BinaryTreeNode*& pr,BinaryTreeNode*& parents) { BinaryTreeNode *p=root; pr=root; while(p) { parents=p; if(key<p->data) { pr=p; p=p->leftchild; } else if(key>p->data) { pr=p; p=p->rightchild; } else return p; } return NULL; } void BSTree::Insert(string a,int postion) { BinaryTreeNode *pr,*p,*pp=NULL; p=Search(a,pr,pp); if(p!=NULL) { p->w++; p->pos[p->w-1]=postion; return; } BinaryTreeNode *r=new BinaryTreeNode(a,postion); if(!root) root=r; else if(a<pp->data) pp->leftchild=r; else pp->rightchild=r; } void BSTree::Delete(string key) { BinaryTreeNode *p,*pr,*pp; p=Search(key,pp,pr); if(p==NULL) return; if(p->leftchild&&p->rightchild) { BinaryTreeNode *s=p->rightchild,*ps=p; while(s->leftchild) { ps=s; s=s->leftchild; } p->data=s->data; p->w=s->w; for(int i=0;i<s->w;i++) { p->pos[i]=s->pos[i]; } pp=ps; p=s; } if(p->leftchild) { if(pp->leftchild==p) { pp->leftchild=p->leftchild; p->leftchild->parent=pp; } else { pp->rightchild=p->leftchild; p->leftchild->parent=pp; } } else if(p->rightchild) { if(pp->leftchild
㈩ 二叉樹演算法有哪些應用場景
二叉樹常被用於實現二叉查找樹和二叉堆。
在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」和「右子樹」。
根據不同的用途可分為：
1、完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
2、滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
3、平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
(10)二叉查找樹演算法擴展閱讀
深度為h的二叉樹最多有個結點(h>=1)，最少有h個結點。對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1。
有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系為若I為結點編號則 如果I>1，則其父結點的編號為I/2。如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I。若2*I>N，則無左孩子。如果2*I+1<=N，則其右孩子的結點編號為2*I+1。