二叉排序樹插入演算法

① 編寫在二叉排序樹中插入一個元素的演算法。謝謝啊。

bstnode*
insert_bst(int
w,
bstnode
*
p)
//首先你要看懂這是個遞歸
{
if
(p
==
null)
{
p
=
malloc(sizeof(bstnode));
//
插入的二叉樹為空或者到達葉子節點，也就是遞歸出口
p->lchild
=
null;
p->rchild
=
null;
p->key
=
w;
}
else
if
(w>
p->key)
p->rchild
=
insert_bst(w,
p->rchild);
//如果w比p->key大的話，插入右節點，也就是大的數在右節點，繼續遞歸
else
p->lchild
=
insert_bst(w,
p->lchild);
//小的數在左節點，接續遞歸
return
p;
}

② 實驗四 二叉排序樹查找

#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;
}

③ 編寫在二叉排序樹中插入一個元素的演算法。謝謝啊。

/*以下是用c++ 實現的二叉排序樹的源代碼*/

#include<iostream.h>
typedef struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;

}treeNode;

class BiSortTree
{
public:
BiSortTree(void);
void desplayTree(void);//顯示這個樹
void insertTree(int key);//在樹中插入一個值
deleteTree(int key);//在樹中刪除一個值
treeNode* searchTree(int key);//在樹中查找一個值

~BiSortTree();

private:
treeNode* buildTree(treeNode* head,int number);//建立一個樹
treeNode* search(treeNode* head ,int key);//查找
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父親節點的指針
treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子樹中最小的節點

void showTree(treeNode* head);//顯示
void destroyTree(treeNode* head);//刪除

treeNode *Head;

};

/**************以下是建立一個二叉排序樹****************/
BiSortTree::BiSortTree()
{
cout<<"建立一棵二叉排序樹,請輸入你要建樹的所有數(以-1 作為結束標志!): "<<endl;
Head=NULL;
int number;
cin>>number;
while(number!=-1)
{
Head=buildTree(Head,number);
cin>>number;

}

}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{

treeNode *p;
p=new treeNode;
p->key=number;
p->left =p->right=NULL;

if(head==NULL)
{

return p;
}
else
{

if(p->key <head->key)
head->left=buildTree(head->left,number);
else
head->right=buildTree(head->right,number);

return head;
}

}
/*****************以下是在一棵二叉排序樹插入一個數***********************************/
void BiSortTree::insertTree(int key)
{

Head=buildTree(Head,key);

}
/*****************以下是在一個二叉排序樹查找一個數是否存在*************************/
treeNode* BiSortTree::searchTree(int key)
{
return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head ,int key)
{
if(head==NULL)
return NULL;
if(head->key==key)
return head;
else
{
if(key<head->key )
return search( head->left,key);

else
return search(head->right,key);

}

}

/************以下是在一個二叉排序樹刪除一個給定的值*********************************/
BiSortTree::deleteTree(int key)
{

treeNode *p;
p=NULL;
p=search(Head,key);
if(p==NULL)
{
cout<<"Don't find the key";

}
if(p==Head)
{
Head=NULL;

}
else
{
treeNode* parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//葉子節點
{
if(parent->left==p)
{
parent->left=NULL;
}
else
{
parent->right=NULL;

}
}
else//非葉子節點
{
if(p->right==NULL)//該節點沒有右孩子
{
if(parent->left==p)
{
parent->left=p->left ;
}
else
{
parent->right=p->left;

}
}

else//該點有左右孩子
{
treeNode * rightMinSon,* secondParent;//secondParent為右子樹中的最小節點的父親
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right ,rightMinSon);

secondParent->left=rightMinSon->right;

if(p->right==rightMinSon)//右子樹中的最小節點的父親為p
{

p->right=rightMinSon->right ;

}

p->key=rightMinSon->key ;

}
}
}
}

treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{

if(head->left==p||head->right==p||head==p||head==NULL)
return head;
else
{
if(p->key<head->key)
return searchParent(head->left ,p);
else
return searchParent(head->right ,p);

}

}

treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子樹中最小的節點
{

if(head->left ==NULL||head==NULL)
{
return head;

}
else
{
return searchMinRight(head->left);

}

}

/*****************以下是顯示一個二叉排序樹****************************************/
void BiSortTree::desplayTree(void)
{

showTree(Head);
cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{

if(Head!=NULL)
{
showTree(Head->left ) ;

cout<<Head->key<<' ' ;

showTree(Head->right) ;

}

}

/*****************以下是刪除一棵整二叉排序樹************************************/
BiSortTree::~BiSortTree()
{
cout<<"已經消除了一棵樹!!!!"<<endl;
destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head )
{

if(head!=NULL)
{
destroyTree(head->left );
destroyTree(head->right );
delete head;

}

}

/*********************/
void print()
{

cout<<endl<<endl<<"以下是對二叉排序樹的基本操作:"<<endl
<<"1.顯示樹"<<endl
<<"2.插入一個節點"<<endl
<<"3.尋找一個節點"<<endl
<<"4.刪除一個節點"<<endl;
}

void main()
{
BiSortTree tree;
int number;
int choiceNumber;
char flag;
while(1)
{
print() ;

cout<<"請選擇你要進行的操作(1~4)"<<endl;
cin>>choiceNumber;
switch(choiceNumber)
{
case 1:
tree.desplayTree();break;
case 2:
cout<<"請插入一個數: "<<endl;
cin>>number;
tree.insertTree(number);
tree.desplayTree();
break;

case 3:
cout<<"請插入你要找數: "<<endl;
cin>>number;
if(tree.searchTree(number)==NULL)
{
cout<<"沒有發現"<<endl;
}
else
{

cout<<"發現"<<endl;

}
break;

case 4:
cout<<"請輸入你要刪除的數: "<<endl;
cin>>number;
tree.deleteTree(number);
tree.desplayTree();
break;

default: break;
}
cout<<"你是否要繼續(Y/N)?"<<endl;
cin>>flag;
if(flag=='N'||flag=='n')
break;

}

}

④ 二叉排序樹插入結點演算法

問題應該出在
int Insert_BinarySortTree(BinaryTree *T,datatype x)
你修改為int Insert_BinarySortTree(BinaryTree **T,datatype x) ==》 指針的指針
試試看，否則傳值而已，等函數返回 BT 該是NULL還是NULL

⑤ 急急急，求將兩顆二叉排序樹合並成一棵二叉排序樹的演算法，謝謝好心人！

提供個思路：遍歷第二棵樹，把其中每個元素依次插入到第一個二叉樹，從而達到合並的目的。
二叉排序樹的插入演算法如下：
//在二叉排序樹中插入關鍵字key
void InsertBST(t, key)
{
if(t==NULL)
{
t=new BiTree;
t->lchild=t->rchild=NULL;
t->data=key;
return;
}
if(key<t->data ) InsertBST(t->lchild,key);
else InsertBST (t->rchild, key );
}