二叉树的先序、中序、后序遍历(递归 and 非递归)
程序员文章站
2022-05-06 21:26:25
...
二叉树的先序、中序、后序遍历(递归 and 非递归)
递归好写,非递归需要用栈就难写了。。
package lianjia;
import java.util.*;
public class Main{
// 先序遍历(递归)
public static void preOrder(TreeNode root) {
if(root != null) {
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// 中序遍历(递归)
public static void inOrder(TreeNode root) {
if(root != null) {
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
// 后序遍历(递归)
public static void postOrder(TreeNode root) {
if(root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
}
// 先序遍历(非递归)
public static void preOrder2(TreeNode root) {
Stack<TreeNode> stack = new Stack();
while(root != null || !stack.isEmpty()) {
while(root != null) {
System.out.print(root.val + " ");
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
}
// 中序遍历 (非递归)
public static void inOrder2(TreeNode root) {
Stack<TreeNode> stack = new Stack();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
System.out.print(root.val + " ");
root = root.right;
}
}
// 后序遍历 (非递归)
public static void postOrder2(TreeNode root) {
Stack<TreeNode> stack = new Stack();
TreeNode preNode = null;
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.peek();
// 如果右子树为空,或者右孩子访问过了,那么说明左右孩子都访问过了,当前父节点出栈
if(root.right == null || root.right == preNode) {
System.out.print(root.val + " ");
preNode = stack.pop();
root = null;
}else {
root = root.right;
}
}
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node5.left = node6;
preOrder(node1); // 先序遍历(递归)
System.out.println("先序遍历(递归)");
preOrder2(node1);// 先序遍历(非递归)
System.out.println("先序遍历(非递归)");
inOrder(node1); // 中序遍历(递归)
System.out.println("中序遍历(递归)");
inOrder2(node1); // 中序遍历(非递归)
System.out.println("中序遍历(非递归)");
postOrder(node1); // 后序遍历(递归)
System.out.println("后序遍历(递归)");
postOrder2(node1);// 后序遍历(非递归)
System.out.println("后序遍历(非递归)");
}
}
测试样例如下:
注:学渣心里苦,不要学楼主,平时不努力,考试二百五,哭 ~