树的递归和非反复遍历

通过在二叉搜索树上执行递归和非递归前序遍历，我得不到相同的结果

递归方法

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 stack=new Stack(); 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

这是preorder树遍历非递归实现

 public void preorderDisplay(Node root) { Node current = root; LinkedList 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 stack = new Stack(); 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

#Simplified

 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/