使用堆栈的二叉搜索树的树遍历算法

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代码。

:-)