Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск элемента в НЕдвоичном дереве

Автор: sapphiro 20.5.2007, 16:53

Че то вот я не знаю...
Как найти элемент в двоичном(бинарном) дереве я знаю: рекурсия налево, рекурсия направо - 2строчки. А как найти элемент в НЕдвоичном дереве (у которого может быть куча потомков одного уровня, т.е из элемента исходят не два, а от 0 до бесконечности), вроде как надо в цикле перебирать массив указателей или я ошибаюсь?? Подскажите че-нибудь...!!!
см. рисунок дерева

Автор: Bitter 21.5.2007, 02:13

Этож не дерево, а граф. Для поиска в графе есть волновой алгоритм. В тернете полно инфы по нему.
Например тут
http://algolist.ncstu.ru/maths/graphs/shortpath/wave.php

Правда, он предназначен для поиска кратчайшего пути, но основан на поиске пути к конкретному элементу графа.

Автор: Lomir 21.5.2007, 15:47

Цитата

А как найти элемент в НЕдвоичном дереве

Дерево это связанных граф без циклов и повторяющихся ребер.
Так все же у вас дерево или просто граф?
Если дерево, то копать в сторону биноминальных деревьев.
Если граф, тогда... DFS наверное подойдет.

Автор: sapphiro 21.5.2007, 20:11

Если б был граф, я бы написал, что это граф.... а это дерево
Оцените кто нить:

Код


struct ORGAZ{
    char name[15];
    ORGAZ *Right_SIBLING;    //Указатель на правого соседа
    ORGAZ *Left_SIBLING;
    ORGAZ *Id_PARENT;    //Указатель на ролителя
    int Kid_Count;    //Кол-во детей одного уровня
    ORGAZ *First_Chlid;        //Указатель на первого ребенка на уровне
};
//----------------------------------------------------------------------------------------
ORGAZ* FindElem(ORGAZ* pHead, char* NeedName)      //указатель на голову, содержимое по которому ищем
{
if(pHead == NULL)
    return NULL;
if(pHead ->name == NeedName)
    return pHead;

ORGAZ* pCur = FindElem(pHead ->First_Chlid, NeedName);         //идем по указателю на ребенка(указатель единственный)
if(pCur != NULL)
    return pCur;

return FindElem(pHead ->Right_SIBLING, NeedName);            //идем по указателю на правого сиблинга
}

"DFS наверное подойдет" - если код имеется, я бы не отказался... smile

Автор: Bitter 21.5.2007, 22:06

А чем Вы, sapphiro, обосновываете, что это дерево? У дерева должен быть корень, на который никто не ссылается. В Вашем случае все элементы имеют как исходящие, так и входящие ссылки, следовательното это граф, а значит и алгоритмы нужно применять графовые.

Автор: Lomir 22.5.2007, 00:08

А дерево подчиняеться каким нибуть законам?
Если нет, тогда ДФС. Код обхода приблизительно такой (если списки не кольцевые):

Код


void DFS(ORGAZ* a)
{
    if (!a) return;
    DFS(a->First_Chlid);
    DFS(a->Left_SIBLING);
}

Цитата

Код


struct ORGAZ{
    char name[15];
    ORGAZ *Right_SIBLING;    //Указатель на правого соседа
    ORGAZ *Left_SIBLING;
    ORGAZ *Id_PARENT;    //Указатель на ролителя
    int Kid_Count;    //Кол-во детей одного уровня
    ORGAZ *First_Chlid;        //Указатель на первого ребенка на уровне
};

Почему-то мне это очень похоже на биноминальные деревья\пирамиды smile

Автор: sapphiro 22.5.2007, 14:27

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