java - ツリーの再帰的および非再帰的トラバース

Question

二分探索木で再帰的および非再帰的なプレオーダートラバーサルを実行しても同じ結果が得られません

再帰的方法

public static void preorder(TreeNode root) {
    if (root == null)
        return;
    else {
        System.out.print(root);
        inorder(root.getLeftPtr());
        inorder(root.getRightPtr());
    }
}

非再帰的方法

public static void preorder2(TreeNode root){
    if(root==null)return;
    Stack<TreeNode> stack=new Stack<TreeNode>();

    while(true){
        while(root!=null){
            //process current Node
            System.out.print(root);
            stack.push(root);
            root=root.getLeftPtr();
        }
        if(stack.isEmpty())break;
        root=stack.pop();
        root=root.getRightPtr();
    }

}

結果

      recursive method-> 10-> 5-> 6-> 8-> 12-> 15-> 20
  non recursive method-> 10-> 6-> 5-> 8-> 15-> 12-> 20

Answer 1

あなたの再帰的な方法はこのようにすべきだと思います、

public static void preorder(TreeNode root) {
    if (root == null)
        return;
    else {
        System.out.print(root);
        preorder(root.getLeftPtr());
        preorder(root.getRightPtr());
    }
}

Answer 2

これがプレオーダーツリートラバーサルの非再帰的実装です

public void preorderDisplay(Node root) {
    Node current = root;
    LinkedList<Node> stack = new LinkedList<>();
    while (true) {
        if (current != null) {
            stack.push(current);
            System.out.print(current.data + " ");
            current = current.left;
        } else if (!stack.isEmpty()) {
            current = stack.poll();
            current = current.right;
        } else {
            break;
        }
    }
}

Answer 3

Javaでのツリートラバーサルの非再帰的実装を事前注文します。

public static void preTraverseNoRec(Node root){
    Stack<Node> stack = new Stack<eNode>();
    stack.push(root);
    while(stack.size()!=0) {
        Node node = stack.pop();
        System.out.println(node.data);
        if(node.right != null) stack.push(node.right);
        if(node.left != null) stack.push(node.left);
    }
}

ノードは次のように定義されます：

public class Node {
    int data;
    Node left, right, nextRight;

    Node(int item)
    {
        data = item;
        left = right = nextRight = null;
    }
}

Answer 4

＃簡略化

public static void preorder(TreeNode root) {
    if (root != null) {
        System.out.print(root);
        preorder(root.getLeftPtr());
        preorder(root.getRightPtr());
    }
}

http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/