從只有深度和最底層兒童信息的節點構建樹

我正在重寫一箇舊項目。出於神祕原因（遺留公司數據庫，無法更改），樹狀數據以特殊方式存儲在數據庫中：每個節點都定義了兩個屬性：節點深度和最底層深度子節點的列表。從只有深度和最底層兒童信息的節點構建樹

我將如何處理轉換爲常規樹？我目前正處於將所有節點放置在樹中的級別，但我現在處於虧損狀態。有一件事我想到的是從最深層次上添加節點並上到根節點，但是這與很多懸掛節點和調整樹的大小息息相關。

編輯：剛纔意識到我的方法將涉及檢查每個低級別節點的組合，以找到一個子級總和等於高級級別的節點。不。

只需對深度上的節點進行排序並逐級插入節點即可。

只有一個根（深度0或1，取決於您的輸入），所以第一步很簡單。

在通用步驟中，您需要將下一級別的每個節點分配給正確的父級。標準很簡單：子節點的最底層子節點是父節點最底層子節點的子集。如果運行時間不是問題，只需檢查每個子節點與所有父節點，直到找到匹配。如果這太慢了，請添加一條評論，我會再考慮一些;-)

2013-09-25 07:12:35

''只是檢查每個子節點對所有父節點「 - 爲什麼你要這樣做，如果可以的話，如你所說，只要檢查一個孩子的祖先是否包含在父輩的祖先之內？ – Dukeling

@Dukeling通過父節點，我的意思是所有深度爲「i」的節點，並且由子節點表示深度爲「i + 1」的所有節點。據我所知，沒有簡單的方法來決定一個孩子屬於哪個父母，所以你需要全部嘗試，看看你有哪個子集。 –

嗯，你只需要檢查一個孩子的祖先是否包含在祖先的祖先內（只要節點是唯一的，這個檢查就足夠了）（這將是O（n）而不是O（n^2）），或O（log n）而不是O（n）（如果使用排序列表（與本機檢查全部節點，即交集進程相比））。 – Dukeling

回答