:
1) , . . ( ) . . , :
struct Data
{
int a;
};
2) , :
struct Tree
{
Data d;
Tree *left;
Tree *right;
};
:
left ;
right .
( main() ).
( main()) :
Tree *u = 0;
, 0.
, . .
. : 10, 25, 20, 6, 21, 8, 1, 30. . .
. 10. . 25. , 25 . 20 10, 25, , 25. . , :
. u .
1. :
void Add(Tree **u, Data &x)
{
Tree *p = *u;
if(p == 0)
{ // -
p = new Tree;
p->d.a = x.a;
p->left = 0;
p->right = 0;
*u = p;
return;
}
Tree *p1;
bool priznak = false; // ,
while(p &&!priznak)
{
p1 = p;
if(x.a == p->d.a)
priznak = true;
else
if(x.a < p->d.a)
p = p->left;
else
p = p->right;
}
if(priznak) return;
//
Tree *pnew = new Tree;
pnew->d.a = x.a;
pnew->left = 0;
pnew->right = 0;
if(x.a < p1->d.a) //
p1->left = pnew;
else //
p1->right = pnew;
}
:
Add(&u, x);
x Data.
. x ( ).
2. ( ) :
void Print(Tree *u)
{
if(u)
{
Print(u->left);
cout << u->d.a << endl;
Print(u->right);
}
}
:
Print(u);
3. , :
Tree* Find(Tree *u, Data &x, Tree **prev)
|
|
|
{
Tree *p = u;
*prev = 0;
// -
if(p == 0)
return 0;
//
while(p)
{
//cout << "Find: " << p->d.a << endl;
if(p->d.a == x.a) //
return p;
if(p->d.a > x.a) //
{
*prev = p;
p = p->left;
}
else//
{
*prev = p;
p = p->right;
}
}
// -
*prev = 0;
return 0;
}
:
Tree *p = Find(u, x, &p0);
( , 0).
- p0 . , p0=0. x, Data.
4. :
void Delete(Tree **u, Data &x)
{
Tree *p0 = 0;
Tree *p = Find(*u, x, &p0);
// -
if(p == 0)
return;
// -
if(p0 == 0 && (p->left == 0 || p->right == 0))
{
if(p->left == 0 && p->right == 0)
*u = 0;
else if(p->left == 0)
*u = p->right;
else
*u = p->left;
delete p;
return;
}
// -
if(p->left == 0 && p->right == 0)
{
if(p0)
{
if(p0->left == p)
p0->left = 0;
else
p0->right = 0;
}
else// !
u = 0;
delete p;
return;
}
// - ,
if(p->left!= 0 && p->right == 0)
{
if(p0->left == p)
p0->left = p->left;
else
p0->right = p->left;
delete p;
return;
}
// - ,
if(p->left == 0 && p->right!= 0)
{
if(p0->left == p)
p0->left = p->right;
else
p0->right = p->right;
delete p;
return;
}
//
if(p->left!= 0 && p->right!= 0)
{
p0 = p;
Tree *t = p->left;
while(t->right)
{
p0 = t;
t = t->right;
}
p->d.a = t->d.a;
if(p0->left == t)
p0->left = 0;
else
p0->right = 0;
delete t;
}
}
:
Delete(&u, x);
x Data.
Delete() Find() . Delete() Find() p0 , .
5. ()
, , . , . :
//
void Clear(Tree **u)
{
if(*u == 0) return;
Clear1(u);
cout << "delete (*u)->d.a=" << (*u)->d.a << endl;
delete *u;
*u=0;
}
void Clear1(Tree **u0)
{
Tree *t;
Tree *u = *u0;
if(u->left!= 0)
{
if(u->left->left!= 0 || u->left->right!= 0)
Clear1(&(u->left));
|
|
|
if(u->left->left == 0 && u->left->right == 0)
{
cout << "delete u->left->d.a=" << u->left->d.a << endl;
t = u->left;
delete t;
u->left = 0;
}
}
if(u->right!= 0)
{
if(u->right->left!= 0 || u->right->right!= 0)
Clear1(&(u->right));
if(u->right->left == 0 && u->right->right == 0)
{
cout << "delete u->right->d.a=" << u->right->d.a << endl;
t = u->right;
delete t;
u->right = 0;
}
}
}
:
Clear(&u);
Clear() Clear1(), , . Clear().
Clear() - . Clear1() .
, Clear1() : u->left? , , , . u->left , , , .. Clear1() . u->right. , , Clear().
Clear() Clear1() . : 10, 25, 20, 6, 21, 8, 1, 30, :
delete u->left->d.a=1
delete u->right->d.a=8
delete u->left->d.a=6
delete u->right->d.a=21
delete u->left->d.a=20
delete u->right->d.a=30
delete u->right->d.a=25
delete (*u)->d.a=10
.
