高效刪除樹數據結構

樹的根有沒有父母ANS以前沒有兄弟姐妹（它可以旁邊的兄弟姐妹）。
每個節點都有唯一的父節點。
每個節點都有一個指向它的下一個和上一個兄弟，孩子和父母的指針。

此樹數據結構正在填充數百萬個節點。當我刪除一棵樹有大量的節點時，會引發堆棧溢出異常。當節點數量相對較少或建立在發佈模式時，數據結構運行良好。

這是一個節點的析構函數：

Entity::~Entity(void) 
    { 
     Entity* child = NULL; 

     if (firstChild != NULL) 
      child = firstChild->getNextSibling(); 

     while(child != NULL) 
     { 
      delete child->getPreviousSibling(); 
      child->setPreviousSibling(NULL); 

      child = child->getNextSibling(); 
     } 

     if (lastChild != NULL) 
      delete lastChild; 

     if (isRoot()) 
     { 
      if (nextSibling != NULL) 
      { 
       nextSibling->setPreviousSibling(NULL); 
       delete nextSibling; 
      } 
     } 
    }

一個可以實現非遞歸算法遍歷樹並刪除所有它的節點。

你能否建議一個高效的後序遍歷算法來刪除一個非二叉樹？

來源

2012-02-13 Ghassen Hamrouni

另一種方法（使用額外內存）是通過節點存儲對數組或專用鏈接列表中的所有樹節點的引用，並根據該節點而不是樹結構進行刪除。 – 2012-02-13 18:50:17

您應該保留原始代碼，否則問題無法理解。您現在公開的代碼（未接受我的答案），**不會引發任何堆棧溢出，正如您已經測試的那樣。 – CapelliC 2012-02-14 11:25:41

不幸的是，原始代碼和代碼會引發堆棧溢出。但你的代碼更清晰... – 2012-02-14 12:50:16

編輯：錯過了有關向父節點返回指針的位。這意味着我們不需要維護路徑歷史來回溯，我們可以取消堆棧。

node = root; 
while (node) 
{ 
    if (node->firstChild) 
    { 
     next = node->firstChild; 
     node->firstChild = null; 
    } 
    else 
    { 
     next = node->nextSibling ? node->nextSibling : node->parent; 
     delete node; 
    } 
    node = next; 
}

原來的答覆：

什麼可以做遞歸，你可以用一個循環和堆棧做。雖然這不需要更少的內存，但優點是可以將該內存放在堆上並避免溢出。

s.push(root); 
while (!s.empty()) 
{ 
    node = s.pop(); 
    if (node->nextSibling) s.push(node->nextSibling); 
    if (node->firstChild) s.push(node->firstChild); 
    delete node; 
}

來源

2012-02-13 22:24:42

我認爲這不是'工作：當它回到父母，刪除兒子後，它仍然有firstChild設置，但指向釋放節點。 – CapelliC 2012-02-14 10:52:57

@chac你是對的，謝謝。固定（我希望;））。 – 2012-02-14 11:00:51

我會嘗試一些簡單得多，而且讓遞歸析構函數行使職責：

Entity::~Entity(void) 
{ 
    Entity* child = firstChild; 
    while (child) { 
     Entity *succ = child->getNextSibling(); 
     delete child; 
     child = succ; 
    } 
}

來源

2012-02-13 18:38:41 CapelliC

你的算法比我的更簡單，但不幸的是它並不能解決我的特殊問題。 – 2012-02-13 18:49:32

我用你的建議更新了我的算法 – 2012-02-13 18:50:01

我提出了這個簡化，因爲我不確定你以前的，特別是最後一部分的正確性（類似於刪除lastChild ...），現在堆棧使用非常有限：只有2個指針* max_tree_deepth。你是否已經驗證了堆棧溢出？ – CapelliC 2012-02-13 19:27:34

您可以嘗試創建一個靜態函數來做刪除。我發現在以前的應用程序中，要求大樹對象執行任務可能比使用獨立功能在樹上執行操作要慢很多。靜態函數本質上是全局的，所以遞歸調用確切地知道去哪裏。使用遞歸「方法」需要通過每個對象查找函數，這可能會增加額外的開銷，特別是對於像這樣緩存不友好的操作。沿着同樣的路線，如果違反界面以避免對每個對象執行getNextSibling（）調用並使程序流完全保留在一個全局遞歸函數中，您可能會獲得更好的性能。

這不是遞歸本身，而是你的指令管道在你通過這棵樹運行時不斷拖延數據訪問。

來源

2012-02-13 19:31:57 phkahler

再次想到，無論何時「刪除」，都必須執行析構函數查找。這可以通過將它們全部鏈接到實際上未被刪除的單個列表中來避免。 – phkahler 2012-02-13 19:35:14

考慮一下，你是否真的需要打擾走樹和處理每個節點。

我經常發現爲特定任務設置一個專用內存池很方便，然後一旦完成就可以一次釋放整個池。

來源

2012-02-13 21:35:41 doynax

下面是一個非遞歸溶液的草圖：

初始化一個指向與根指針的節點;
重複
- 如果當前節點有一個兒子，移動到那個兒子;
- 否則，刪除當前節點並返回其父節點（如果有的話）;
直到當前節點沒有父節點。

來源

2012-02-13 22:15:55

或者，您可以簡單地增加堆棧大小。

在Windows和Visual C++中，默認值是微不足道的1 MB - 只是將其增加到10 MB甚至100 MB - 此內存實際上不會是承諾直到（並且除非）您真的需要它， d只是預先保留（請參閱/STACK選項）。你甚至可以選擇性地僅對Debug配置進行操作，以解釋那裏的「更胖」堆棧。

來源

2012-02-15 01:38:11

高效刪除樹數據結構

回答

相關問題