C# Итерация большого дерева

У меня есть большой набор результатов, собранный в отношениях родитель/потомок. Мне нужно пройтись по дереву и отобразить результаты пользователю.

Я сделал это до использования рекурсии, но поскольку мой результирующий набор может быть большим, я хочу избежать возможности получения StackOverflowException.

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


LeveL 1
Level 1.1
Level 1.1.1 
Level 1.1.2 
Level 1.2 
Level 1.2.1 
Level 1.2.2

Но похоже:


LeveL 1
Level 1.2 
Level 1.2.2 
Level 1.2.1 
Level 1.1 
Level 1.1.2 
Level 1.1.1

Любые идеи?

Вот пример моего кода. Предполагая, что DataTable dt имеет следующие столбцы: ID, ParentID и Text

    private struct Item
    {
        public string Text;
        public int ID;
        public int ParentID;
    }

    private void BuildView()
    {
        Stack<Item> itemTree = new Stack<Item>(40);

        //Get All Parent Nodes
        DataView dv = new DataView(dt);
        dv.RowFilter = "ParentID = 0";

        //Add the parent nodes to the stack
        foreach (DataRowView drv in dv)
        {
            Item item = new Item();
            item.Text = drv["Text"].ToString();
            item.ID = drv["ID"].ToString();
            item.ParentID = drv["ParentID"].ToString();
            itemTree.Push(item);
        }

        //Go through the stack one node at a time
        while (itemTree.Count > 0)
        {
            Item currentItem = itemTree.Pop();
            Debug.WriteLine(currentItem.Text);

            //Get children of current node
            dv.RowFilter = String.Format("ParentID = {0}", currentItem.ID);
            if (dv.Count > 0)
            {
                //Add child nodes to the stack
                foreach (DataRowView drvChild in dv)
                {
                    Item item = new Item();
                    item.Text = drvChild["Text"].ToString();
                    item.ID = drvChild["ID"].ToString();
                    item.ParentID = drvChild["ParentID"].ToString();
                    itemTree.Push(item);
                }
            }
        }

    }

c# recursion iteration algorithm tree-traversal
person user62064    schedule 03.02.2009    source источник

Ответы (4)


arrow_upward
1
arrow_downward

Поместите свои предметы в стек в обратном порядке, то есть 2 перед 1.

Пример:

// suppose I want to push children[] onto the stack

for (int i = children.Length - 1; i >= 0; i--)
{
   stack.Push(children[i]);
}

Чтобы сделать это в своем коде, попробуйте следующий оператор for-each:

foreach (DataRowView drvChild in dv.Reverse())
person Zach Scrivena    schedule 03.02.2009
comment
@Niyaz: обновил мой ответ примером. - person Zach Scrivena; 03.02.2009
comment
Ага. Но можете ли вы объяснить, как это даст требуемый ответ? Не могу понять. - person Niyaz; 03.02.2009
comment
@Niyaz: я думаю, что это работает для особого способа использования стека OP. Думаю, это зависит от того, как вы используете стек для обхода. - person Zach Scrivena; 03.02.2009
comment
Есть лучший способ сделать это? - person user62064; 03.02.2009
comment
@djdouma: я думаю, что ваш способ оптимален для желаемого результата. - person Zach Scrivena; 03.02.2009

arrow_upward
3
arrow_downward

В текущем алгоритме вы сначала выбираете правильного ребенка.

Сначала сделайте его левым дочерним. Это все.

Например, в вашем коде может быть что-то вроде:

node = node.rightChild()

Измените его на

node = node.leftChild()

Это общее решение для такого рода проблем.

Поскольку реализация MSDN не предоставляет такой код, я не могу это комментировать.

person Niyaz    schedule 03.02.2009
comment
Я думаю, что там опечатка... обе строки кода идентичны. - person Zach Scrivena; 03.02.2009

arrow_upward
0
arrow_downward

Если вас беспокоит просто порядок, измените использование стека на использование очереди. Для практических целей они одинаковы, с той разницей, что Queue действует в порядке очереди.

person Jacob Proffitt    schedule 03.02.2009
comment
Использование очереди изменяет ее на обход в ширину вместо желаемого обхода в глубину. - person Zach Scrivena; 03.02.2009
comment
Зак, Не обязательно. Он становится первым в ширину, только если вы делаете сначала в ширину. Но обычно мы используем очередь в поиске в ширину. - person Niyaz; 03.02.2009
comment
Если я использую очередь, данные выглядят так. Уровень 1 Уровень 1.1 Уровень 1.2 Уровень 1.1.1 Уровень 1.1.2 Уровень 1.2.1 Уровень 1.2.2 - person user62064; 03.02.2009

arrow_upward
0
arrow_downward

Изменив мою итерацию дочерних узлов в обратном порядке, они отображаются по желанию

//Add child nodes to the stack
for (int i = dv.Count - 1; i >= 0; i--)
{
    DataRowView drvChild = dv[i];
    Item item = new Item();
    item.Text = drvChild["Text"].ToString();
    item.ID = drvChild["ID"].ToString();
    item.ParentID = drvChild["ParentID"].ToString();
    itemTree.Push(item);
}
person user62064    schedule 03.02.2009
comment
Опечатка? Индекс i, похоже, не используется. - person Zach Scrivena; 03.02.2009