目录
1.递归序实现
2.非递归实现
二叉树的节点结构
java">public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}
}1.递归序实现
递归的方法遍历二叉树时每一个节点都会被访问三次
java">public static void f(Node head) {//第1次访问当前节点if (head == null) {return;}//第1次访问结束f(head.left);//第2次访问当前节点//第2次访问结束f(head.right);//第3次访问当前节点//第3次访问结束
}
java">递归序
1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1在递归序的基础上衍生出了三种顺序的遍历，先序中序后序
先序：先打印头节点，再打印左子树上所有的节点，最后打印右子树上所有的节点。可以利用递归序，仅当第一次来到一个节点时才打印
java">public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur(head.left);preOrderRecur(head.right);
}java">先序(根左右)
1,2,4,5,3,6,7中序：先打印左子树上所有的节点，再打印头节点，最后打印右子树上所有的节点。可以利用递归序，仅当第二次来到一个节点时才打印
java">public static void inOrderRecur(Node head) {if (head == null) {return;}inOrderRecur(head.left);System.out.print(head.value + " ");inOrderRecur(head.right);
}java">//中序(左根右)
4,2,5,1,6,3,7后序：先打印左子树上所有的节点，再打印右子树上所有的节点，最后打印头节点。可以利用递归序，仅当第三次来到一个节点时才打印
java">public static void posOrderRecur(Node head) {if (head == null) {return;}posOrderRecur(head.left);posOrderRecur(head.right);System.out.print(head.value + " ");
}java">//后序(左右根)
4,5,2,6,7,3,12.非递归实现
准备一个栈
-
先序遍历
首先根节点入栈
(1) 每次从栈中弹出一个节点cur
(2) 处理（打印）cur
(3) 如果可以，先把右孩子压入栈，再把左孩子压入栈
(4) 重复这个过程
java">public static void preOrderRecur(Node head) {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();
}-
后序遍历
我们在先序遍历中做以下改动
额外准备一个收集栈（总共有两个栈）
首先根节点入栈
(1) 每次从栈中弹出一个节点cur
(2) 把cur放入收集栈中
(3) 如果可以，先把左孩子压入栈中，再把右孩子压入栈中
(4) 重复这个过程
(5) 弹出收集栈中的所有元素并打印
java">public static void posOrderUnRecur1(Node head) {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();
}-
中序遍历
先把整棵树的左边界全部压入栈，左边界指从当前根节点开始一直.left直至null
在依次弹出并打印节点的过程中对当前节点的右子树重复这个操作，
java">public static void inOrderUnRecur(Node head) {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();
}
