package BiTree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
//二叉树数据结构
class TreeNode {
TreeNode left;
TreeNode right;
int val;
public TreeNode(int val) {
this.val = val;
}
}
public class Traverse {
public static void main(String[] args) {
//构建二叉树
TreeNode root = new TreeNode(3);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(5);
TreeNode node3 = new TreeNode(1);
TreeNode node4 = new TreeNode(6);
TreeNode node5 = new TreeNode(9);
TreeNode node6 = new TreeNode(8);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
Traverse test = new Traverse();
//前序遍历
System.out.println("前序递归(递归):");
test.preOrderRecursion(root);
System.out.println("\n前序递归(非递归):");
test.preOrder(root);
//中序遍历
System.out.println("\n中序遍历(递归):");
test.inOrderRecursion(root);
System.out.println("\n中序遍历(非递归):");
test.inOrder(root);
//后序遍历
System.out.println("\n后序遍历(递归):");
test.postOrderRecursion(root);
System.out.println("\n后序遍历(非递归)使用两个栈:");
test.postOrder(root);
System.out.println("\n后序遍历(非递归)使用一个栈:");
test.postOrderSingleStack(root);
System.out.println("\n层序遍历：");
test.levelOrder(root);
}
//前序遍历:根左右
//1.递归
public void preOrderRecursion(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrderRecursion(root.left);
preOrderRecursion(root.right);
}
}
//2.非递归
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tmp = stack.pop();
System.out.print(tmp.val + " ");
//先将右孩子压入栈，再将左孩子压入栈，就能保证弹出栈时先访问左孩子。
if (tmp.right != null) {
stack.push(tmp.right);
}
if (tmp.left != null) {
stack.push(tmp.left);
}
}
}
//中序遍历：左根右
//1.递归
public void inOrderRecursion(TreeNode root) {
if (root != null) {
inOrderRecursion(root.left);
System.out.print(root.val + " ");
inOrderRecursion(root.right);
}
}
//2.非递归
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root= stack.pop();
System.out.print(root.val + " ");
root = root.right;
}
}
}
//后序遍历
//1.递归
public void postOrderRecursion(TreeNode root) {
if (root != null) {
postOrderRecursion(root.left);
postOrderRecursion(root.right);
System.out.print(root.val + " ");
;
}
}
//2.非递归,两个栈
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
//使用两个栈
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode tmp = stack1.pop();
stack2.push(tmp);
if (tmp.left != null) {
stack1.push(tmp.left);
}
if (tmp.right != null) {
stack1.push(tmp.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}
//3.非递归，一个栈
public void postOrderSingleStack(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = root;
while (!stack.isEmpty() || root != null) {
if (root != null) {
//走到最左边
stack.push(root);
root = root.left;
} else {
root = stack.peek();
if (root.right != null && root.right != pre) { //右子树不为空且未访问
root = root.right;
stack.push(root);
root = root.left;
} else {
root = stack.pop();
System.out.print(root.val + " ");
pre = root;
root = null;
}
}
}
}
//层序遍历
public void levelOrder(TreeNode root){
if(root==null){
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode tmp = queue.poll();
System.out.print(tmp.val+" ");
if(tmp.left!=null){
queue.offer(tmp.left);
}
if(tmp.right!=null){
queue.offer(tmp.right);
}
}
}
}
运行结果：
前序递归(递归): 3 2 1 6 5 9 8 前序递归(非递归): 3 2 1 6 5 9 8 中序遍历(递归): 1 2 6 3 9 5 8 中序遍历(非递归): 1 2 6 3 9 5 8 后序遍历(递归): 1 6 2 9 8 5 3 后序遍历(非递归)使用两个栈: 1 6 2 9 8 5 3 后序遍历(非递归)使用一个栈: 1 6 2 9 8 5 3 层序遍历： 3 2 5 1 6 9 8
