如何迭代四/十進制樹

Question

我很難掌握如何迭代八叉樹或四元組。這可能是因爲我沒有經歷過不同的迭代神話。但假設我生成了一個包含float x，y，z的四叉樹;雙色。現在，我們還要說，這個節點一次只能產生4個孩子（並且這些孩子可以產生4個孩子等等），直到達到7個級別（以便孩子不能再創造孩子，但是它的孩子兄弟/姐妹可以），所有4個孩子創建的dword顏色是相同的（如果發生這種情況，它的兄弟姐妹仍然可以生產），或者創建的總節點等於87380.當上述情況發生時，容器。這個過程還在繼續。

現在這個容納節點的容器是（例如）7層深的，兒童的所有孩子都有不同的x，y，zs和顏色。我遇到的問題是我如何迭代這個容器，我怎麼能通過所有的孩子，姐妹？由於根可以導致4個孩子，並且這4個孩子有4個孩子等等，等等：4^1 + 4^2 .... + 4^7。如何在不編寫複雜if語句的情況下找到我想要的節點，並遍歷整個節點（從根開始）？容器（產生節點的那個容器）是否需要額外的代碼來讓這個過程變得簡單？

對不起，如果問題是一般的。

Answer 1

遍歷整個樹很容易，你可以遞歸地做。

void iterate(node *n) { 
    // do something with n 
    if (n->child1 != NULL) iterate(n->child1); 
    if (n->child2 != NULL) iterate(n->child2); 
    if (n->child3 != NULL) iterate(n->child3); 
    if (n->child4 != NULL) iterate(n->child4); 
} 

然後調用iterate(root)和do something會發生在四叉樹的每個節點上。

我懷疑這實際上並不是你要問的，但是。如果這就是你所做的一切，那麼將數據保存在四叉樹中是沒有意義的。如果你想找到四叉樹中的一個特定節點，那麼你需要別的東西。假設你想在四叉樹中找到一個點x,y。從點（其中僅存儲在葉

void find(node *n, float x, float y) { 
    if (x == n->x && y == n->y) // you've found it! 
    if (x < n->x) { 
     if (y < n->y) { 
      if (n->child1 != NULL) { 
       find(n->child1, x, y); 
      } else { 
       // point not in quadtree 
      } 
     } else { 
      ...same, but child2 
     } 
    } else { 
     ...same, child3 & 4 
    } 
} 

注意四叉樹一般都不會分裂他們自己存儲點通過存儲分裂，它們通常被分成單獨的座標：那你這樣做四叉樹）。例如，請參閱wikipedia picture。