迭代深化首先使用有限的內存搜索

Question

這是Find first null in binary tree with limited memory的後續行動。

維基百科說，迭代加深深度優先搜索將找到最短路徑。我想要一個內存限制爲k個節點的實現，並且訪問樹的次數最少。

舉例來說，如果我的二叉樹是：

  0 
    1    2 
3 4  5  6 
7 8 9 10 11 12 13 14 

而且我有限的內存比我的搜索順序5個節點是：

mem[0] = read node 0 
mem[1] = read node 1 
mem[2] = read node 2 
mem[3] = read node 3 
mem[4] = read node 4 //Now my memory is full. I continue... 
mem[3] = read node 5 //overwrite where I stored node 3 
mem[4] = read node 6 //overwrite where I stored node 4 

現在，如果我的下一個讀是7，我需要重新閱讀3.但是，如果我將下一個閱讀到14，那麼我不需要重新閱讀3。如果解決方案是在14，這將使我的算法快一點！

我正在尋找一個通用的解決方案;可以用於任何大小的內存和每個節點的分支數量。

Answer 1

如果您的節點鏈接到其父母，並且節點的子節點將始終按照相同的順序枚舉，則可以在不保存節點的情況下跟蹤您的步驟。