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

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

Форум программистов > Visual C++/MFC/WTL > Обход дерева (небинарного)

Автор: metoflex 19.9.2010, 12:55

Здравствуйте!

Второй день не могу спать спокойно, очень озадачен вопросом, как мне обойти все вершины дерева (CTreeCtrl) начиая с самой первой, причём обойти последовательно каждую ветку, т.к. мне потом нужно будет информацию упорядоченно сохранить в файл, а потом загрузить из него. Как сохранить и загрузить-придумал, а вот как обойти дерево, для сохранения данных каждого узла....ума не приложу... Дерево не бинарное. Предполагаю что необходимо выполнять рекурсивный обход , но как...

Буду очень рад, если у кого есть уже готовый алгоритм обхода.

Спасбо Огромное!

Автор: Cheloveck 19.9.2010, 13:18

Вот я когда-то делал для рекурсивного обхода каталогов. По аналогии разберёшься, я думаю.

Код


void MainWnd::_scan_dir( const CString dirname )
{
    WIN32_FIND_DATA find_data;
    CString searchdirname = dirname; // Текущий каталог поиска.
    CString path = dirname + L"\\*"; // Полное имя файла.

    // Начинаем поиск.
    HANDLE handle = ::FindFirstFile( path, &find_data );
    if( handle == INVALID_HANDLE_VALUE )
        return;

    // Очередь сканирования.
    std::deque< CString > dir_deque; 

    while( true )
    {
        if( ::FindNextFile( handle, &find_data ) ) // Ищем файл.
        {
            // Всякие точки и двоеточия нам не нужны.
            if( ( find_data.cFileName[0] == '.' &&
                    find_data.cFileName[1] == 0 ) ||
                    ( find_data.cFileName[0] == '.' &&
                    find_data.cFileName[1] == '.' &&
                    find_data.cFileName[2] == 0 ) )
                continue;
            
            // Собираем полное имя файла.
            path = searchdirname + L"\\" + find_data.cFileName; 
            switch( _check_filename( path ) ) // Проверяем тип файла.
            {
                case MifFile:
                    // MIF или TXT - добавляем в список.
                    _filelist->AddItem( path ); 
                    break;
                case DirectoryFile:
                    // Каталог добавляем в очередь сканирования.
                    dir_deque.push_front( path );
                    break;
                default:
                    // Остальное нас не интересует.
                    continue;
            }
        }
        else // Файлы в каталоге закончились.
        {
            // Завершаем текущий поиск.
            FindClose( handle ); 
            // Проверяем наличие записей в очереди.
            if( dir_deque.empty() ) // Если пусто - уходим.
                break; 

            // Новый каталог для поиска.
            searchdirname = dir_deque.back(); 
            // Начальное имя файла.
            path = searchdirname + L"\\*"; 
            // Удаляем из очереди запись.
            dir_deque.pop_back(); 
            // Начинаем новый поиск.
            handle = ::FindFirstFile( path, &find_data ); 
            if( handle == INVALID_HANDLE_VALUE )
                break;
        }
    }
}

Автор: metoflex 19.9.2010, 13:35

Спасибо Огромное! Сейчас попробую разобраться!

Автор: metoflex 19.9.2010, 14:13

Создал функцию с параметрами:

Код


void RecurseTree (CTreeCtrl  n ,CString str, HTREEITEM first, int i)

Выдаёт ошибку:

Код


1>d:\games\vc\atlmfc\include\afxwin.h(1986): error C2248: CObject::CObject: невозможно обратиться к private член, объявленному в классе "CObject"
1>          d:\games\vc\atlmfc\include\afx.h(534): см. объявление "CObject::CObject"
1>          d:\games\vc\atlmfc\include\afx.h(509): см. объявление "CObject"
1>          Сообщение диагностики возникло в созданной компилятором функции "CCmdTarget::CCmdTarget(const CCmdTarget &)"
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========

Я так полагаю, что компилятор не может скопировать в функцию переменную n, типа CTreeCtrl , необходимо вызывать конструктор копирования, я полагаю, подскажите как исправить ошибку. Спасибо!

Автор: Cheloveck 19.9.2010, 14:28

Передавай объекты по ссылке. У меня в примере небольшая ошибка

Код


void MainWnd::_scan_dir( const CString & dirname )

надо. Соответственно тебе

Код


void RecurseTree (CTreeCtrl  & n ,const CString & str, HTREEITEM first, int i)

CTreeCtrl тоже, наверное, const.

Автор: metoflex 20.9.2010, 19:03

Спасибо Огромное! Всё получилось!)

Кому надо, вот код:

Код


void RecursTree (const CTreeCtrl & n ,CString str, HTREEITEM first)
{
    static int i=0;

    do 
    {
        if (i==0)
        {
            if (n.GetChildItem(first))
            {
                i++;
                RecursTree (n,str,n.GetChildItem(first));
                i=0;
            }
        }
        if (i==1)
        {
            if (n.GetChildItem(first))
            {

                if (n.GetChildItem(n.GetChildItem(first)))
                {
                    first=n.GetChildItem(first);
                    RecursTree (n,str,first);
                }
                else
                {
                    RecursTree (n,str,n.GetChildItem(first));
                }
            }
            else // Если конечный узел.
            {
                AfxMessageBox(n.GetItemText(first));
            }
        }
    } while (first=n.GetNextSiblingItem(first));

    return;
}

