作業：二叉樹 - 水平順序traversversal

Question

有沒有辦法從最低級別訪問二叉樹到更高（根）？

不是從根級到最低級!!!

（而不是使用水平序遍歷和堆棧... !!!）< ---它的反面..

這麼難...謝謝！

Answer 1

提供我正確理解你的問題：如果你想遍歷樹首先訪問a葉子和最後根，你可以在遍歷樹的時候訪問返回的節點。

function traverse(node) 
    for each child of node 
     traverse(child) 
    end 
    visit(node) 
end 

如果你想參觀平次序的節點，你可以做這樣的事情（雖然使用堆棧 - 我不知道您是否使用了不想要一個在全部或部分特定的解決方案堆棧）：

queue.push(root) 
while queue is not empty 
    node = queue.pop() 
    for each child of node 
     queue.push(child) 
     stack.push(child) 
    end 
end 
while stack is not empty 
    visit(stack.pop()) 
end 

可以使用只隊列，但糟糕的時間複雜度做到這一點，如果你不喜歡這樣寫道：

for i = treedepth down to 0 
    queue.push(root) 
    while queue is not empty 
     node = queue.pop() 
     if node has depth i 
      visit(node) 
     else 
      for each child of node 
       queue.push(child) 
      end 
     end 
    end 
end 

樹如果需要，可以使用初始遍歷找到深度和節點級別。

但是，如果您允許進行遞歸調用，您實際上可以訪問堆棧（調用堆棧）。這可以被利用來實現第二種解決方案，但是使得堆棧隱含。

function unwind(queue) 
    if queue is not empty 
     node = queue.pop() 
     unwind(queue) 
     visit(node) 
    end 
end 

queue.push(root) 
while queue is not empty 
    node = queue.pop() 
    for each child of node 
     queue.push(child) 
     queue2.push(child) 
    end 
end 

unwind(queue2) 

和當然，如果你有機會到幾乎任何其他數據結構（列表，數組，優先級隊列，雙端隊列等），你可以很容易地實現自己的堆棧。但是，首先禁止堆棧是毫無意義的。

Answer 2

你可能很容易做到這一點如果你維護了一個指向最深處節點的指針。如果你不這樣做，那麼你必須在開始遍歷之前找到該節點。此外，你的節點都必須有指向父母的指針。

Answer 3

這裏有導致不同的解決方案的幾個挑戰：

1. 可以遍歷了樹？通常情況下，數據結構是建立起來的，所以你只能停下來。您可以找到所有葉節點，將它們按級別放入優先級隊列中，然後遍歷。

2. 您可以存儲O（n）個附加數據嗎？您可以按照普通的寬度優先方式遍歷它，像先前的解決方案一樣，將指針插入優先級隊列中，但這次是在初始遍歷期間插入所有節點。這將增加在遍歷期間使用的輔助數據的最大大小。

3. 樹是否保證平衡和充滿，就像它可能在堆狀樹中一樣？如果是這樣，你可以通過簡單的方式遍歷它，只要去正確的地方。

Answer 4

我以更好的方式解釋。我有一個代數表達式樹（所以不平衡）。我必須使用一個隊列（只有一個隊列）來評估它。我問這個問題，因爲我覺得唯一的辦法是採取從最低級別開始節點，直到根...

例如： 樹（+（*（2）（2））（3））

我排隊和：

enqueue（1）; enqueue（2）;

（*）-----> dequeue;出隊;結果= 2 * 2;入列（結果）; 入隊3; （+）----->出隊;出隊;結果= 4 + 3;給出結果;

所以我需要有這個遍歷：2; 2; *; 3; +

我不知道這是否是明確的......

Answer 5

隊列只有從根遍歷水平，以樹的葉子非常有用。

您可以使用深度優先遍歷打印某個級別。 像這樣：

void printLevel(BinaryTree *p, int level) { 
    if (!p) return; 
    if (level == 1) { 
    cout << p->data << " "; 
    } else { 
    printLevel(p->left, level-1); 
    printLevel(p->right, level-1); 
    } 
} 

打印從葉達根各級，你需要找到樹的最大深度。這可以使用深度優先遍歷來輕鬆完成（您可以輕鬆地谷歌解決方案）。

void printLevelOrder(BinaryTree *root) { 
    int height = maxHeight(root); 
    for (int level = height; level >= 1; level--) { 
    printLevel(root, level); 
    cout << endl; 
    } 
} 

運行時間複雜度令人驚訝的是O（N），其中N是節點的總數。

欲瞭解更多信息和運行時間複雜度分析，請參閱下面的頁面：

http://www.ihas1337code.com/2010/09/binary-tree-level-order-traversal-using_17.html