二叉樹O（n）的InOrder樹遍歷的時間複雜度？

public void iterativePreorder(Node root) { 
     Stack nodes = new Stack(); 
     nodes.push(root); 

     Node currentNode; 

     while (!nodes.isEmpty()) { 
       currentNode = nodes.pop(); 
       Node right = currentNode.right(); 
       if (right != null) { 
         nodes.push(right); 
       } 
       Node left = currentNode.left(); 
       if (left != null) { 
         nodes.push(left);  
       } 
       System.out.println("Node data: "+currentNode.data); 
     } 
}

來源：維基樹遍歷二叉樹O（n）的InOrder樹遍歷的時間複雜度？

是時間複雜度將是O（N）？如果使用遞歸完成時間複雜度會是相同的嗎？

新問題：如果我用上面的代碼從TreeA中找到某個節點來創建另一個樹TreeB，它將具有與TreeA一樣多的節點，那麼創建TreeB的複雜度爲O（n^2）因爲它是n個節點，每個節點將使用上面的代碼是O（n）？

來源

2012-03-11 Dan

是的，因爲你一次擊中了樹中的N個元素。 – 2012-03-11 20:47:45

1.請分別提出新問題。 2.我不明白TreeB應該如何創建...... – thkala 2012-03-11 21:54:31

由於二進制樹的遍歷（相對於所述搜索和大多數其他樹操作）要求所有樹節點被處理，任何遍歷算法的最小複雜度是O（n），即線性WRT樹中節點的數量。這是一個不可改變的事實，在一般情況下不會改變，除非有人構建量子計算機或其他東西...

至於遞歸，唯一的區別是遞歸方法調用通過推送調用框架隱式地構建堆棧到JVM堆棧，而您的示例代碼顯式構建堆棧。我寧願不推測這兩者之間的性能差異 - 您應該爲每個特定用例場景描述和基準測試兩種選擇。

來源

2012-03-11 20:48:14 thkala

二叉樹O（n）的InOrder樹遍歷的時間複雜度？

回答

相關問題