VPF::Cложный код, не могу разобраться!

Ozerich

Дата 25.4.2010, 21:22 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 164
Регистрация: 2.8.2009
Где: Минск, Беларусь

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

Есть класс для работы с бинарным деревом

Код


template <typename IDType, typename INF> class TTree
{
// тип данных, который описывает элемент дерева
    template <typename IDType, typename ElemType> struct TElem
    {
        IDType ID;
        ElemType Inf;
        TElem *Left, *Right;
    };
// Уникальный идентификационный номер + информационная часть (полезная нагрузка) + 
// указатель на левый элемент (когда он равен NULL, то это может быть листовой элемент)
// указатель на правый элемент (когда он равен NULL, то это может быть листовой элемент)

    protected:
// Описываем указатели на корневой элемент дерева, который недоступен пользователю
    TElem<IDType, INF> *Root;    
// Недоступный пользователю метод, который обрабатывает все элементы в поддереве
        
        void ProcessAllElemSubTree(TElem<IDType, INF> *Cur, TBaseProcess<IDType, INF> *PBase)
        {
            if (Cur != NULL)
            {
                ProcessAllElemSubTree(Cur->Left, PBase);
                (*PBase)(Cur->ID, Cur->Inf);
                ProcessAllElemSubTree(Cur->Right, PBase);
            }
        }
    public:

        TTree()
        {
            Root = NULL;
        }

        int AddToTree(const IDType ID, const INF Inf)
        {
            TElem<IDType, INF> *NewElem, *Parent;

            if (SearchElem(ID, &Parent) != NULL)
                return NOT_SUCCESS_OPER;

            NewElem = new TElem<IDType, INF>;
            NewElem->ID = ID;
            NewElem->Inf = Inf;
            NewElem->Left = NewElem->Right = NULL;

            if (Root != NULL)
            {
                if (ID > Parent->ID)
                    Parent->Right = NewElem;
                else
                    Parent->Left = NewElem;
            }
            else
                Root = NewElem;

            return SUCCESS_OPER;
        }


//-----------------------------------------------------------------------

// Обработка (например, вывод на экран) всех элементов дерева
        
        void ProcessAllElem(TBaseProcess<IDType, INF> *PBase)
        {
            ProcessAllElemSubTree(Root, PBase);
        }

};

И есть еще вот такой класс

Код


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

template <typename IDType, typename ElemType> class TBaseProcess
{
    public:
        virtual TBaseProcess& operator()(IDType &ID, ElemType &Inf)
        {
            cout << ID << " -> " << Inf << endl;
            return *this;
        }
};

Что мне надо сделать, чтобы написать функцию для обработки каждого элемента дерева, всмысле как PBase передать?

--------------------

C++(STL) / DHTML(CSS) / Javascript / PHP Developer

Artemon

Дата 25.4.2010, 22:59 (ссылка)

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

Загрузка ...

а ты мне нравишься

Профиль
Группа: Завсегдатай
Сообщений: 1771
Регистрация: 24.2.2004
Где: Челябинск

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

Чтобы разобраться Убери везде "Template <typename IDType, typename INF>"
и замени IDType на int.

Думаю станет понятней

Добавлено через 6 минут и 55 секунд

Цитата

Что мне надо сделать, чтобы написать функцию для обработки каждого элемента дерева, всмысле как PBase передать?

Что значит обработка ? Имеешь ввиду пройтись по каждому узлу ?

--------------------

Контроль топлива на топливозаправщиках, мониторинг автотранспорта, расчет зарплаты водителей www.rscat.ru

Ozerich

Дата 25.4.2010, 23:40 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 164
Регистрация: 2.8.2009
Где: Минск, Беларусь

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

Цитата

Что значит обработка ? Имеешь ввиду пройтись по каждому узлу

Задача состоит в том как найти самый правый элемент. Если не лень, то раскажи, иначе завтра сам разберусь, как ты подсказал smile

Это сообщение отредактировал(а) Ozerich - 25.4.2010, 23:40

--------------------

C++(STL) / DHTML(CSS) / Javascript / PHP Developer

Artemon

Дата 26.4.2010, 08:29 (ссылка)

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

Загрузка ...

а ты мне нравишься

Профиль
Группа: Завсегдатай
Сообщений: 1771
Регистрация: 24.2.2004
Где: Челябинск

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

Для начала скажу, что в твоем случае имеем бинарное дерево, это означает что у каждого узла могут быть только 2 листа, значение левого листа дерева должно быть < значения узла.
Значение правого листа дерева должно быть >= значения узла.

Чтобы пройтись по всему дереву и найти крайний правый лист - можно воспользоваться рекурсией,
примеры по алгоритмам с бинарным деревом лежат вот здесь: http://en.wikipedia.org/wiki/Binary_search_tree

--------------------

Контроль топлива на топливозаправщиках, мониторинг автотранспорта, расчет зарплаты водителей www.rscat.ru

Ozerich

Дата 26.4.2010, 12:48 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 164
Регистрация: 2.8.2009
Где: Минск, Беларусь

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

Цитата(Artemon @ 26.4.2010, 08:29)

Что такое бинарное дерево и как найти самый правый элемент я прекрасно понимаю, но как это сделать, используя данный класс?

--------------------

C++(STL) / DHTML(CSS) / Javascript / PHP Developer

Artemon

Дата 26.4.2010, 15:22 (ссылка)

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

Загрузка ...

а ты мне нравишься

Профиль
Группа: Завсегдатай
Сообщений: 1771
Регистрация: 24.2.2004
Где: Челябинск

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

Ну ты хоть сделай предположение, и покажи что получилось, а мы и подправим если что-то не так.

--------------------

Контроль топлива на топливозаправщиках, мониторинг автотранспорта, расчет зарплаты водителей www.rscat.ru

Ozerich

Дата 26.4.2010, 15:56 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 164
Регистрация: 2.8.2009
Где: Минск, Беларусь

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

Ура! Утра вечера мудренее. Разобрался в этом полиморфизме. Достаточно было унаследовать от TBaseProcess класс который реализует свою функцию перегрузки () и потом создать указатель на TBaseProcess и присвоить ему TMyBaseProcess класс. И всё заработало. smile

Спасибо!

--------------------

C++(STL) / DHTML(CSS) / Javascript / PHP Developer

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