VPF::GetEnumerator() для дерева - Форум программистов

Walker

Дата 12.12.2007, 09:18 (ссылка)

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

Загрузка ...

Опытный

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

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

Доброго времени суток, Уважаемые жители Винграда.

Пишу реализацию Tree. Дерево состоит из узлов Node следующей структуры:
Поле 1: Уникальный идентификатор узла.
Поле 2: Указатель на родительский узел. Для корня - null.
Поле 3: Содержимое узла.
Поле 4: Указатель на коллекцию List<T> дочерних узлов.

Обход дерева по всем узлам помог бы упростить многие методы работы с этой структурой. Мне удобен такой алгоритм:
int i = 0;
1. Берём i-ый узел коллекции.
2. ЕСЛИ ссылка на коллекцию дочерних объектов не пуста (List<T>.Count != 0)
              ТО Переходим на первый элемент дочерней коллекции;
                    Начинаем выполнение алгоритма сначала. Счётчик инциализируется нулём.
               ИНАЧЕ
                           ЕСЛИ последний элемент коллекции обработан,
                                     ТО поднимаемся на уровень вверх:
                                      ИНАЧЕ i++;

По сути - это foreach с рекурсией. Я начинаю перебор узлов, спускаюсь по всем первым узлам до конца. В конце пробегаю весь лист, поднимаюсь на уровень вверх, пробегаю у второго узла весь дочерний лист, поднимаюсь на уровень вверх - у третьего.... И т.д.

Вопрос - как же для такого алгоритма реализовать GetEnumerator(). Хотелось бы через yield return, но не могу придумать-как его приспособить.

Код


// Начало понятно
class Tree
{
    ...
    public IEnumerator GetEnumerator()
          foreach(Node n in this) // Перебираем корневые элементы
          {
                 yield return n;
                 RecurseFunc(n.Nodes);
          }

    private void RecurseFunc(List<Node> nodes)
    {
              foreach (Node n in nodes)
              {
                          ????
                           RecurseFunc(n.Nodes);
              }
    }
}

Ведь возврат будет происходить в рекурсионную функцию, а не наружу. То ли какой-то глобальной переменной не хватает, то ли ещё чего, но какой-то выход должен быть. smile

В общем, запутался... smile

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

"От вчерашних побед остаётся усталость, если завтрашний день не сулит ничего..."

Veitmen

Дата 12.12.2007, 10:31 (ссылка)

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

Загрузка ...

Опытный

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

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

http://www.sgu.ru/ie/mehmat/odfka/r1/R1-2.htm

Код


using System;
using System.Collections.Generic;
using System.Text;
using System.Data;
using System.Collections;

namespace AstroSoftNewVersion.Classes.GUI
{
    class Information
    {
        private ArrayList Parent;
        private ArrayList Child;
        public Information()
        {
            Parent = new ArrayList();
            Child = new ArrayList();
        }

        public void ShowTree(System.Windows.Forms.TreeView Tree,DataSet DataSetTask)
        {      
            try
            {
                Tree.Nodes.Clear();
                DataRow[] WorkData = DataSetTask.Tables["Task"].Select("FK_Task = 0");//Находим узлы       
                foreach (DataRow RowTask in WorkData)
                {
                    Parent.Clear();
                    Tree.Nodes.Add(RowTask["TaskID"].ToString(), RowTask["Name"].ToString());//Добавляем
                    Parent.Add(RowTask["TaskID"].ToString());//Запоминаем с кем работаем, надо для рекурсии
                    FillingTree(Tree,DataSetTask);//Поехали...
                }
            }
            catch (NullReferenceException ex)
            {
                throw new NullReferenceException(AstroSoftNewVersion.Properties.Resources.exNullReference, ex);
            }
        }

        private void FillingTree(System.Windows.Forms.TreeView Tree,DataSet DataSetTask)
        {
            Child.Clear();
            Boolean Changed = false;
            System.Windows.Forms.TreeNode[] FindNode;
            for (int I = 0; I < Parent.Count; I++)
            {
                FindNode = Tree.Nodes.Find(Parent[I].ToString(),true);//Находим нод по ключу
                DataRow[] WorkData = DataSetTask.Tables["Task"].Select("FK_Task = " +
                    Parent[I].ToString() + " and FK_Task <> 0 ","DateReg");//Находим наследников
                foreach (DataRow RowTask in WorkData)
                {
                    FindNode[0].Nodes.Add(RowTask["TaskID"].ToString(), RowTask["Name"].ToString());//Заполняем
                    Child.Add(RowTask["TaskID"].ToString());//Запоминаем наследников
                    Changed = true;
                }
            }
            if (Changed)//Если дерево менялось, значит есть наследники
            {
                Parent.Clear();   //Здесь и далее делаем наследников родителями и вызываем функцию еще раз
                Parent = (ArrayList)Child.Clone();
                Child.Clear();
                FillingTree(Tree,DataSetTask);
            }
        }
    }
}

Walker

Дата 17.12.2007, 15:23 (ссылка)

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

Загрузка ...

Опытный

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

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

Спасибо, Veitmen!

В коце концов использовал сторонний бесплатный компонент Generic Tree<T>. Там логика реализована несколько иначе, нежели я предполагал, тем не менее, нужный мне функционал был обеспечен.
К Сожалению, на данный момент почему-то домашняя страница компонента недоступна, хотя на прошлой неделе ещё была жива. На всякий случай - поиск по http://www.codeproject.com/ в разделе C# компонента Generic Tree<T>.

ЗЫ: Вопрос помечаю решённым.

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

"От вчерашних побед остаётся усталость, если завтрашний день не сулит ничего..."

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »