Добрый день. Есть задача найти ширину левого поддерева. Что такое дерево и как оно работает - худо-бедно разобрался.. Но вот, как найти его ширину - увы, не знаю и не представляю, как это делать от слова - вовсе. Это код из книжки, вроде бы понимаю его..
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <iostream>
using namespace std;
struct node // описание узла
{
int info; // информационное поле
node *left; // указатель на левое поддерево
node *right; // указатель на правое поддерево
};
node * create(int d) // формирование нового элемента дерева
{
node *p = new node; // выделение памяти под новый узел
p->info = d;
p->left = NULL; // слева нет потомков
p->right = NULL; // справа нет потомков
return p;
}
void insert(node **p, int d) // добавление узла в дерево поиска
{
if (*p == NULL) *p = create(d);
else
{
if (d<(*p)->info)//если d меньше значения в узле - идем влево
// если там нет узла - создаем
if (&(*p)->left == NULL) (*p)->left = create(d);
else //если узел есть, вызываем вставку в левую ветвь
insert(&(*p)->left, d);
if (d>(*p)->info)//если d больше значения в узле, идем вправо
//если там нет узла – создаем новый узел
if (&(*p)->right == NULL) (*p)->right = create(d);
else //если узел есть, вызываем вставку в правую ветвь
insert(&(*p)->right, d);
}
}
// распечатка дерева в симметричном порядке
void printsim(const node * p)
{
if (p != NULL) // если дерево не пусто
{
printsim(p->left); // печатаем левое поддерево
cout << p->info << " "; // печатаем значение текущего узла
printsim(p->right); // печатаем правое поддерево
}
}
// распечатка дерева в прямом порядке
void printpr(const node * p)
{
if (p != NULL) // если дерево не пусто
{
cout << p->info << " "; // печатаем значение текущего
printpr(p->left); // печатаем левое поддерево
printpr(p->right); // печатаем правое поддерево
}
}
// распечатка дерева в обратном порядке
void printobrat(const node * p)
{
if (p != NULL) // если дерево не пусто
{
printobrat(p->left); // печатаем левое поддерево
printobrat(p->right); // печатаем правое поддерево
cout << p->info << " "; // печатаем значение текущего
}
}
void clear(node **p) // очистка дерева
{
if ((*p) != NULL) // если дерево не пусто
{
clear(&(*p)->left); // удаляем левое поддерево
clear(&(*p)->right); // удаляем правое поддерево
delete *p; //Удаляем указатель на текущий узел
*p = NULL;//Присваиваем ему пустой указатель
}
} |
|
(
