Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Turbo Pascal]Вычисление ср.высоты двоичн.дерева 
:(
    Опции темы
BCworm
Дата 29.7.2008, 03:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 23.8.2007

Репутация: нет
Всего: нет
Приветствую!.  
Прошу помощи в написании функции для вычисления средней высоты бинарного дерева. (Я уже поднимал тему про деревья на ветке про паскаль но её закрыли за оффтоп причем не мой  smile ).
Порыв гугль удалось найти чужой код для вычисления средней высоты. Но для правильной работы функции нужна функция (вычисляющая сумму длин ветвей на каждом уровне дерева

Код

function AVsize(t:tTree; Level: integer):integer
if t=nil then
AVsize:=0
Else Avsize:=Level+AVsize(t.left, Level+1)+AVsize(t.right, Level+1)
End;


Судя по всему он написан по псевдокоду. Явно есть недоработки. Помогите пожалуйста уже неделю мучаюсь  smile 
PM MAIL   Вверх
volvo877
Дата 29.7.2008, 08:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 34
Всего: 116
Ну, напиши вот так:
Код
procedure AvSize(level: integer; Root: TTree; var leafs, s: Integer);
begin
  if Root <> nil then begin
    AvSize(level + 1, Root^.Left, leafs, s);
    if (Root^.Left = nil) and (Root^.Right = nil) then begin
      Inc(leafs); Inc(s, level);
    end;
    AvSize(level + 1, Root^.Right, leafs, s)
  end
end;

...
{ Вызывать: }
leafs := 0; s := 0;
AvSize(1, myTree, leafs, s); { <--- Считаем, что корень - первый уровень дерева }
...


На выходе получишь количество листьев дерева и суммарную длину путей до каждого из них. Все что останется - поделить S на leafs (если leafs <> 0, разумеется smile )
PM MAIL   Вверх
BCworm
Дата 30.7.2008, 08:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 23.8.2007

Репутация: нет
Всего: нет
Спасибо большое!.
Вроде бы сдвинулось! я пока не закончил с этим заданием если можно пусть тема пока побудет открытой.


Это сообщение отредактировал(а) BCworm - 30.7.2008, 09:22
PM MAIL   Вверх
BCworm
Дата 30.7.2008, 09:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 23.8.2007

Репутация: нет
Всего: нет
Вот что я только что нашел!

...Для определения средней высоты дерева понадобится функция вычисления суммы длин путей от корня до каждой вершины на L-том уровне.

Псевдокод алгоритма
TreeAvSize (p: pVertex; L: -level)
IF (p = NIL) TreeAvSize:= 0
ELSE TreeAvSize:= L + TreeAvSize(p Left, L+1) + TreeAvSize(p Right, L+1)
FI

Тогда средняя высота вычисляется следующим образом
Ср высота дерева := TreeAvSize(Root, 1)/ TreeSize(Root) 

Тут получается что среднюю высоту дерева нужно поделить на размер. т.е на количество элементов? Кстати это кажется тот самый псевдокод по которому написан тот код который я показывал вначале. Кажется я опять запутался. На что делить то на количество листов -т.е на те узлы которые не имеют потомков или на количество узлов в общем т.е на количество элементов.
PM MAIL   Вверх
volvo877
Дата 30.7.2008, 09:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 34
Всего: 116
Цитата(BCworm @  30.7.2008,  09:37 Найти цитируемый пост)
Тогда средняя высота вычисляется следующим образом
Ср высота дерева := TreeAvSize(Root, 1)/ TreeSize(Root) 

Тут получается что среднюю высоту дерева нужно поделить на размер. т.е на количество элементов?

Ты других-то не путай! Тебе ясно сказали, что для того чтобы найти среднюю высоту дерева, нужно сумму высот (другими словами - длин путей от корня до листа) всех листьев разделить на их количество (листьев, разумеется). Нет, ты опять начинаешь находить какой-то бред: "чтобы найти среднюю высоту надо среднюю высоту поделить..." Ты нашел ее, чтобы делить?
PM MAIL   Вверх
BCworm
Дата 1.8.2008, 03:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 23.8.2007

Репутация: нет
Всего: нет
Ок все! Дошло!
volvo877 - Большое спасибо!

Цитата(volvo877 @  30.7.2008,  09:47 Найти цитируемый пост)
Ты других-то не путай! Тебе ясно сказали, что для того чтобы найти среднюю высоту дерева, нужно сумму высот (другими словами - длин путей от корня до листа) всех листьев разделить на их количество (листьев, разумеется). Нет, ты опять начинаешь находить какой-то бред: "чтобы найти среднюю высоту надо среднюю высоту поделить..." Ты нашел ее, чтобы делить? 


А что делать если в одном месте написано так в другом эдак а в третьем вообще что то  в роде 
... построить двоичное дерево достаточно просто, настолько просто что мы даже не будем объяснять что это такое и как его построить. Вот  и возникает кипа вопросов без ответа.


Сейчас пробую заполнять дерево генератором. Опять же все элементарно, все получается но почемуто после заполнения дерева не срабатывает процедура вычисления характеристик а сразу осуществляется переход к началу программы. В принципе так и должно быть но в коде есть строчка readln котороя подразумевает что нужно дождаться нажатия клавиши а происходит чтото вроде перескакивания через команду.

Код

procedure RndVVod;
begin
writeln('Vvedite kolichestvo elementov');
read(z); 
randomize;
for i:=1 to z do
InsTree(Root,Random(100-50));
End;


Все функции вычисления характеристик работаю отлично при заполнении вручную, при заполнении заранее заданными значениями. Все это собрано в одну процедуру которая выполняется после создания дерева одним из способов. А вот после процедуры создания генератором почемуто происходит перепрыгивание сразу на начало программы. Хотя по тексту сначало должна выполниться процедура вычисления характеристик а затем ожидание нажатия кнопки press any key...
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0467 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.