使用堆棧的二叉搜索樹的樹遍歷算法

Question

我的輸入結果爲24, 4, 2, 3, 9, 10, 32，我得到如下結果2, 3, 4, 24。我正在使用堆棧。當我手動檢查該程序時，即使有右子樹，節點也不會通過棧4上的else if。

public void inorderNonRcursive(Node root){ 

    Stack s = new Stack(); 
    Node node = root; 
    Node k; 
    int c=0; 

    if(node != null) { 
     s.push(node);  
    } 

    while(!s.stack.isEmpty()) { 

     //node=(Node) s.stack.get(s.stack.size()-1); 
     System.out.println("first condition" + (node.getleft() != null && (node.getVisited() == false)) + "second condi" + (node.getRight() != null)); 

     if(node.getleft() != null && (node.getVisited() == false)) { 
      node = node.getleft(); 
      s.push(node); 
      System.out.println(" from 1   "+(++c)); 

     } else if(node.getRight() != null) { 
      k = s.pop(); 
      System.out.println(k.getvalue()); 
      node=node.getRight(); 
      s.push(node); 
      System.out.println(" from 2   "+(++c)); 

     } else { 
      k = s.pop(); 
      System.out.println(k.getvalue()); 
      System.out.println("  from 3  "+(++c)); 
     } 

    } 

} 

Answer 1

享受對我來說，有兩個問題在設計：

1. 算法似乎是遞歸一個適合迭代和
2. 的Node類知道是參觀。

這裏是一個不同的解決方案（你需要去適應它了一下）：

// Inorder traversal: 
// Keep the nodes in the path that are waiting to be visited 
Stack s = new Stack(); 
// The first node to be visited is the leftmost 
Node node = root; 
while (node != null) 
{ 
    s.push(node); 
    node = node.left; 
} 
// Traverse the tree 
while (s.size() > 0) 
{ 
    // Visit the top node 
    node = (Node)s.pop(); 
    System.out.println((String)node.data); 
    // Find the next node 
    if (node.right != null) 
    { 
     node = node.right; 
     // The next node to be visited is the leftmost 
     while (node != null) 
     { 
      s.push(node); 
      node = node.left; 
     } 
    } 
} 

參考回到我的第一個評論，你不說你寫的僞代碼和測試它。我認爲這是編寫新算法的關鍵步驟。

Answer 2

這看起來像一個類練習，旨在幫助您瞭解二叉樹。

在您編寫任何代碼之前，繪製您的樹的圖片，並在每個節點處添加一個值，例如「A」，「B」，「C」等。然後從根節點開始，需要按順序訪問每個節點。寫下你在僞代碼中學到的東西，並通過做它所說的來測試它。確保你測試了每個節點可以想到的所有不同情況（至少應該有三個）。在你的樹上放大約七個節點。

現在你可以開始你的代碼。輸入您的僞代碼作爲註釋，然後在每個註釋之間插入Java代碼。

:-)