:
() ;
;
, , ;
;
.
, .. , , .
, 17, 18, 6, 5, 9, 23, 12, 7, 8, :
, . , , (Tree->info) (b). b < info, , . , , , .
11:
, , :
Tree* Make(Tree *Root) {
Tree *Prev, *t; // Prev ()
int b, find;
if (Root == NULL) { //
printf("\n Input Root: ");
scanf(%d, &b);
Root = List(b); //
}
//================ =================
while(1) {
printf("\n Input Info: "); scanf(%d, &b);
if (b<0) break; // < 0
t = Root; //
find = 0; //
while (t &&! find) {
Prev = t;
if(b == t->info)
find = 1; //
else
if (b < t -> info) t = t -> Left;
else t = t -> Right;
}
if (!find) { // Prev
t = List(b); //
if (b < Prev -> info) // ,
Prev -> Left = t; // ,
else Prev -> Right = t; //
}
} //
return Root;
}
List :
Tree* List(int i) {
Tree *t = (Tree*) malloc (sizeof(Tree));
t -> info = i;
t -> Left = t -> Right = NULL;
return t;
}
Create :
¼
struct Tree { //
int info;
Tree *Left, *Right;
};
void main()
{
Tree *Root = NULL; //
¼
Root = Make(Root);
¼
, () .
1. . key:
|
|
|
2. , .. . key, :
3. , , . key , w, ( , Right NULL) , ( , Left NULL) .
, w, key, :
key (6). , .. w ( Left NULL):
key
Tree* Del(Tree *Root, int key) {
Tree *Del, *Prev_Del, *R, *Prev_R;
// Del, Prev _ Del ();
// R, Prev _ R , , ;
Del = Root;
Prev_Del = NULL;
// ===== key =====
while (Del!= NULL && Del -> info!= key) {
Prev_Del = Del;
if (Del->info > key) Del = Del->Left;
else Del = Del->Right;
}
if (Del == NULL) { //
puts("\n NO Key!");
return Root;
}
// ============ R =================
if (Del -> Right == NULL) R = Del->Left;
else
if (Del -> Left == NULL) R = Del->Right;
else {
//
Prev_R = Del;
R = Del->Left;
while (R->Right!= NULL) {
Prev_R = R;
R = R->Right;
}
// R Prev _ R
if(Prev_R == Del)
R->Right = Del->Right;
else {
R->Right = Del->Right;
Prev_R->Right = R->Left;
R->Left = Prev_R;
}
}
if (Del== Root) Root = R; // , R
else
// R
if (Del->info < Prev_Del->info) Prev_Del->Left = R; //
else Prev_Del->Right = R; //
printf("\n Delete element %d \n", Del->info);
free(Del);
return Root;
}
¼
printf("\n Input Del Info: ");
scanf(%d, &key);
Root = Del(Root, key);
¼
, .
1. : Left-Root-Right ( , , , ).
2. : Root-Left-Right ( ).
3. : Left-Right-Root ( ).
, .
. + . , + , , + .
|
|
|
, + * . , +( * ). , , : +( *).
( *): *+.
, + * *+, +* .
: ((a + b / c)*(d e * f)). :
, ;
-, .
1 (Left-Root-Right) ( ):
a + b / c * d e * f.
2 (Root-Left-Right) ( ):
* + a / b c d * e f.
3 (Left-Right-Root) :
a b c / + d e f * *.
() , 2.
void View (Tree *t, int level) {
if (t) {
View (t -> Right, level+1); //
for (int i=0; i<level; i++) printf(" ");
printf( %d\n, t -> info);
View(t -> Left, level+1); //
}
}
View View(Root, 0);
View , , , (level) . 0. , . , . , .
10 (), 25, 20, 6, 21, 8, 1, 30, , View :
, , View
void Del_All(Tree *t) {
if (t!= NULL) {
Del_All (t -> Left);
Del_All (t -> Right);
free(t);
}
}
