二叉树前序中序后序详细设计
时间: 2023-11-11 07:03:03 浏览: 43
二叉树的前序、中序、后序遍历是指按照某种顺序遍历二叉树的所有节点。其中,前序遍历是先遍历根节点,再遍历左子树,最后遍历右子树;中序遍历是先遍历左子树,再遍历根节点,最后遍历右子树;后序遍历是先遍历左子树,再遍历右子树,最后遍历根节点。这三种遍历方式都可以使用递归或非递归的方式实现。
具体实现方法如下:
1. 前序遍历
递归实现:
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
非递归实现:
public void preOrder(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);
}
}
}
2. 中序遍历
递归实现:
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
非递归实现:
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
System.out.print(node.val + " ");
node = node.right;
}
}
3. 后序遍历
递归实现:
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
非递归实现:
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
Stack<Integer> output = new Stack<>();
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
output.push(node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
while (!output.isEmpty()) {
System.out.print(output.pop() + " ");
}
}