бинарные деревья

[michael]

Помогите!
(для любителей мазохизма)
нужно написать метод что получает бинарное дерево. метод возврощяет 1 если дерево не полное (полное дерево=у каждого узла есть ровно 2 потомка (левый и правый)). если дерево полное возврощяет его (дерево) высоту

П.С 2дня мучаюсь. Выручай народ

[chew]

Хм, ...
А как мы будем интерпретировать результат, если высота
(кстати, уровень корня учитывается в определении высоты?)
дерева будет =1 ???
Лучше бы возвращать 0, если не полное.

Если ещё не написали алг., пришлю.

[michael]

буду премного благодарен. (монжно возвращять -1)

[versus]

нужно написать метод что получает бинарное дерево. метод возврощяет 1 если дерево не полное (полное дерево=у каждого узла есть ровно 2 потомка (левый и правый)).

если у каждого узла будет по два потомка, тогда дерево будет бесконечным! здесь надо поточнее сформулироваться!
а так это же тривиальнейший обход дерева (в ширину или в глубину это уж как хотите). у каждого узла надо спросить сколько у него потомков и если не два то вернуть 1 или чего там.

это правда не совсем Java, но принцип везде одинаков:

Код: Выделить всё

int in_order(const Tree* t)
{
  if (t->left_child != NULL) 
    in_order(t->left_child);
  else
    return 1;

  if (t->right_child != NULL)
    in_order(t->right_child);
  else
    return 1;
}

а высота бинарного дерева это log2(n) где n количество узлов в дереве.
количество узлов можно посчитать опять же обойдя дерево вглубь или в ширину... ну или где нибудь хранить это число.

или я чего-то не понял? %)

[Deady]

а как граф задается?

[chew]

2 versus:

1)

если у каждого узла будет по два потомка, тогда дерево будет бесконечным!

Замечание справедливое! Очевидно, предполагается, что у каждого НЕ ЛИСТА, может быть
не более двух потомков.

2) поправочка: НЕ

log2(n) где n количество узлов в дереве

, а log2(n+1)

[versus]

2 versus:

1)

если у каждого узла будет по два потомка, тогда дерево будет бесконечным!

Замечание справедливое! Очевидно, предполагается, что у каждого НЕ ЛИСТА, может быть
не более двух потомков.

ну тогда чуть-чeть поправить in_order введением одной пременной...
что-то типа такого?

Код: Выделить всё

int in_order&#40]

in_order вернет 1 для "неполного" дерева и 0 для таки полного.

[quote]
2) поправочка: НЕ  
[quote]log2(n) где n количество узлов в дереве[/quote], а log2(n+1)[/quote]
верно! спасибо за поправку.

[michael]

Ребята! Вношу поправку. Конечно у листьев нет детей. И да у каждого узла, что не лист есть 2 ребёнка, но проблема не в этом, а в том что нужно доказать что дерево ПОЛНОЕ т.е. все листья находятся на одной высоте. Если дерево не полное нужно вернуть -1 а если полное то нужно вернуть высоту дерево.
Пройтись по дереву конечно елементарно, но вот пройтись так что бы сосчитать требуемое я как то не додумался. Поетому прошу помощи.
VERSUS по с++ я не спец , но помоему твой код вернёт 1 в любом случае. Извини и поправь если не так.

[michael]

VERSUS-а что это за метод max() втвоём втором коде?

[versus]

VERSUS по с++ я не спец , но помоему твой код вернёт 1 в любом случае. Извини и поправь если не так.

попробуй на листочке нарисовать, посмотреть что получится.
если в дереве есть хотя бы один узел с одним ребенком то как бы глубого этот узел не находился за счет max() в конце концов вернется 1.
если нигде в дереве такого узла не нашлось, то для каждого узла будет возвращаться 0.

алгоритм усложняется, я начинаю сомневатся в его корректности и что более важно - оптимальности. а в книгах про это ничего не говорят? ведь наверняка переизобретаем велосипед!

как посчитать требуемое я честно говоря тоже не знаю, не проще ли сначала убедится в полноте дерева, а потом сказать заветное log2(n)+1 ?