java代码实现数组[3,1,2,5,4]用中的栈进行前中后序遍历
时间: 2023-10-16 09:48:01 浏览: 35
下面是使用Java代码实现数组 [3, 1, 2, 5, 4] 的前序遍历、中序遍历和后序遍历的过程:
```java
import java.util.Stack;
public class Main {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
// 前序遍历
public static void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
// 中序遍历
public static void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
System.out.print(node.val + " ");
cur = node.right;
}
}
// 后序遍历
public static void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode lastVisited = null;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.peek();
if (node.right != null && node.right != lastVisited) {
cur = node.right;
} else {
stack.pop();
System.out.print(node.val + " ");
lastVisited = node;
}
}
}
public static void main(String[] args) {
// 构建二叉树
TreeNode root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(4);
System.out.print("前序遍历结果:");
preOrderTraversal(root);
System.out.println();
System.out.print("中序遍历结果:");
inOrderTraversal(root);
System.out.println();
System.out.print("后序遍历结果:");
postOrderTraversal(root);
System.out.println();
}
}
```
通过运行以上代码,你可以得到数组 [3, 1, 2, 5, 4] 的前序遍历、中序遍历和后序遍历的结果。