如何從邊緣製作二叉樹？

Question

我從

parentId childId 
    e.g. 0 3 // means from node 0 to node 3 
    // 0 does not mean root of the tree. 

得到二叉樹的所有邊緣從輸入如何從這種構造的樹？要做到這一點

Answer 1

一種方法是做到這一點的兩道：

1. 裝配樹中的所有鏈接。
2. 找到樹的根。

要組裝所有鏈接，您可以通過構建由每個節點的ID（或者如果知道ID均在範圍0中的適當大小的數組鍵值化的哈希表開始。 N代表N的某種選擇）。當你從文件中讀取一條線，你可以做到以下幾點：

1. 如果節點尚未使用由起點和終點指定的ID存在，則創建這些節點並初步建立起自己的左側和右側指針空值。
2. 將第二個節點添加爲第一個子節點。 （我假設這不是一個二叉搜索樹，所以孩子的順序並不重要，如果這是一個二叉搜索樹，那麼你可以根據你找到的設置合適的子指針）。

要找到樹的根，可以創建一組作爲根節點的候選者的節點，該節點最初是樹中的每個節點。然後，您可以遍歷迄今爲止構建的節點。每次發現節點v是另一個節點u的子節點時，都可以從候選根集合中刪除節點v（因爲它是一個孩子）。當你完成後，你將留下所有可能的根。如果邊界列表確實定義了二叉樹，則這只是一個節點。如果它定義了二叉樹的森林，這會讓你回到森林中所有樹的根。總的來說，這需要O（n）個時間，其中n是邊的數量（也是樹中的節點數，因爲二叉樹中的邊數是節點數減1）。

如果您願意，您可以將這兩個通行證放入一個通行證;爲了便於表達，我只是分別描述了它們。

希望這會有所幫助！

Answer 2

首先你在地圖上標註節點ID，以連接節點
的名單，然後iterage通過地圖和創造，在地圖

，如果它是一個二叉樹，從您的信息鏈接，然後有文件中缺少信息，應該有格式

父，leftChild，rightChild或
或左右總是在相同的順序（左第一），每個節點的兩排，第二下一行。