递归树映射

Question

我最近一直在研究树的实现以及如何表示和理解树。我的重点是将数学表达式转化为二叉树，我提出了一个问题：如何用线性形式（例如字符串或数组）表示树，同时仍然保留有关树及其子树的重要信息。

因此，我开发了一种非常简单的二叉表达式树编码方法，可以做到这一点。然而，我在以递归方式有效地实现它方面遇到了一些问题，这似乎是该概念失败的一个方面。

如果节点作为左子节点存在，则给予1的映射；如果节点作为右子节点存在，则给予0的映射。这种简单的编码方式使我能够像这样对整个平衡和不平衡的树进行编码：

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

Etc to trees of depth N

如何创建一个递归函数来创建表示此类映射的前缀字符串（例如## 1 11 10 0 01 00）？是否有任何建议？

由于需要在保留父元素的值并将其连接起来时不断在1和0之间切换，因此我被告知这可能很困难/不可能。

我想知道是否有人对如何使用C＃实现此功能有任何见解或想法？

- user648132

---

你的方案中似乎存在很多冗余。特别是，每个节点都从根节点编码其路径。采用这种方案，列举叶节点的编码就足以完全表示整棵树了。不知道这是否有所帮助，只是一些观察。 - Alexander Kondratskiy

我需要保留那个路由，以便我可以有效地确定子表达式及其作为整体的交互方式。 - user648132

Answer 1

嗯，我不知道我是否完全理解你的问题，但似乎你想要树的先序遍历。我不知道C#的语法，但我认为伪代码应该如下：

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

- sukunrt

Answer 2

我不确定我是否理解了你的问题，但这里有一些可能会有所帮助的东西。一个解决方案可能是在图上实现图遍历例程（请记住，树是一种专门的图），其中访问发生在第一次遇到节点/顶点时。很抱歉我发布了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();
    ...
}

希望这能给你一些启发。

- cyber-monk

Answer 3

即使对于经验丰富的程序员来说，递归构建树也是一个困难的挑战。我意识到我有点晚参与这个问题的讨论，因为它最初是在2011年3月发布的。但迟做总比不做好吧？

创建树的一个重要因素就是确保数据集格式正确。你只需要找到一种将父节点和子节点关联起来的方法。一旦关联清晰明确，你就可以开始编写解决方案了。我选择使用了一个简单的格式，如下所示：

ParentId ChildId
1        2
1        3
2        4
3        5

等等。

一旦建立了这种关系，我开发了一种递归方法来遍历数据集以构建树形结构。

首先，我识别所有的父节点，并将它们存储在一个集合中，使用父ID和子ID的组合为每个节点分配一个唯一的标识符：

 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年编写的代码，所以它是旧的，但仍然可以使用。 :-) 希望这有所帮助。

- soundbender