2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Двоичные деревья
Сообщение14.12.2011, 21:54 
Добрый!
Помогите пожалуйста сделать задание,все мозги сделал себе
Нужно описать 2 процедуры,одну рекурсивно ,другую нет
1)Найти сумму значений внутренних узлов дерева
2)Определить адрес узла дерева с заданным значением

 
 
 
 Re: Двоичные деревья
Сообщение14.12.2011, 22:44 
А с какой процедурой и каким пунктом больше проблем?

 
 
 
 Re: Двоичные деревья
Сообщение14.12.2011, 23:06 
с двумя :D
на самом деле, если бы в первом задании было,найти сумму всех значений дерева,то не так страшно, а вот сумму внутренних узлов то, не со всем понимаю, как их(внутренние узлы) считать...
во втором, если честно, не понимаю вообще что от меня хотят....
т.е. примерно так создаю дерево,потом ввожу число которое нужно сравнить,ищу такой же элемент в дереве,если да, то что я должен вернуть?или показать?

 
 
 
 Re: Двоичные деревья
Сообщение14.12.2011, 23:23 
Подразумевается, что к листям дерева привязаны значения. Значит, числовые, раз просят сумму. :-) Если подразумеваете под внутренними узлами те, в которых дерево ветвится, то вроде бы обычно к ним не приклеивают значения. Но иногда и такое дерево нужно. Скорее всего, первое, но вы поглядите, как у вас описывается структура узла.

Во втором, думаю, вам не нужно писать программу, а только функцию, и возвращать указатель на запись узла дерева.

Ещё интересуют язык и совершенно любые, хоть словами, наработки. :-)

P. S. Извиняюсь, не дочитал. Ну, если нужно считать сумму значений внутренних узлов, значит, к ним как раз прикреплены значения, а на листья плевать. Ну так вы проверяйте, попали ли в лист, и в этом случае не добавляйте его число в сумму. Так и накопится по всем внутренним узлам.

 
 
 
 Re: Двоичные деревья
Сообщение15.12.2011, 12:37 
Определить адрес узла дерева с заданным значением
таким образом?
Код:
function adress(Tree:plist;x:integer):plist; {Возвращаем адрес искомого элемента, nil если не найден}
var
p:plist;   {вспомогательная переменнная }
begin
  if Tree=nil then   {если дерево пустое то}
     begin
       adress:=nil;  {присваеваем функции результат нил}
       exit; {и выходим }
     end;
  if x=Tree^.data then  {если искомый элемент равен корню дерева то }
    p:=Tree  {запоминаем его адрес }
     else   {иначе}
       if x < Tree^.data then {если вводимый элемент менньше корня то }
          p:=adress(Tree^.left,x) {то ищем его в левом поддереве}
       else     {иначе }
         p:=adress(Tree^.right,x);  {ищем в правом поддереве }
  adress:=p; {присваеваем переменной с именем фугкции результат работы}
end;

 
 
 
 Re: Двоичные деревья
Сообщение15.12.2011, 15:30 
Всё верно, если какую-нибудь деталь не пропустил. :-)

Ага, можно обойтись без p. Pascal отличается от C тем, что при присваивании результата немедленного выхода из функции не происходит, пока мы явно не вызовем Exit. Так что промежуточная переменная избыточна.

 
 
 
 Re: Двоичные деревья
Сообщение15.12.2011, 16:41 
arseniiv
ага,хорошо!
Блин чё-то не пойму, а как проверить попал я в лист или нет?

 
 
 
 Re: Двоичные деревья
Сообщение15.12.2011, 16:50 
Из листа не выходит никаких поддеревьев: и слева, и справа nil.

 
 
 
 Re: Двоичные деревья
Сообщение15.12.2011, 22:59 
arseniiv
т.е. примерно так? если Tree^.left=nil and Tree^.right =nil then
проходим дальше
иначе
накапливаем сумму

 
 
 
 Re: Двоичные деревья
Сообщение16.12.2011, 10:31 
Ага!

 
 
 
 Re: Двоичные деревья
Сообщение26.12.2011, 21:34 
arseniiv
Добрый вечер!Извините что опять вам пишу,возникли проблемы с Определением адреса узла дерева с заданным значением,сделал так как я писал,вызвал результат фукнции а мне выводит не понятно что,типа $2D0F20

 
 
 
 Re: Двоичные деревья
Сообщение26.12.2011, 21:44 
Здравствуйте! А что именно выводит?

 
 
 
 Re: Двоичные деревья
Сообщение26.12.2011, 21:48 
arseniiv
создаю дерево например количество элементов =5,ввожу 1 2 3 4 5, поиск по значению беру равным 5,а мне выводит $2D0F20

 
 
 
 Re: Двоичные деревья
Сообщение26.12.2011, 21:51 
Ну правильно. Функция возвращает, как и прошено, указатель (= адрес). А что имелось в виду?

Я забыл, что это дерево представляет упорядоченный список. Если нужна была позиция в представляемом им списке, тогда надо подумать…

Вы храните сбалансированное (АВЛ-) дерево или как уж построилось?

-- Вт дек 27, 2011 00:54:34 --

Или я чепуху горожу. Если мы пойдём поиском в ширину по нашему дереву, то, разумеется, будем перечислять элементы по неубыванию. Тогда как только нашли данный, надо вернуть, сколько элементов мы уже до этого насчитали.

Знаете поиск в ширину? :-)

 
 
 
 Re: Двоичные деревья
Сообщение26.12.2011, 21:58 
arseniiv
Если честно то не совсем и понятно из задания то что нужно,нужно правда вернуть указатель а не позицию,хотя не уверен
создается и обычное дерево и сбалансированное

-- 26.12.2011, 21:58 --

не знаю

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group