Java二叉树的前中后序遍历
Java二叉树的前中后序遍历
- 1.前序遍历
- 1.1前序遍历概念
- 1.2前序遍历习题
- 2.中序遍历
- 2.1中序遍历概念
- 2.2中序遍历习题
- 3.后续遍历
- 3.1后序遍历概念
- 3.2后序遍历习题
大家好，我是晓星航。今天为大家带来的是 Java二叉树的前中后序遍历 的讲解！😀
1.前序遍历
1.1前序遍历概念
[前序遍历](前序遍历_百度百科 (baidu.com))（VLR）， [1] 是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
数学表达式形式：当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。
在后缀（postfix）表达式中，每个操作符跟在操作数之后，操作数按从左到右的顺序出现。在前缀（prefix）表达式中，操作符位于操作数之前。在前缀和后缀表达式中不会存在歧义。
因此，在前缀和后缀表达式中都不必采用括号或优先级。从左到右或从右到左扫描表达式并采用操作数栈，可以很容易确定操作数和操作符的关系。若在扫描中遇到一个操作数，把它压入堆栈，若遇到一个操作符，则将其与栈顶的操作数相匹配。把这些操作数推出栈，由操作符执行相应的计算，并将所得结果作为操作数压入堆栈。
1.2前序遍历习题
二叉树的前序遍历。 OJ链接
解法一(遍历思路：只new一个list，然后直接递归走完每一次，直接返回list)：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
解法二(子问题思路：每次都new一个新的list 再每一次递归时将他们直接存入list中)：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
list.add(root.val);
List<Integer> leftTree = preorderTraversal(root.left);
list.addAll(leftTree);
List<Integer> rightTree = preorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
}
思路：利用循环递归的方法来解决前序遍历法。
2.中序遍历
2.1中序遍历概念
[中序遍历](中序遍历_百度百科 (baidu.com))是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
数学表达式形式：当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。中缀（infix）形式即平时所书写的数学表达式形式，在这种形式中，每个二元操作符（也就是有两个操作数的操作符）出现在左操作数之后，右操作数之前。在使用中缀形式时，可能会产生一些歧义。例如，x+y ×z可以理解为(x+y) ×z或x+ (y ×z)。为了避免这种歧义，可对操作符赋于优先级并采用优先级规则来分析中缀表达式。在完全括号化的中缀表达式中，每个操作符和相应的操作数都用一对括号括起来。更甚者把操作符的每个操作数也都用一对括号括起来。如( (x) + (y) )，( (x) + ( (y) * (z) ) )和( ( (x) + (y) ) * ( (y) + (z) ) ) * (w)。
2.2中序遍历习题
二叉树中序遍历 。OJ链接
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
List<Integer> leftTree = inorderTraversal(root.left);
list.addAll(leftTree);
list.add(root.val);
List<Integer> rightTree = inorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
}
思路：子问题思路：每次都new一个新的list 再每一次递归时将他们直接存入list中，利用循环递归的方法来解决前序遍历法。
3.后续遍历
3.1后序遍历概念
后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
3.2后序遍历习题
二叉树的后序遍历 。OJ链接
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
List<Integer> leftTree = postorderTraversal(root.left);
list.addAll(leftTree);
List<Integer> rightTree = postorderTraversal(root.right);
list.addAll(rightTree);
list.add(root.val);
return list;
}
}
思路：子问题思路：每次都new一个新的list 再每一次递归时将他们直接存入list中，利用循环递归的方法来解决前序遍历法。
感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！😘