c# - 递归树映射

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# 时发布 Java 代码，我深表歉意，但我碰巧知道 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();
    ...
}

希望这能给你一些想法。