Java二叉树遍历 - 递归和非递归实现
package tree;
public class Test {
public static void main(String[] args) {
TreeNode tn1 = new TreeNode(1);
TreeNode tn2 = new TreeNode(2);
TreeNode tn3 = new TreeNode(3);
TreeNode tn4 = new TreeNode(4);
TreeNode tn5 = new TreeNode(5);
TreeNode tn6 = new TreeNode(6);
TreeNode tn7 = new TreeNode(7);
TreeNode tn8 = new TreeNode(8);
tn7.left = tn6;
tn7.right = tn5;
tn5.left = tn4;
tn5.right = tn3;
tn3.left = tn2;
tn3.right = tn1;
preNode(tn7);
System.out.println(" ");
midNode(tn7);
System.out.println(" ");
lastNode(tn7);
}
//前序 根左右
private static void preNode(TreeNode root) {
if (root != null) {
System.out.print(root.index + " ");
preNode(root.left);
preNode(root.right);
}
}
//中序 左根右
private static void midNode(TreeNode root) {
if (root != null) {
midNode(root.left);
System.out.print(root.index + " ");
midNode(root.right);
}
}
//后序 左右根
private static void lastNode(TreeNode root) {
if (root != null) {
lastNode(root.left);
lastNode(root.right);
System.out.print(root.index + " ");
}
}
}
package tree;
public class TreeNode {
public int index;
public TreeNode left;
public TreeNode right;
public TreeNode(int index) {
this.index = index;
}
}
//以下是非递归遍历
//非递归 前序
private static void preNotNode(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
System.out.print(node.index + " ");
stack.push(node);
node = node.left;
} else {
node = stack.pop();
node = node.right;
}
}
}
//非递归 中序
private static void midNotRecursionNode(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
System.out.print(node.index + " ");
node = node.right;
}
}
}
//后序 非递归
private static void lastNotRecursionNode(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> result = new Stack<>();
TreeNode node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
stack.push(node);
result.push(node);
node = node.right;
} else {
node = stack.pop();
node = node.left;
}
}
for (; result.size() > 0; ) {
System.out.print(result.pop().index + " ");
}
}
结果