实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式
/*
* 二叉树的遍历,二叉树每个节点在遍历的过程中访问三次,第一次访问打印为先序遍历,第二次访问打印为中序打印,第三次访问打印为后序打印。
*/
import java.util.Stack; public class 二叉树的遍历 { public static class Node{ public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } //递归先序:中左右 public static void prerec(Node head) { if(head == null) { return; } System.out.print(head.value+" "); prerec(head.left); prerec(head.right); } //递归中序:左中右 public static void inrec(Node head) { if(head == null) { return; } inrec(head.left); System.out.print(head.value+" "); inrec(head.right); } //递归后序:左右中 public static void posrec(Node head) { if(head == null) { return; } posrec(head.left); posrec(head.right); System.out.print(head.value+" "); } //非递归先序:中左右 构建一个栈,头结点压入栈,然后弹出栈,打印头结点,如果头结点有右孩子,压入栈内,如果头结点有左孩子, //压入栈内,然后执行while循环。 public static void preunrec(Node head) { if(head != null) { Stack stack = new Stack(); 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 inunrec(Node head) { if(head != null) { Stack stack = new Stack(); 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 posunrec1(Node head) { if(head != null) { Stack stack = new Stack(); Stack stack2 = new Stack(); stack.add(head); while(!stack.isEmpty()) { head = stack.pop(); stack2.push(head); if(head.left != null) { stack.push(head.left); } if(head.right != null) { stack.push(head.right); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().value + " "); } } 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); prerec(head); System.out.println(); preunrec(head); System.out.println(); inrec(head); System.out.println(); inunrec(head); System.out.println(); posrec(head); System.out.println(); posunrec1(head); } }