從路徑字符串中獲取類似於結構的樹

由於我不堅定地使用指針和遞歸，所以我被困在2天之內。我有路徑類似的結構數組，讓說：從路徑字符串中獲取類似於結構的樹

s:=[]string { 
    "a/b/c", 
    "a/b/g", 
    "a/d", 
}

與數據結構是這樣的：

type Node struct { 
    Name  string `json:"name"` 
    Children []Node `json:"children"` 
}

我想用這樣的事情結束了：

{ 
"name": "a", 
"children": [ 
    { 
     "name": "b", 
     "children": [ 
     { 
     "name": "c", 
     "children": [] 
     }, 
     { 
     "name": "g", 
     "children": [] 
     } 
     ] 
    }, 
    { 
    "name": "d", 
    "children": [] 
    } 
    ] 
}

我試圖用遞歸來構建它，這種方法很好，但只適用於一個字符串（例如「a/b/c」），只要我嘗試實現某些應該添加缺失節點（「g」）的內容「a/b/g」）到我被卡住的樹上。

我有這樣的事情：

func appendChild(root Node, children []string) Node { 
    if len(children) == 1 { 
     return Node{children[0], nil} 
    } else { 
     t := root 
     t.Name=children[0] 
     t.Children = append(t.Children, appendChild(root, children[1:])) 
     return t 
    } 
}

可能有人點我到一個有效的解決方案？

來源

2017-05-05 hanneslehmann

你可以做一個[Trie]（https：// en。 wikipedia.org/wiki/Trie）或[Radix Tree]（https://en.wikipedia.org/wiki/Radix_tree）插入算法，以瞭解如何實現您想要的內容。 – mkopriva

如果你沒有問題，但想改善你的解決方案，你可以發佈類似這樣的問題到codereview.stackexchange –

其實代碼實際上並不工作，但我會嘗試你的建議 – hanneslehmann

https://play.golang.org/p/9pER5cwChF

func AddToTree(root []Node, names []string) []Node { 
    if len(names) > 0 { 
     var i int 
     for i = 0; i < len(root); i++ { 
      if root[i].Name == names[0] { //already in tree 
       break 
      } 
     } 
     if i == len(root) { 
      root = append(root, Node{Name: names[0]}) 
     } 
     root[i].Children = AddToTree(root[i].Children, names[1:]) 
    } 
    return root 
}

輸出示例（請注意，我的孩子們現場使用omitempty，因爲我不喜歡在我的JSONs null項）：

[{ 
    "name": "a", 
    "children": [{ 
     "name": "b", 
     "children": [{ 
      "name": "c" 
     }, { 
      "name": "g" 
     }] 
    }, { 
     "name": "d" 
    }] 
}]

從您的版本顯着差異：

它運行在n代替單個節點的孩子。這很重要，因爲您的版本假定所有樹都具有相同的單根節點（a），但情況可能並非如此。在你的版本中處理這個問題的唯一方法是在根上有一個「假」節點。
它不重用輸入節點。這是您的代碼的主要問題之一。如果len（children）> 1，則更新輸入節點的名稱，附加到它的子節點，然後遞歸。這意味着切片的每個先前級別都成爲兒童的一部分。您需要創建一個新的節點。
它實際上搜索樹。你沒有搜索樹，看是否已經存在的項目，所以你複製節點（具體來說，節點b）

來源

2017-05-05 16:02:50 Kaedys

非常酷！感謝您的幫助如此之快！這樣可行。 – hanneslehmann

從路徑字符串中獲取類似於結構的樹

回答

相關問題