VPF::Поиск элемента в НЕдвоичном дереве

sapphiro

Дата 20.5.2007, 16:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 13.11.2006

Репутация: нет
Всего: нет

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

Это сообщение отредактировал(а) sapphiro - 20.5.2007, 21:10

Присоединённый файл ( Кол-во скачиваний: 16 )

ex.JPG 78,26 Kb

Bitter

Дата 21.5.2007, 02:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный лентяй

Профиль
Группа: Завсегдатай
Сообщений: 1209
Регистрация: 15.8.2004
Где: Харьков, Ukraine

Репутация: 4
Всего: 27

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

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

Lomir

Дата 21.5.2007, 15:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 30.1.2007
Где: Lithuania::Kaunas

Репутация: нет
Всего: 1

Цитата

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

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

sapphiro

Дата 21.5.2007, 20:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 13.11.2006

Репутация: нет
Всего: нет

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

Код


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

Это сообщение отредактировал(а) sapphiro - 21.5.2007, 20:13

Bitter

Дата 21.5.2007, 22:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный лентяй

Профиль
Группа: Завсегдатай
Сообщений: 1209
Регистрация: 15.8.2004
Где: Харьков, Ukraine

Репутация: 4
Всего: 27

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

Lomir

Дата 22.5.2007, 00:08 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 30.1.2007
Где: Lithuania::Kaunas

Репутация: нет
Всего: 1

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

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 13.11.2006

Репутация: нет
Всего: нет

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »