十四.实现二叉树的先序、中序、后序遍历，包括递归方式和非递归 方式

【题目】

实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式

【分析】

先序遍历：中左右

非递归的思路：1.建立一个栈存放结点；2.栈中不为空的时候，弹出节点并且打印，相当于打印的是中间的位置；3.先压入的是弹出节点的右节点，在压入左节点（保证弹出的时候左节点先打印）。

中序遍历：左中右

非递归的思路：
不为空的话，入栈，节点一直向左移动；为空的话，出栈，打印，节点向右移动。

后序遍历：左右中

非递归的思路：
1.先构造中右左的结构（就是先序遍历中先放左孩子，再放右孩子）；
2.在准备一个栈，调换一下顺序就变成了左右中结构

【先序遍历代码实现】

//1.构造节点结构
	public static class Node{
		int value;
		Node left;
		Node right;
		public Node(int data) {
			this.value=data;
		}
	}
	
	//2.先序遍历递归（中左右）
	public static void preOrderRecur(Node head) {
		if (head==null) {
			return;
		}
		System.out.print(head.value+" ");
		preOrderRecur(head.left);
		preOrderRecur(head.right);
	}
	
	//3.先序遍历非递归（中左右）
	public static void preOrderUnRecur(Node head) {
		if(head!=null) {
		//3.1 建立一个栈结构，把第一个压进去
			Stack<Node> stack=new Stack<>();
			stack.add(head);
			while(!stack.isEmpty()) {
			//3.2 栈中不为空的话，弹出一个（就是头结点），打印了中间的节点
				cur=stack.pop();
				System.out.print(cur.value+" ");
				//3.3 当前弹出的节点的右节点压进去
				if (cur.right!=null) {
					stack.push(head.right);
				}
				//3.3 当前弹出的节点的左节点压进去，出来的时候想出来左节点 保证了中左右的顺序
				if (cur.left!=null) {
					stack.push(cur.left);
				}
			}
		}
		System.out.println();
	}

【中序遍历代码实现】

//1.构造节点结构
	public static class Node{
		int value;
		Node left;
		Node right;
		public Node(int data) {
			this.value=data;
		}
	}
	
	//2.中序遍历递归（左中右）
	public static void inOrderRecur(Node head) {
		if (head==null) {
			return;
		}
		inOrderRecur(head.left);
		System.out.print(head.value+" ");
		inOrderRecur(head.right);
	}

    //3.中序遍历非递归（左中右）
	public static void inOrderUnRecur(Node head) {
			if (head!=null) {
				Stack< Node> stack=new Stack<>();
				while(head!=null||!stack.isEmpty()) {
				//1.如果节点不为空，压栈，下一步是她的左孩子（找到最左）
					if(head!=null) {
						stack.push(head);
						head=head.left;
					}
					//2.如果节点为空，出栈，打印，下一步是她的右孩子
					else {
						Node cur = stack.pop();
						System.out.print(cur.value+" ");
						cur=cur.right;
					}
				}
			}
			System.out.println();
		}

【后序遍历代码实现】

				//1.后序遍历递归（左右中）
				public static void posOrderRecur(Node head) {
					if (head==null) {
						return;
					}
					posOrderRecur(head.left);
					posOrderRecur(head.right);
					System.out.print(head.value+" ");
				}
				
			//2.后序遍历非递归（左右中）
				public static void posOrderUnRecur(Node head) {
					if (head!=null) {
						Stack<Node> stack1=new Stack<>();
						Stack<Node> stack2=new Stack<>();
						stack1.push(head);
						while(!stack1.isEmpty()) {
							Node cur=stack1.pop();
							//弹出一个压一个
							stack2.push(cur);
							if (cur.left!=null) {
								stack1.push(cur.left);
							}
							if(cur.right!=null) {
								stack1.push(cur.right);
							}
						}
						while(!stack2.isEmpty()) {
							System.out.print(stack2.pop().value+" ");
						}
					System.out.println();
					}
				}