樹結構中樹葉的計算索引

給定樹（二進制）結構，深度爲N.是否可以計算映射葉節點的某些查找索引。樹結構中樹葉的計算索引

每個節點都知道它的父節點和它的子節點（左邊和右邊），如果它不是葉。

我的想法就像說rootnode是索引0，然後左：1，左：左：2，左：左：3，左：左：右：4，左：右：左：5，左：右：右：6，右：7，右：左：8例如

因此，給定一個葉節點，我該如何計算最智能的索引。

其他解決方案也被接受，如果它更聰明地給出葉子索引從0,1 ... L，其中L是葉子的數量。

2012-03-10 Poul K. Sørensen

如果你想在一個數組中表示一棵樹，最簡單的方法是一次一層地取樹。

 0 
    /\ 
    / \ 
    1  2  [0, 1, 2, 3, 4, 5, 6] 
/\ /\ 
3 4 5 6

這樣，找到父母很簡單：(index-1)/2。找到這兩個孩子只是2*index和2*index + 1。

來源

2012-03-10 18:33:05

我的樹是在外部庫中生成的。它確實是遞歸的，左邊的計算然後右邊的計算。然後我想計算一個更快找到葉節點的映射。所以當通過一個葉節點時，我需要通過詢問它的父母是什麼來找到它的索引。我想這樣做是因爲它更快地在父節點上迭代N個步驟，而不是迭代樹中的所有節點以找到節點。原因是我需要存儲一些附加信息鏈接到葉節點，我不能擴展類。 – 2012-03-10 18:44:24

謝謝，我需要這樣一個想法 – 2012-04-26 14:58:42

在我的樹結構（四叉樹和八叉樹）中，我使用了每個節點索引的二進制表示。例如每個維度爲32位（最大32級）。所以我可以通過公式計算葉的完整索引（或路徑）

path.x =（unsigned int）（leaf.position.x * pow（2,32））;

leaf.position.x musst是從0的範圍內... 1

唯一的約束（我認爲）此方法是，你是存儲數據musst是在特定範圍內，從而使你可以根據你的區域大小來區分它。如果這是可能的你的用例閱讀更多在 Simple and Efﬁcient Traversal Methods for Quadtrees and Octrees

來源

2012-03-10 19:23:12 Smittii

我的確在考慮利用位來創建路徑，但是我的樹比32位要深一些。現在我只是先計算從左到右迭代的索引，然後在達到新葉時給它們索引++。 – 2012-03-11 05:39:31

樹結構中樹葉的計算索引

回答

相關問題