二叉树遍历非递归写法

二叉树递归遍历

public class recursiveTraversalBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	//递归顺序
	public static void f(Node head) {
		if (head == null) {
			return;
		}
		// 1 前序
		f(head.left);
		// 2 中序
		f(head.right);
		// 3 后序
	}

	// 先序打印所有节点
	public static void pre(Node head) {
		if (head == null) {
			return;
		}
		System.out.println(head.value);
		pre(head.left);
		pre(head.right);
	}

	public static void in(Node head) {
		if (head == null) {
			return;
		}
		in(head.left);
		System.out.println(head.value);
		in(head.right);
	}

	public static void pos(Node head) {
		if (head == null) {
			return;
		}
		pos(head.left);
		pos(head.right);
		System.out.println(head.value);
	}

}

如何用非递归方式遍历呢？

public class unRecursiveTraversalBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	/*
		1. 首先，构造一个辅助栈，将头结点入栈
		2. 开始循环，条件：栈不为空
		3. 出栈，并记录出栈的结点，打印
		4. 如果此结点右子树存在，入栈
		5. 如果此结点左子树存在，入栈
		6. 返回3
	*/
	public static void pre(Node head) {
		System.out.print("pre-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(head);
			while (!stack.isEmpty()) {
				head = stack.pop();
				System.out.print(head.value + " ");
				if (head.right != null) {
					stack.push(head.right);
				}
				if (head.left != null) {
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}


	/*
		1. 对于上边先序遍历，先右子树入栈，再左子树入栈，最后输出结果为：头、左、右
		2. 那么，如果先左子树入栈，再右子树入栈，最后输出结果就为：头、右、左
		3. 将 【头、右、左】 顺序不输出，再存入一个栈，最后输出，就能得到后序
	*/
	public static void pos1(Node head) {
		System.out.print("pos-order: ");
		if (head != null) {
			Stack<Node> s1 = new Stack<Node>();
			Stack<Node> s2 = new Stack<Node>();
			s1.push(head);
			while (!s1.isEmpty()) {
				head = s1.pop(); // 头 右 左
				s2.push(head);
				if (head.left != null) {
					s1.push(head.left);
				}
				if (head.right != null) {
					s1.push(head.right);
				}
			}
			// 左 右 头
			while (!s2.isEmpty()) {
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

	public static void pos2(Node h) {
		System.out.print("pos-order: ");
		if (h != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			Node c = null;
			while (!stack.isEmpty()) {
				c = stack.peek();
				if (c.left != null && h != c.left && h != c.right) {
					stack.push(c.left);
				} else if (c.right != null && h != c.right) {
					stack.push(c.right);
				} else {
					System.out.print(stack.pop().value + " ");
					h = c;
				}
			}
		}
		System.out.println();
	}

	/*
		1. 初始化构造一个栈
		2. 循环，条件：栈不为空 或者 当前结点不为空
		3. 如果当前结点不为空，当前结点入栈，并指向它的左子结点
		4. 否则，栈顶出栈，记为当前结点，然后当前结点指向它的右子树
		5. 循环3
	*/
	public static void in(Node cur) {
		System.out.print("in-order: ");
		if (cur != null) {
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || cur != null) {
				if (cur != null) {
					stack.push(cur);
					cur = cur.left;
				} else {
					cur = stack.pop();
					System.out.print(cur.value + " ");
					cur = cur.right;
				}
			}
		}
		System.out.println();
	}

}