Алгоритм итерации узлов TreeView в реферсе от последнего листа к корню

Question

Каков наилучший алгоритм для перебора элемента управления WinForms TreeView от последних листьев до корней в обратном порядке? C #

Answer 1

Код ниже будет посещать каждый узел и проходить его полностью, сначала на глубину, пока не дойдет до листа. Затем, когда он раскручивает стек, вызовет DoSomethingWithNode для каждого узла. Параметр depth показывает, что узлы возвращаются в обратном порядке.

void ReverseTraverse(TreeNodeCollection nodes, int depth)
{
    if (nodes == null) return;
    foreach (TreeNode child in nodes)
    {
        ReverseTraverse(child.Nodes, depth+1);
        DoSomethingWithNode(child, depth);
    }
}

Чтобы вызвать его, предполагая, что MyTreeView является TreeView экземпляром:

ReverseTraverse(MyTreeView.Nodes, 1);

Обратите внимание, что это не дает вам сначала самые глубокие конечные узлы, а просто гарантирует, что любой конечный узел выводится перед его родительским узлом. Если ваше дерево выглядит так:

Node 1
  Node 1.1
  Node 1.2
    Node 1.2.1
Node 2
  Node 2.1
    Node 2.1.1
      Node 2.1.1.1
    Node 2.1.2

Порядок вывода будет:

Node 1.1
Node 1.2.1
Node 1.2
Node 1
Node 2.1.1.1
Node 2.1.1
Node 2.1.2
Node 2.1
Node 2

Если вы хотите, чтобы сначала были самые глубокие узлы (т. Е. Сначала был бы выведен узел 2.1.1.1), то вам нужно было бы выполнить полный обход (в прямом порядке будет проще) и создать список узлов с соответствующими глубины. Затем сортируйте список по глубине (по убыванию) и выводите по порядку.

Answer 2

Если у вас есть BT (бинарное дерево), лучшим обходом дерева для прохождения дерева от листьев к корню будет обход дерева после заказа.Это посещает узлы в следующем порядке: влево -> вправо -> корень.Если вы хотите изменить это, используйте: вправо -> влево -> корень.

Псевдокод:

BottomUpTraversal(x)
    BottomUpTraversal(x.left)
    BottomUpTraversal(x.right)
    print(x.key)

Answer 3

Для бинарного дерева вы ищете обратный обход обхода. Для этого вы можете вставить узлы в связанный список (через правый связанный узел) во время обхода по порядку. Затем вы читаете связанный список в обратном порядке.

1. Преобразовать двоичное дерево поиска в двусвязный список, используя обход по порядку O (n).
2. Пройдите этот двусвязный список в обратном направлении. Для этого вы можете использовать два указателя.

Тогда вы можете повеселиться и оптимизировать его:)