Автор: Cheloveck 20.9.2010, 19:42

1. Это будет работать только один раз, так как i не обнуляется.
2. Это будет работать только с довольна малым количеством элементов дерева. С большим получешь переполнение стека, ибо рекурсия - зло!

Автор: Earnest 20.9.2010, 19:59

Cheloveck, не пугай ты так. Чтобы рекурсия реально сожрала стек, нужно столько элементов, что виндоус треснет.
Точнее, столько уровней вложенности, т.к. глубина рекурсии зависит именно от этого.
Во всяком, случае, проблемы раньше начнутся в другом месте. Рекурсивные алгоритмы - естественны для рекурсивных структур.
Если начнутся проблемы с производительностью\памятью, то рекурсивный алгоритм всегда можно развернуть через стек, но будет утрачена лаконичность кода, так что делать это стоит только при действительной необходимости, а не заранее и на всякий случай.

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

Код


void DoSomething (CTreeCtrl& tree, HTREEITEM hItem, ...)

    // можно, в зависимости от задачи, этот код переставить в конец
    DoSomethingWithItem (hItem);

   if (tree.ItemHasChildren (hItem)) 
   {
      for (HTREEITEM hSubItem = tree.GetChildItem (hItem); hSubItem!=0; 
         hSubItem = tree.GetNextItem (hSubItem, TVGN_NEXT)) 
      {
          DoSomething (tree, hSubItem, ...);
      }
   }
}

Автор: Cheloveck 20.9.2010, 20:50

Цитата(Earnest @ 20.9.2010, 19:59

)

и оно вроде есть.

Точно, не заметил. Всё равно я против рекурсии без крайней необходимости. И то при условии, что точно известно максимальное количество итераций. Кстати, при обходе рекурсией каталога Windows у меня стек валился, кажется.

Автор: Earnest 21.9.2010, 07:57

Цитата(Cheloveck @ 20.9.2010, 21:50

)

Кстати, при обходе рекурсией каталога Windows у меня стек валился, кажется.

Это вовсе не значит, что плоха рекурсия, это ты код плохой написал. Чтобы стека не хватило на рекурсивный обход каталогов - ни в жисть не поверю. Но ошибиться в рекурсивной процедуре можно легко, это верно. Легкая лажа в условии выхода и привет стеку. Но ты ведь не перестаешь пользоваться молотком только оттого, что пару раз по пальцам попал?

Автор: Cheloveck 21.9.2010, 08:40

Цитата(Earnest @ 21.9.2010, 07:57

)

молотком только оттого, что пару раз по пальцам попал?

Но я не пользуюсь молотком там, где можно закрутить отвёрткой. Я к тому, что стек можно организовать и в куче самому. И такой стек не лопнет в один прекрасный момент.

Цитата(Earnest @ 21.9.2010, 07:57

)

это ты код плохой написал

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

Автор: metoflex 21.9.2010, 23:30

Спасибо Огромное за ваши отзывы, очень помогли!

Взник еще один небольшой вопросик. Создал класс (который прикрепил к CTreeCtrl), вызываю метод этого класса:

Код


TreeClass.RecursTree(str, EL);

Пишет ошибку такого толка:

Нестатическая ссылка на член должна указывать относительно заданного объекта

Если пишу так:

Код



              TreeClass* k;
    k->RecursTree(str, EL);

Съедает без ошибки.

Почему так??

Спасибо!

Автор: Cheloveck 21.9.2010, 23:40

Потому что TreeClass - это класс. Из класса (без объекта) можно вызывать только статические функции, то есть объявленные с модификатором static. Но такие функции, соответственно, не имеют доступа к членам класса. А к обычным функциям можно обращаться только через объект, ибо только объеет хранит все переменные.
Обычно, разницу между объектом и классом объясняют так: класс - это разметка, по которой создаётся объект.

Добавлено через 55 секунд
Статические методы вызываются из класса через оператор двойное двоеточие

Код


TreeClass::RecursTree(str, EL);

Автор: metoflex 21.9.2010, 23:48

То же самое сообщение выдаёт, если обращаюсь через ( :: )

Добавлено @ 23:51
Статические, как я понимаю, не могут внести изменения в объект, но я вызовом данной функции вызываю построение древа... она явно не static ....

Автор: Cheloveck 22.9.2010, 09:43

Цитата(metoflex @ 21.9.2010, 23:48

)

она явно не static ....

Цитата(metoflex @ 21.9.2010, 23:48

)

То же самое сообщение выдаёт, если обращаюсь через ( :: )

Ну так это логично oO

Автор: metoflex 22.9.2010, 12:42

Cheloveck, А как исправить?? Подскажи, пожалуйста!

Автор: metoflex 22.9.2010, 14:08

Проблему поправил сам. Так:

TreeClass tree;

tree.InsertItem();

Автор: Cheloveck 22.9.2010, 16:34

metoflex, можешь же, когда захочешь думать сам =)