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

[versus]

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

просто максимум из двух чисел:
например так:

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

int max&#40]

[michael]

К сожалению литература молчит. Извини за мою тупость но что такое метод max() .кого я тут вызываю?
А насчет O(log2(n)+1) или O(log2(n+1)) или O(log2(n)) то вроде они все равны O(log2(n))

[michael]

не успел увидеть твоё последнее сообщение

[versus]

К сожалению литература молчит. Извини за мою тупость но что такое метод max() .кого я тут вызываю?

ну это функция обычная, просто мне в лом ее было писать %)
(вообще говоря эта лень оправдана, потому что MAX, если я не ошибаюсь реализуется в стандартной сишной библиотеки в виде простенького макроса, а уж в С++ она должны быть подавно... вся из себя параметризированная какая-нибудь)

если смущает Си, сейчас попробую сообразить пример на Java

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

class daClass
&#123]
ну и позвать его соответственно:
daClass.max(lalala, blablabla);

in_order переписывается на Java аналогичным образом %)

[quote]
А насчет O(log2(n)+1) или  O(log2(n+1)) или O(log2(n)) то вроде они все равны O(log2(n))
[/quote]
"O"-большое здесь не причем. Это для оценки сложности алгоритмов используется (в матане для оценки порядка функций). Мы же здесь говорим не про приблизительную оценку сверху, а про вполне определенное значение - высоту дерева. Все таки лучше поискать книжечку....

[michael]

2 versus:

Запустил твой код. Стобильно выдоёт 0.

[michael]

Оптимизировал под джяву:

int boolTree(Node node)
{
int node_sum = 0;

if (node.left!= null)
node_sum++;

if (node.right != null)
node_sum++;

switch(node_sum)
{
case 2: // normal node with 2 childs; continue
return max(boolTree(node.right), boolTree(node.left));
case 1: // node have only 1 child; stop
return -1;
case 0: // leaf
return 0;
default:
return 100;
}


}
int max(int a, int b)
{
return (a > b) ? a : b;
}

[michael]

К сожалению результат так и остаётся 0.

[versus]

к сожалению не могу ничем помочь. Результат работы in_order напрямую зависит от того как заполняется дерево.

пусть бинарным деревом будет дерево двоичного поиска (другой реализации не оказалось под рукой %))... в принципе это такое же бинарное дерево только с парой дополнительный свойств.

вход:
6, 3, 2, 1, 4

дерево:

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

       6
      / 
     3    
    / \      
  2    4
 /      
1       

выход: 1


вход:
6, 7, 2, 1, 4

дерево:

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

       6
      / \
     2   7
    / \      
  1    4 

выход: 0

Должно быть так. Проверил на своей программе - работает. А у вас?

ps: надеюсь никто не видел как я облажался с рисованием дерева?

[michael]

da no eto ne polnoe binarnoe derevo. V zadanie skazano 4to vse list'ya doljni bit' na odnoy visote.

(Izvinite 4to piwu ne na ruskom-ya sei4as na drugom komp. gde net podderjki)

[versus]

тогда добавь в in_order еще один параметр - level.

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

// вычисляем высоту дерева
int tree_height = eval_tree_height();

int in_order(const Node* t, int level)
{
  int node_sum = 0;
  level++;

  if (t->left != NULL)
    node_sum++;

  if (t->right != NULL)
    node_sum++;

  switch(node_sum)
    {
    case 2: // нормальный узел с двумя потомками
      return max(in_order(t->right, level), in_order(t->left, level));
    case 1: // узел с одним потомком
      return 1;
    case 0: // дошли до узла, проверить равен ли текущий 
               // уровень высоте дерева
      if (level != tree_height)
        return 1;
      else
        return 0;
    default:
      printf("doh!");
    }
}

зовешь in_order так:

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

in_order(tree, 0);

и получаем для

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

6, 7, 2, 1, 4

aka:
       6 
      / \ 
     2   7 
    / \      
  1    4

1 (неполное)

а для

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

5, 7, 6, 9, 2, 1, 3

aka:
      5
    /   \
   2     7
  / \    / \
 1   3 6   9

0 (полное)