遞歸樹映射

Question

最近我一直在樹的實現方面做了很多工作，以及我們如何表示和理解樹。我的注意力集中在將數學表達式轉化爲二叉樹上，我設置了以線性形式表示樹的問題，即一個字符串或一個數組，同時仍然保留有關該樹及其子樹的重要信息。

因此，我開發了一個非常簡單的二進制表達式樹編碼就是這樣做的。然而，我在遞歸莊園中有效地實現它有一些問題，它似乎是這個概念背後的一個失敗的方面。

編碼很簡單，如果節點作爲一個左邊的孩子居住，如果它作爲一個右邊的孩子被賦予一個0，它就被給予1的映射。這個簡單的編碼允許我編碼整個平衡和不平衡的樹木，像這樣：

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

等來的精度N樹木

有沒有人有任何建議，如何創建，將創建一個表示這種映射（例如## 1 11前綴字符串遞歸函數10 0 01 00）。

我被告知這將是困難/不可能的，因爲必須跟蹤1和0之間的交替，同時保留並連接到父母的價值。

我想知道如果任何人有任何見解或想法，如何用C＃做到這一點？

Answer 1

我不確定我是否理解你的問題，但這裏有些可能有所幫助。一種解決方案可能是在Graph上實現圖遍歷例程（記住樹是專用圖），其中訪問首次遇到節點/頂點時發生。我張貼的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) 
} 

您可以輕鬆地修改這是使用雙端隊列爲隊列的棧，而不是作爲遵循廣度優先搜索：

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

注意，用於此目的的圖形和邊緣類支持以下操作：

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(); 
    ... 
} 

希望給你一些想法。

Answer 2

那麼我不知道我是否完全得到你的問題，但似乎你想要樹的預先遍歷。我不知道C＃的語法，但僞代碼，我認爲將是如下：

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

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年的時間框架，所以它是舊的代碼，但它仍然有效。 ：-） 希望這可以幫助。