Рекурсивное картографирование деревьев

Question

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

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

Кодировка проста, если узел находится как левый потомок, ему дается картаиз 1, если он находится как правильный дочерний элемент, ему присваивается 0. Это простое кодирование позволяет мне кодировать целые сбалансированные и несбалансированные деревья, например, так:

           ##                      ##
          /  \                    /  \
         1    0         OR       1    0
        / \  / \                     / \
       11 10 01 00                  01  00 

и т. д. для деревьев глубины N

Есть ли у кого-нибудь какие-либо предложения относительно того, как создать рекурсивную функцию, которая создала бы строку префикса, представляющую отображение такого рода (например, ## 1 11 10 0 01 00).

Мне сказали, что это будет трудно / невозможно из-за необходимости отслеживать чередование между 1 и 0 при сохранении и объединении со значением родителя.

Я задавался вопросом, есть ли у кого-нибудь понимание или идеи, как это сделать с помощью C # ??

Answer 1

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

preorder_traversal(node)
    if(node != NULL)
        print(node)
        preorder_traversal(left_sub_child)
        preorder_traversal(right_sub_child)
    else
        return

Answer 2

Рекурсивное построение дерева - сложная задача даже для опытного программиста.Я понимаю, что немного опоздал на вечеринку по этому вопросу, учитывая, что он был первоначально опубликован в марте 2011 года. Лучше поздно, чем никогда?

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

ParentId ChildId
1        2
1        3
2        4
3        5

И т. Д.

После того, как это отношение установлено, я разработал рекурсивный метод для перебора набора данных для построения дерева.

Сначала я идентифицирую все родительские узлы и сохраню их в коллекции, присваивая каждому уникальный идентификатор, используя комбинацию родительского идентификатора и дочернего идентификатора:

 private void IdentifyParentNodes()
{
    SortedList<string, MyTreeNode> newParentNodes = new SortedList<string,MyTreeNode>();
    Dictionary<string, string> parents = new Dictionary<string, string>();
    foreach (MyTreeNode oParent in MyTreeDataSource.Values)
    {
        if (!parents.ContainsValue(oParent.ParentId))
        {
            parents.Add(oParent.ParentId + "." + oParent.ChildId, oParent.ParentId);

            newParentNodes.Add(oParent.ParentId + "." + oParent.ChildId, oParent);
        }
    }

    this._parentNodes = newParentNodes;
}

Затем корневой вызывающий метод будет зацикленчерез родителей и вызовите рекурсивный метод для построения дерева:

// Build the rest of the tree
foreach (MyTreeNode node in ParentNodes.Values)
{
    RecursivelyBuildTree(node);
}

Рекурсивный метод:

private void RecursivelyBuildTree(MyTreeNode node)
{
    int nodePosition = 0;

    _renderedTree.Append(FormatNode(MyTreeNodeType.Parent, node, 0));
    _renderedTree.Append(NodeContainer("open", node.ParentId));

    foreach (MyTreeNode child in GetChildren(node.ParentId).Values)
    {
        nodePosition++;
        if (IsParent(child.ChildId))
        {
            RecursivelyBuildTree(child);
        }
        else
        {
            _renderedTree.Append(FormatNode(MyTreeNodeType.Leaf, child, nodePosition));
        }
    }
    _renderedTree.Append(NodeContainer("close", node.ParentId));
}

Метод, используемый для получения потомков родителей:

private SortedList<string, MyTreeNode> GetChildren(string parentId)
{
    SortedList<string, MyTreeNode> childNodes = new SortedList<string, MyTreeNode>();
    foreach (MyTreeNode node in this.MyTreeDataSource.Values)
    {
        if (node.ParentId == parentId)
        {
            childNodes.Add(node.ParentId + node.ChildId, node);
        }
    }
    return childNodes;
}

Не такой сложный или элегантный, но он сделал свою работу.Это было написано в 2007 году, поэтому это старый код, но он все еще работает.:-) Надеюсь, это поможет.

Answer 3

Я не уверен, что понимаю вашу проблему, но вот кое-что, что может помочь.Одним из решений может быть реализация подпрограммы обхода графа на графе (помните, что дерево - это специализированный граф), где посещение происходит в первый раз, когда вы сталкиваетесь с узлом / вершиной.Я извиняюсь за публикацию кода Java, когда вы спрашиваете о C #, но я знаю, что Java ...

public void depthFirstSearch(Graph graph, Vertex start){
    Set<Vertex> visited = new HashSet<Vertex>(); // could use vertex.isVisited()...
    Deque<Vertex> stack = new ArrayDeque<Vertex>(); // stack implies depth first

    // first visit the root element, then add it to the stack so
    // we will visit it's children in a depth first order
    visit(start);
    visited.add(start);
    stack.push(start);   

    while(stack.isEmpty() == false){
        List<Edge> edges = graph.getEdges(stack.peekFirst());
        Vertex nextUnvisited = null;
        for(Edge edge : edges){
            if(visited.contains(edge.getEndVertex)) == false){
               nextUnvisited = edge.getEndVertex();
               break; // break for loop
            }
        }
        if(nextUnvisited == null){
            // check the next item in the stack
            Vertex popped = stack.pop();
        } else {
            // visit adjacent unvisited vertex
            visit(nextUnvisited);
            visited.add(nextUnvisited);
            stack.push(nextUnvisited); // visit it's "children"
        }
    }
}

public void visit(Vertex vertex){
    // your own visit logic (string append, etc)
}

Вы можете легко изменить это для поиска в ширину, используя Deque в качестве очереди вместо стека какследует:

stack.pop()  >>>>  queue.removeFirst()
stack.push() >>>>  queue.addLast()

Обратите внимание, что для этой цели классы Graph и Edge поддерживают следующие операции:

public interface Graph {
    ...
    // get edges originating from Vertex v
    public List<Edge> getEdges(Vertex v);
    ...
}

public interface Edge {
    ...
    // get the vertex at the start of the edge
    // not used here but kind of implied by the getEndVertex()...
    public Vertex getStartVertex();
    // get the vertex at the end of the edge
    public Vertex getEndVertex();
    ...
}

Надеемся, что это даст вам некоторые идеи.