實驗題目:查找技術綜合應用
實驗目的:
(1)熟練掌握查找的常用演算法;
(2)熟練設計和應用查找演算法解決比較簡單的實際問題。

實驗內容:二叉排序樹。

任意給定一組資料,設計一個演算法,建立一棵二叉排序樹,對它進行查找、插入、刪除等操作。
來源程式代碼:
#include<iostream>

using namespace std;

typedef struct TreeNode

{

int key;

struct TreeNode *left;

struct TreeNode *right;

}treeNode;

class BiSortTree

{

public:

BiSortTree(void);

void desplayTree(void);//顯示這個樹
void insertTree(int key);//在樹中插入一個值
void 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);

}

}

void 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;

}

}
創作者介紹

資訊園

shadow 發表在 痞客邦 PIXNET 留言(0) 人氣()