Двоичные деревья

[denis_stell]

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

[arseniiv]

А с какой процедурой и каким пунктом больше проблем?

[denis_stell]

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

[arseniiv]

Подразумевается, что к листям дерева привязаны значения. Значит, числовые, раз просят сумму. Если подразумеваете под внутренними узлами те, в которых дерево ветвится, то вроде бы обычно к ним не приклеивают значения. Но иногда и такое дерево нужно. Скорее всего, первое, но вы поглядите, как у вас описывается структура узла.

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

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

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

[denis_stell]

Определить адрес узла дерева с заданным значением
таким образом?

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;

[arseniiv]

Всё верно, если какую-нибудь деталь не пропустил.

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

[denis_stell]

arseniiv
ага,хорошо!
Блин чё-то не пойму, а как проверить попал я в лист или нет?

[arseniiv]

Из листа не выходит никаких поддеревьев: и слева, и справа nil.

[denis_stell]

arseniiv
т.е. примерно так? если Tree^.left=nil and Tree^.right =nil then
проходим дальше
иначе
накапливаем сумму

[arseniiv]

Ага!

[denis_stell]

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

[arseniiv]

Здравствуйте! А что именно выводит?

[denis_stell]

arseniiv
создаю дерево например количество элементов =5,ввожу 1 2 3 4 5, поиск по значению беру равным 5,а мне выводит $2D0F20

[arseniiv]

Ну правильно. Функция возвращает, как и прошено, указатель (= адрес). А что имелось в виду?

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

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

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

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

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

[denis_stell]

arseniiv
Если честно то не совсем и понятно из задания то что нужно,нужно правда вернуть указатель а не позицию,хотя не уверен
создается и обычное дерево и сбалансированное

-- 26.12.2011, 21:58 --

не знаю