Задача с бинарным деревом

[vadimpirov]

Здравствуйте! Подскажите пожалуйста как реализовать следующее, можно только более-менее подробный алгоритм, код сам постараюсь написать

Условие

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

@темы: Вопрос, C++, Алгоритм

Comments

[mr Gray]

ИМХО рекурсией будет очень удобно. Первый вызов обрабатывает обоих потомков корня (делает вызов самого себя для этих потомков). Второй вызов обрабатывает потомков этих потомков и т.д, пока не встретим то, что искали. Когда встретили то, что искали - смотрим - если глубина меньше сохраненной, то сохраняем эту глубину и соответствующую ветвь и продолжаем поиск, т.к. можем встретить более близкую от корня ветку. Ну а для обратного раскручивания пути нужно запоминать в очереди цепочку узлов до текущего - при переходе к новому узлу добавлять его, а при возврате - удалять.

Если не совсем поняли - скажите - напишу, как должна выглядеть эта функция.

[mr Gray]

Есть еще один способ: создаем очередь (каждый элемент очереди будет содержать ссылку на элемент дерева и расстояние от вершины). Сначала пишем в нее 2 потомка корня. Теперь очередь состоит из 2-ух элементов. Начинаем идти с левого края очереди. Для каждого встреченного элемента пишем его потомков в конец очереди (их расстояние от корня будет на единицу больше, чем у родителя). И т.д., пока не найдем нужный. Он будет и ближайшим. ИМХО, так даже удобнее, чем рекурсией.

Поиск пути от корня до найденного элемента нужно делать с конца - то есть от найденного элемента. Ищем родителя найденного элемента среди элеменов очереди с расстоянием от коня на единицу меньше и т.д., пока не придем к вершине дерева.

Опять таки - если не совсем понятно - пишите - уточню.

[vadimpirov]

mr Gray
Большое спасибо!! Постараюсь разобраться, распечатаю, возьму с собой на работу, будет что непонятно обязательно обращусь! Спасибо..

[vadimpirov]

ИМХО рекурсией будет очень удобно. Первый вызов обрабатывает обоих потомков корня (делает вызов самого себя для этих потомков). Второй вызов обрабатывает потомков этих потомков и т.д, пока не встретим то, что искали. Когда встретили то, что искали - смотрим - если глубина меньше сохраненной, то сохраняем эту глубину и соответствующую ветвь и продолжаем поиск, т.к. можем встретить более близкую от корня ветку. Ну а для обратного раскручивания пути нужно запоминать в очереди цепочку узлов до текущего - при переходе к новому узлу добавлять его, а при возврате - удалять.

смысл понятен, а вот как реализовать, не ясно. С таким еще не сталкивался.. не могли бы подсказать? если конечно есть время


2ой вариант более прозрачен, только вот

Поиск пути от корня до найденного элемента нужно делать с конца - то есть от найденного элемента. Ищем родителя найденного элемента среди элеменов очереди с расстоянием от коня на единицу меньше и т.д., пока не придем к вершине дерева.

это не совсем понятно..


Ищем родителя найденного элемента среди элеменов очереди с расстоянием от коня на единицу меньше

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

правильно понял?

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

[mr Gray]

правильно понял?

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

Схематично функция рекурсии для первого способа будет выглядеть так:

TElement Сохраненнтый_путь[];

void Element(TElement Элемент, int Глубина)
{
  Сохраненный_путь = сохраненный_путь + Элемент;  

  if ((Элемент == искомый_элемент) && (Глубина<Сохраненная_глабина))
  {
    Сохраненны_элемент=Элемент;
    Сохраненная_глабина=Глубина;
    Сохраненный_путь тоже сохраняем;
    return;
  };

  for (i=0; i<2; i++)
    Element(Элемент.Потомок[i], Глубина+1);  //продвигаемся вперед по дереву

  Сохраненный путь = сохраненный путь - Элемент;  
}

[vadimpirov]

Здравствуйте! все еще разбираюсь.. решаю вторым вариантом

вопрос

...(каждый элемент очереди будет содержать ссылку на элемент дерева и расстояние от вершины).

сделал так

struct NodeData
{
void *p;
int glub;
};


еще

deque < NodeData > NodeSpisokStack;

//добавляем в очередь указатель на элемент дерева и его растояние от вершины
void AddtoDeque(void *node, int glubina)
{
//if (node != NULL)
// exit;
NodeData *sp;
sp = new NodeData;
sp->glub = glubina;
sp->p = node;
NodeSpisokStack.push_back(*sp);
}

а как по ссылке на элемент дерева, получить его свойства (данные)??

struct Node // узел бинарного списка
{
Node* Left; // указатель на лево
Node* Right; // указатель на право
void* Data; // данные


которые используются для заполнения очереди. или нужно пройтись по дереву ища элемент с сохраненной ссылкой
NodeData(NodeSpisokStack.back()).p

ответьте пожалуйста.

[mr Gray]

Вот так можно реализовать второй алгоритм: http://paste.org.ru/?tuxfb0
Программа создает бинарное дерево. Корень - 1. Второй уровень: 11 и 12. У 11 есть потомки: 111 и 112 и т.д.

[vadimpirov]

mr Gray Большое Вам спасибо!
видно нету профессию я выбрал, или на заочке с этим в одиночку не справится..