二叉树整理

/* * 分别用递归和非递归方式实现二叉树先序、中序和后序遍历 【题目】 用递归和非递归方式，分别按照二叉树先序、中序和后序打印所有的节点。 * 我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。 */ 二叉树样例： 递归的过程： 1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1 由上可知每个节点访问3次

二叉树的3个遍历： 先序： 1 2 4 5 3 6 7 中序： 4 2 5 1 6 3 7 后序： 4 5 2 6 7 3 1

创建二叉树的相应节点：

public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } }

递归代码如下：

先序遍历：

public static void preOrderRecur(Node head){ if(head == null){ return; } System.out .print(head.value + ""); preOrderRecur(head.left); preOrderRecur(head.right); }

中序遍历：

public static void inOrderRecur(Node head) { if(head == null){ return; } inOrderRecur(head.left); System.out .print(head.value + ""); inOrderRecur(head.right); }

后序遍历：

public static void posOrderRecur(Node head) { if(head == null){ return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out .print(head.value + ""); }

以下为非递归的详细讲解： 先序（根左右）：有右节点先压右然后在压左节点 一下是思路模拟：

public static void preOrderUnRecur(Node head){ System.out.print("pre-order: "); if(head != null){ Stack<Node> stack = new Stack<Node>(); stack.add(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(); }

中序遍历（左根右）：当前节点为空从栈拿一个打印当前节点往右跑，若当前节点不为空入栈当前节点往左 模拟如下：

public static void inOrderUnRecur(Node head){ System.out.print("in-order: "); if(head != null){ Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty() || head != null){ if(head != null){ stack.push(head); head = head.left; }else { head = stack.pop(); System.out.print(head.value + " "); head = head.right; } } } System.out.println(); }

后序遍历： 先序遍历是中左右 先压右孩子在压左孩子，那么我们想实现中左右的遍历我们仅需先压左后压右，后序遍历是左右中那么我们仅需要在利用一个栈把中右左存进去。

public static void posOrderUnRecur1(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(); }

总体代码：

package basic_class_01; import java.util.Stack; /* * 分别用递归和非递归方式实现二叉树先序、中序和后序遍历 【题目】 用递归和非递归方式，分别按照二叉树先序、中序和后序打印所有的节点。 * 我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。 */ public class PreInPosTraversal { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static void preOrderRecur(Node head){ if(head == null){ return; } System.out .print(head.value + ""); preOrderRecur(head.left); preOrderRecur(head.right); } public static void inOrderRecur(Node head) { if(head == null){ return; } inOrderRecur(head.left); System.out .print(head.value + ""); inOrderRecur(head.right); } public static void posOrderRecur(Node head) { if(head == null){ return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out .print(head.value + ""); } public static void preOrderUnRecur(Node head){ System.out.print("pre-order: "); if(head != null){ Stack<Node> stack = new Stack<Node>(); stack.add(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(); } public static void inOrderUnRecur(Node head){ System.out.print("in-order: "); if(head != null){ Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty() || head != null){ if(head != null){ stack.push(head); head = head.left; }else { head = stack.pop(); System.out.print(head.value + " "); head = head.right; } } } System.out.println(); } public static void posOrderUnRecur1(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 posOrderUnRecur2(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(); } public static void main(String[] args) { Node head = new Node(5); head.left = new Node(3); head.right = new Node(8); head.left.left = new Node(2); head.left.right = new Node(4); head.left.left.left = new Node(1); head.right.left = new Node(7); head.right.left.left = new Node(6); head.right.right = new Node(10); head.right.right.left = new Node(9); head.right.right.right = new Node(11); // recursive System.out.println("==============recursive=============="); System.out.print("pre-order: "); preOrderRecur(head); System.out.println(); System.out.print("in-order: "); inOrderRecur(head); System.out.println(); System.out.print("pos-order: "); posOrderRecur(head); System.out.println(); // unrecursive System.out.println("============unrecursive============="); preOrderUnRecur(head); inOrderUnRecur(head); posOrderUnRecur1(head); posOrderUnRecur2(head); } } 实验效果：