mahdi.manian
پنج شنبه 07 خرداد 1394, 22:47 عصر
با عرض سلام.
بنده درخت BST را طراحی کردم که در آن اعمال زیر انجام می شود:
1-درج اعداد و مرتب سازی
2-نمایش اعداد مرتب شده
3.حذف یک عدد
موارد 1 و 2 به درستی کار می کند. مورد 3 که حذف گره از درخت BST هست مشکل داره به طوری که برخی از اعداد وارد شده را نمی توان حذف کرد. برای مثال اگر 10 عدد وارد درخت کنیم، 1-2 تای آن را نمی توان حذف کرد.
نحوه حذف هم به این صورت هست که اول توسط یه تابع به نام search_bstگروه پیدا میشه سپس توسط تابع del_bst گره حذف میشه.
سورس کامل برنامه در Visual C++:
// BST_Tree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
using namespace std;
struct tree_node
{
int info;
tree_node *left, *right;
};
tree_node *par=NULL;
void inorder(tree_node *root);
void insert_bst(tree_node *r, tree_node *p);
bool search_bst(tree_node *r, int value);
void del_bst(tree_node *par, tree_node *p);
int _tmain()
{
tree_node *p, *root=NULL;
while(true)
{
system("cls");
cout<<"1.Insert numbers and sorting"<<endl;
cout<<"2.Show sorted numbers"<<endl;
cout<<"3.Search and delete a number"<<endl;
cout<<"4.Exit"<<endl;
int s, n, c, key;
cin>>s;
switch(s)
{
case 1:
system("cls");
cin>>n;
while(n)
{
p=new(tree_node);
p->info=n;
p->left=p->right=NULL;
if(root==NULL)
root=p;
else
insert_bst(root, p);
cin>>n;
}
cout<<"Sorted list is:"<<endl;
inorder(root);
cout<<endl<<"Do yout want to continue? 0/1"<<endl;
cin>>c;
if(c!=1)
std::exit(0);
break;
case 2:
system("cls");
cout<<"Sorted list is:"<<endl;
inorder(root);
cout<<endl<<"Do yout want to continue? 0/1"<<endl;
cin>>c;
if(c!=1)
std::exit(0);
break;
case 3:
system("cls");
cout<<"Enter search key"<<endl;
cin>>key;
if(!search_bst(root,key))
cout<<"Not Found!"<<endl;
cout<<"Sorted list is:"<<endl;
inorder(root);
cout<<endl<<"Do yout want to continue? 0/1"<<endl;
cin>>c;
if(c!=1)
std::exit(0);
break;
case 4:
std::exit(0);
}
}
return 0;
}
void inorder(tree_node *root) {
if(root==NULL)
return;
inorder(root->left);
cout<<root->info<<" ";
inorder(root->right);
}
void insert_bst(tree_node *r, tree_node *p) {
if(p->info < r->info)
if(r->left==NULL)
r->left=p;
else
insert_bst(r->left, p);
else
if(r->right==NULL)
r->right=p;
else
insert_bst(r->right, p);
}
bool search_bst(tree_node *r, int value) {
if(r)
{
if(r->info == value) {
del_bst(par, r);
return(true);
}
else if(value <r->info) {
par=r;
search_bst(r->left, value);
}
else {
par=r;
search_bst(r->right, value);
}
}
else
return(false);
}
void del_bst(tree_node *par, tree_node *p) {
if(par->left || par->right)
{
if(par->left==p)
if(p->left==NULL)
par->left=p->right;
else
par->left=p->left;
else
if(p->right)
par->right=p->right;
else
par->right=par->left;
}
else {
if(par->left==p)
par->left=NULL;
else
par->right=NULL;
}
if(par->left && par->right)
{
par=p;
p=p->right;
while(p)
{
par=p;
p=p->left;
}
}
}
ممنون میشوم راهنمایی کنید.
بنده درخت BST را طراحی کردم که در آن اعمال زیر انجام می شود:
1-درج اعداد و مرتب سازی
2-نمایش اعداد مرتب شده
3.حذف یک عدد
موارد 1 و 2 به درستی کار می کند. مورد 3 که حذف گره از درخت BST هست مشکل داره به طوری که برخی از اعداد وارد شده را نمی توان حذف کرد. برای مثال اگر 10 عدد وارد درخت کنیم، 1-2 تای آن را نمی توان حذف کرد.
نحوه حذف هم به این صورت هست که اول توسط یه تابع به نام search_bstگروه پیدا میشه سپس توسط تابع del_bst گره حذف میشه.
سورس کامل برنامه در Visual C++:
// BST_Tree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
using namespace std;
struct tree_node
{
int info;
tree_node *left, *right;
};
tree_node *par=NULL;
void inorder(tree_node *root);
void insert_bst(tree_node *r, tree_node *p);
bool search_bst(tree_node *r, int value);
void del_bst(tree_node *par, tree_node *p);
int _tmain()
{
tree_node *p, *root=NULL;
while(true)
{
system("cls");
cout<<"1.Insert numbers and sorting"<<endl;
cout<<"2.Show sorted numbers"<<endl;
cout<<"3.Search and delete a number"<<endl;
cout<<"4.Exit"<<endl;
int s, n, c, key;
cin>>s;
switch(s)
{
case 1:
system("cls");
cin>>n;
while(n)
{
p=new(tree_node);
p->info=n;
p->left=p->right=NULL;
if(root==NULL)
root=p;
else
insert_bst(root, p);
cin>>n;
}
cout<<"Sorted list is:"<<endl;
inorder(root);
cout<<endl<<"Do yout want to continue? 0/1"<<endl;
cin>>c;
if(c!=1)
std::exit(0);
break;
case 2:
system("cls");
cout<<"Sorted list is:"<<endl;
inorder(root);
cout<<endl<<"Do yout want to continue? 0/1"<<endl;
cin>>c;
if(c!=1)
std::exit(0);
break;
case 3:
system("cls");
cout<<"Enter search key"<<endl;
cin>>key;
if(!search_bst(root,key))
cout<<"Not Found!"<<endl;
cout<<"Sorted list is:"<<endl;
inorder(root);
cout<<endl<<"Do yout want to continue? 0/1"<<endl;
cin>>c;
if(c!=1)
std::exit(0);
break;
case 4:
std::exit(0);
}
}
return 0;
}
void inorder(tree_node *root) {
if(root==NULL)
return;
inorder(root->left);
cout<<root->info<<" ";
inorder(root->right);
}
void insert_bst(tree_node *r, tree_node *p) {
if(p->info < r->info)
if(r->left==NULL)
r->left=p;
else
insert_bst(r->left, p);
else
if(r->right==NULL)
r->right=p;
else
insert_bst(r->right, p);
}
bool search_bst(tree_node *r, int value) {
if(r)
{
if(r->info == value) {
del_bst(par, r);
return(true);
}
else if(value <r->info) {
par=r;
search_bst(r->left, value);
}
else {
par=r;
search_bst(r->right, value);
}
}
else
return(false);
}
void del_bst(tree_node *par, tree_node *p) {
if(par->left || par->right)
{
if(par->left==p)
if(p->left==NULL)
par->left=p->right;
else
par->left=p->left;
else
if(p->right)
par->right=p->right;
else
par->right=par->left;
}
else {
if(par->left==p)
par->left=NULL;
else
par->right=NULL;
}
if(par->left && par->right)
{
par=p;
p=p->right;
while(p)
{
par=p;
p=p->left;
}
}
}
ممنون میشوم راهنمایی کنید.