使用堆栈的二叉搜索树的有序树遍历算法 [英] Inorder Tree Traversal algorithm for a Binary Search Tree using Stack

问题描述

我的输入结果为24, 4, 2, 3, 9, 10, 32，而我得到的结果为2, 3, 4, 24.

My inputs results 24, 4, 2, 3, 9, 10, 32, and I am getting following result 2, 3, 4, 24.

我正在使用 stack .当我手动检查了该程序后，即使具有正确的子树，该节点也不会在堆栈上的4处通过else if.

I am using a stack. When I have manually checked this program the node is not going through else if at 4 on stack, even if has right sub tree.

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)); 
        }  

    }

}

推荐答案

对我来说，设计中存在两个问题:

To me, there are two problems in the design:

1. 该算法似乎是适用于迭代的递归算法，并且
2. Node类知道有关被访问的信息.

1. The algorithm seems to be the recursive one adapted for iteration and
2. The Node class knows about being visited.

这是另一种解决方案(您需要对其稍作调整):

Here is a different solution (you will need to adapt it a bit):

// 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;
        }
    }
}

回到我的第一个评论中，您并不是说您编写了伪代码并对其进行了测试.我认为这是编写新算法的关键一步.

Referring back to my first comments, you don't say you wrote pseudo code and tested it. I think this a key step in writing new algorithms.

这篇关于使用堆栈的二叉搜索树的有序树遍历算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！