Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
25.06.2007, 22:54
|
|||
|---|---|---|---|
|
|||
Ширина двоичного дерева |
|||
|
#18+
Необходимо подсчитать ширину двоичного дерева (под шириной уровня я понимаю число вершин дерева на данном уровне, а под шириной двоичного дерева максимальную ширину по всем уровням). Если кто знает и подскажет алгоритм решения такой задачи буду очень благодарен, а если у кого еще и код есть то будет просто восхитительно! спасибо за внимание. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
25.06.2007, 23:01
|
|||
|---|---|---|---|
Ширина двоичного дерева |
|||
|
#18+
Заводишь динамически растущий массив (вектор, список или что-то подобное). По достижению очередной ноды записываешь в соотвествующую ячейку массива (по уровню текущей ноды) количество детей этой ноды. Повторить для каждого из детей. В конце пробежаться по массиву и найти ячейку с максимальным значением. все. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.06.2007, 09:29
|
|||
|---|---|---|---|
|
|||
Ширина двоичного дерева |
|||
|
#18+
Насколько я помню, для нормализованного дерева эта вещь равняется чему-то вроде base ^ level (2^level)?! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
26.06.2007, 19:20
|
|||
|---|---|---|---|
|
|||
Ширина двоичного дерева |
|||
|
#18+
Рассматривается общий случай, т.е. когда дерево может быть не полным на любом из уровней, тогда речь может идти лишь о оценке сверху, что ширина не больше чем 2 ^ номер уровня, а необходимо найти точную ширину ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=57&tablet=1&tid=2028605]: |
0ms |
get settings: |
8ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
186ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
40ms |
get tp. blocked users: |
1ms |
| others: | 219ms |
| total: | 485ms |
| 0 / 0 |
