如何創建一個樹，找到正確的節點來添加子節點？

什麼是最好的方式來建立一個樹的輸入給出格式(a,b),a是父節點和b是兒童節點？（節點1根）例如：如何創建一個樹，找到正確的節點來添加子節點？

1 2 //adds node #2 as the children of #1 (the root) 
1 3 //adds node #3 as the second children of the root 
2 4 //adds node #4 as the children of node #2 
etc...

我瞭解如何使這種樹的，如果它像一個二叉樹（自左子是較小值，右孩子是的對於給定的父節點來說更大）。但是，父親可以擁有的子節點的數量對於我的樹來說不是固定的。我怎樣纔能有效地創造這個？我無法理解算法如何迭代並找到正確的節點（輸入的a部分），以便它可以將另一個節點添加爲子節點（輸入的b部分），因爲節點可以使用的子節點數量有沒有固定。

編輯：我想補充的另一件事：每個葉子節點（沒有子節點的）將被分配一些值。我需要遞歸（或其他方法）遍歷樹，以便可以計算每個節點的值：父節點值是其所有子節點值的總和。

來源

2013-10-25 StarShire

問題可能更適合程序員.stackexchange.com。另請參閱http://meta.stackexchange.com/questions/82988/choosing-between-stack-overflow-and-programmers-stack-exchange – grasbueschel

你能否防止類似情況發生？ 1 2，2 1;基本上是父 - >子，孩子 - >父母的循環。 – Justin

存儲在每個節點中的右孩子和兄弟姐妹地址。

當您收到a,b，如果節點a還沒有右孩子插入b爲右孩子，如果有合適的孩子跟着右孩子的兄弟找到最後一個子並插入b作爲最後一個節點的兄弟。

遍歷樹：

我覺得這種算法可以在深度遍歷樹首先：

traverse(Node) 
visit (Node) // pre order 
if (Node.RightChild != Null) 
    n = Node.RightChild 
    while(n.LeftSibling != Null) 
    traverse (n.LeftSibling) 
    n = n.LeftSibling 
    end 
end 
end

來源

2013-10-25 07:05:31

嗯...我想過，但我現在有另一個問題：在我建立樹後，葉節點（他們沒有任何孩子的節點）將有一個給定的輸入值（一個不同於值' （A，b）'）。我需要以某種方式遞歸計算每個節點的值，其中父節點等於子節點的所有值的總和。這是否適用於您提供的方法？ – StarShire

它通常足以存儲子節點的鏈接列表（或數組）（儘管取決於樹的類型，其他表示可能更有效）。

通常你會有一個地圖或節點數組。

當您在尋找a時，您只需在地圖或陣列中查找它即可。

然後，您只需將b添加到子列表中。

我需要遞歸遍歷樹倒

這將涉及簡單breadth-first search或depth-first search。

來源

2013-10-25 07:46:17 Dukeling

如何創建一個樹，找到正確的節點來添加子節點？

回答

相關問題