PDA

Просмотр полной версии : бинарные деревья



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

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

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

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

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

versus
16.11.2004, 12:17
нужно написать метод что получает бинарное дерево. метод возврощяет 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
16.11.2004, 14:14
а как граф задается?

chew
16.11.2004, 18:45
2 versus:

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

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

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

versus
16.11.2004, 23:48
2 versus:

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


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


int in_order(const Tree* t)
{
int node_sum = 0;

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

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

switch(node_sum)
{
case 2: // normal node with 2 childs; continue
return max(in_order(t->right_child), in_order(t->left_child));
case 1: // node have only 1 child; stop
return 1;
case 0: // leaf
return 0;
default:
printf("doh!");
}
}


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



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

log2(n) где n количество узлов в дереве, а log2(n+1)
верно! спасибо за поправку.

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

michael
16.11.2004, 23:58
VERSUS-а что это за метод max() втвоём втором коде?

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

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

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

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

versus
17.11.2004, 00:04
VERSUS-а что это за метод max() втвоём втором коде?

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



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

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

michael
17.11.2004, 00:11
не успел увидеть твоё последнее сообщение

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


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

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



class daClass
{
public static int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
}

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

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



А насчет O(log2(n)+1) или O(log2(n+1)) или O(log2(n)) то вроде они все равны O(log2(n))

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

michael
17.11.2004, 00:20
2 versus:

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

michael
17.11.2004, 00:23
Оптимизировал под джяву:

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
17.11.2004, 00:35
К сожалению результат так и остаётся 0. :(

versus
17.11.2004, 01:19
к сожалению не могу ничем помочь. Результат работы 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
17.11.2004, 11:23
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
17.11.2004, 13:06
тогда добавь в 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 (полное)

chew
17.11.2004, 13:36
Ниже приведён текст программы на C#.
Она подсчитывает кол-во вершин графа.

После получения этого числа надо использовать:
Теорема.
Бинарный граф явл. правильным тогда и только тогда,
когда кол-во его вершин равно 2**k-1,
где k - высота графа.
Док-во: почти очевидно :)

Если получено число 'N' и оно имеет такой вид, то граф правильный.
-------------------------------------------------------------------------------------
using System;

namespace chewProject1
{
public class BTree
{
public BTree v1;
public BTree v2;
public string nameNode;
public BTree(string name)
{
nameNode = name;
}

public static int CountNodes(BTree bTree)
{ // выдаёт кол-во вершин бинарного графа
// NB! рекурсивный метод!
int cnt=1; // текущая вершина

if ( (bTree.v1 != null) )
{// левая ветка
cnt += CountNodes(bTree.v1);
}
if ( (bTree.v2 != null) )
{// правая ветка
cnt += CountNodes(bTree.v2);
}

if ( (bTree.v1 == null) && (bTree.v2 == null) )
{// лист
return (1);
}
return (cnt);
}

public static void Main()
{
// заполняем дерево
BTree c1= new BTree("c1"); // лист
BTree c2= new BTree("c2"); // лист
BTree b1= new BTree("b1");
b1.v1 = c1;
b1.v2 = c2;
BTree d1= new BTree("d1"); // лист
BTree d2= new BTree("d2"); // лист
BTree b2= new BTree("b2");
b2.v1 = d1;
b2.v2 = d2;

BTree a1= new BTree("a1"); // корень
a1.v1 = b1;
a1.v2 = b2;

int n= BTree.CountNodes(a1);
Console.WriteLine("CountNodes: {0}", n);
// если n=2**k -1, то граф полный.
}
}
}
-------------------------------------------------------------------------------------

michael
17.11.2004, 15:14
kod horowiy. No nado v TOY je funkzie vi4isliat' visotu dereva.
Ya v ot4aenie :cry:

versus
17.11.2004, 15:14
> Бинарный граф явл. правильным тогда и только тогда,
> когда кол-во его вершин равно 2**k-1,

ну вот, я же сказал велосипед переизобретаем :)

michael
17.11.2004, 15:19
ya znaiu 4to 2**k-1 no problema 4to visotu ya doljen pods4itat' v toy je funkzie

versus
17.11.2004, 15:31
michael, ну тебе же уже все дали!
количество узлов посчитать можешь? ( Amount )
log2(от этого количества) посчитать можешь? ( Height )
сравнить количество узлов Amount с 2*Height - 1 можешь?
ну так в чем тогда проблема? в том что CountNodes рекурсивный? Так его легко можно переписать без рекурсии.

michael
20.11.2004, 12:49
spasibo -razorabralsia