Кто нибудь напишите, пожалуйста, как выглядит функция с помощью которой можно найти прошлого и следущего соседа какой нибудь вершины. Если можно то хотя бы в inorder, пожалуйста :((( 

CrystalNoir, ты ничего не сказал про тип дерева, его структуру и т.д.
Задай полный вопрос, а не обрывок.

CrystalNoir, что такое inorder?

дерево классического вида (значение+ссылки на листья) позволяет вершине иметь в ближнем доступе только листья, то есть связанные с ней вершины, расположенные ниже по иерархии. Чтобы получить "соседей", придётся от корня поиском добраться до вершины, имеющей данную в качестве листа (если только дерево не реализовано по-другому).

JackYF, 

извините - забыла :(( .. Это бинарное дерево. Например такое:
-----4
---/---\
--2----6
-/-\---/-\
1--3-5--7

Соседи корня 4 - это не 2 и 6, а 3 и 5. Но в то же время соседи вершины 2 - это 1 и 3. Как  можно найти соседей каждой вершины в инордер порядке? :((((((

marcusmae, 

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

Помогите, пожалуйста, разобраться с нахождением соседей в инордере на С++ или С :(((

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



- такова ли структура Вашего дерева?

marcusmae, я может не правильно высказалась.. 
Соседями (siblings) для данной вершины в бинарном дереве являются не самый правый лист левого поддерева и самый левый лист правого поддерева, а последняя обойденная вершина и следущая, которую надо обойти в inorder.


Именно эти два примера я написала для того чтоб была видна разница, если у 2 соседи 1 и 3, то это не значит что у всех вершин соседи будут две вершины на уровень ниже, потому что ниже, например, той же вершины 4 ее дети 2 и 6, а надо найти предыдущего и следущего соседей в инордер порядке и у 4 они будут 3 и 5, потому что если смотреть на приведенное в пример дерево, то в инордер его обходят так: 1234567, получается что сосед каждой нужной вершины слево и с право.


да, идея дерева такая, только записана с классом, но это ничего, со структурой пример я бы тоже поняла.. 
Я просто ОЧЕНЬ хочу узнать, как найти этих соседей инордер обходом :((((((
ПОЖАЛУЙСТА помогите :((

CrystalNoir, я пытаюсь интерпретировать Ваше определение, потому что оно непонятно. Моя трактовка с левейшим и правейшим в поддеревьях НЕ является неправильной по крайней мере для тех двух примеров, что Вы приводите. Вот код :



Нехитрой парой циклов получаем искомые пары 3 и 5 для большого дерева и 1 и 3 - для левого поддерева. Здесь нет никакого обхода (он не нужен, вообще-то), но я готов его сделать, если вы объясните принцип обхода не на примере, а в общем. Последний Ваш пост не содержит дополнительных объяснений на этот счёт  

Это сообщение отредактировал(а) marcusmae - 23.11.2007, 22:24

Ты знаешь, по твоему описанию это одно и тоже получается   
Если полный обход твоего дерева в inorder это 1,2,3,4,5,6,7. То marcusmae понял тебя правильно и написал все верно.

marcusmae, спасибо Вам за ответ! Но если дерево будет в два или три раза глубже, то левейший лист с помощью GetLeftestLeaf(tree->left->right)->value не найдется..

Принцип работы инордер обхода: идти влево до самого левого листа - запомнить этот лист, поднятся на уровень выше к вершине-родителю левого листа - запомнить ее, спуститься вниз к правому листу - запомнить. Подняться опять к вершине-родителю - не запоминать. Поднятся к родителю родителя-запомнить -> спуститься в право-низ и там в таком порядке все обойти. Получается что то на подобии  левый лист-вершина-правый лист.

(A+5)*B-2*E , в этом примере сначала идет (A+5), потом это умножается на B, затем 2*E и от первого отнимают второе. Это смысл инордера, деревом это можно записать как:

-----------   -
---------- /----\
-------- *------ *
-------/---\-----/--\
----- + --  B--2---E
----/--\
---A---5


SaDFromSpb,  я не говорю что неправильно, правильно конечно, просто деревья могут быть даны абсолютно разные, с разными значениями(values). Как бы  сделать чтоб не только на конкретный пример функция работала, а на любой произвольный.. :(((((

Это сообщение отредактировал(а) CrystalNoir - 24.11.2007, 16:50

Ага, ясно.

Ну, вот, можно рекурсией :



Проверьте. Сейчас придумаю, как вывести соседей.

Это сообщение отредактировал(а) marcusmae - 23.11.2007, 23:28

marcusmae, спасибо за рекурсию! я ее проверила - выводит все вершины в инордер порядке!


пожалуйста, напишите :((((((

Вот какой мой окончательный вариант :



Это сообщение отредактировал(а) marcusmae - 24.11.2007, 00:17

marcusmae, спасибо большое! Вы мне очень помогли! ))))

О, замечательно! Желаю успехов  

CrystalNoir, пометьте тему решённой тогда