索引：使用數組/矢量實現樹數據結構

Question

我一直在使用矢量在C++中實現一個堆。由於我必須輕鬆訪問節點（2n，2n + 1）的子節點，因此我必須從索引1開始。這是正確的方法嗎？根據我的實現，在第零個位置總是有一個虛擬元素。

Answer 1

你的方式有效。另外，您可以在索引0有根，並在2n+1和2n+2

Answer 2

有孩子雖然這可以很好地用於堆，你最終使用一個巨大的其他樹的數據結構冗餘內存量不一定有一個全面和完整的二叉樹。例如，這意味着如果您有一個包含20個節點且深度爲5的二叉搜索樹，則最終必須使用2^5 = 32而不是20的數組。現在想象一下，如果您需要一個包含25個節點的樹深度爲22.您最終將使用大量的4194304陣列，而您可以使用鏈接表示來存儲25個節點。

您仍然可以使用數組而不會產生這樣的內存命中。只需將一大塊內存分配爲一個數組，並將數組索引用作指向子節點的指針。

因此，如果你有

node.left = (node.index*2) 
node.right = (node.index*2+1) 

您只需使用

node.left = <index of left child> 
node.right = <index of right child> 

或者，你可以使用指針/引用，而不是整數索引到一個數組，如果你的語言支持它。

編輯：

，一個完整的二叉搜索樹佔據了O（2^d）內存它可能不是有目共睹的。有d個級別，每個級別的節點數量是其父級級別的兩倍（因爲除底部的節點外，每個節點只有兩個孩子 - 從來沒有一個）。 A binary heap是一個binary tree（但不是二進制搜索樹），它總是按定義完成的，所以由OP概述的基於數組的實現不會產生任何實際的內存開銷。對於堆來說，這是在代碼中實現它的最佳方式。 OTOH，大多數其他二叉樹（特別是二叉搜索樹）不保證是完整的。所以試圖使用這種方法需要O（2 ^深度）的內存，其中深度可以與n一樣大，在鏈接實現中我們只需要O（n）內存。

所以我的回答是：是的，這是堆的最佳方式。只是不要嘗試用於其他二叉樹（除非你確定它們將始終完整）。