作者:因情语写
链接:https://www.proprogrammar.com/article/614
声明:请尊重原作者的劳动,如需转载请注明出处
在上节的介绍中,相信大家已经熟知了树和二叉树的基本概念。
本章节,我们把重点放在介绍二叉树中几种常见的遍历方法。掌握这几种遍历方法,会加深你对树这个数据结构的理解,并为以后的学习打下扎实的基础。
本章目标:
前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。
请看下面的例子:
中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。
让我们一起来看树的中序遍历:
通常来说,对于二叉搜索树,我们可以通过中序遍历得到一个递增的有序序列。 我们将在另一张卡片(数据结构介绍 – 二叉搜索树)中再次提及。
后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。
我们一起来看后序遍历的动画演示:
值得注意的是,当你删除树中的节点时,删除过程将按照后序遍历的顺序进行。 也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。
另外,后序在数学表达中被广泛使用。 编写程序来解析后缀表示法更为容易。 这里是一个例子:
您可以使用中序遍历轻松找出原始表达式。 但是程序处理这个表达式时并不容易,因为你必须检查操作的优先级。
如果你想对这棵树进行后序遍历,使用栈来处理表达式会变得更加容易。 每遇到一个操作符,就可以从栈中弹出栈顶的两个元素,计算并将结果返回到栈中。
请练习文章后面习题中的三种遍历方法。 您可以通过递归或迭代方法实现算法,并比较它们之间的差异。
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
result.clear();
preorder(root);
return result;
}
private void preorder(TreeNode node) {
if(null != node){
result.add(node.val);
preorder(node.left);
preorder(node.right);
}
}
}
上面是递归的方法,下面看一下非递归的
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.add(node.val);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return output;
}
}
非递归栈,先进右子树,再进左子树,这样出时先出左子树,再出右子树
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
public void inorder(TreeNode node, List<Integer> result){
if(node != null){
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
}
上面是递归的方法,再看一下非递归的方法
// 用栈,非递归
// 处理树:对一个节点,如果有左孩子且没被处理过,入栈,然后处理最左没被处理的那个节点,如果此节点有右孩子,右孩子入栈
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> result = new ArrayList<>();
List<TreeNode> visited = new ArrayList<>();
TreeNode temp, left;
if(root == null){
return result;
}
stack.push(root);
while(!stack.isEmpty()){
temp = stack.peek();
while(temp.left != null && !visited.contains(temp.left)){
stack.push(temp.left);
temp = temp.left;
}
result.add(temp.val);
visited.add(temp);
stack.pop();
if(null != temp.right){
stack.push(temp.right);
}
}
return result;
}
处理结点的顺序:对一个节点,如果有左孩子且没被处理过,入栈,然后处理最左没被处理的那个节点,如果此节点有右孩子,右孩子入栈
给定一个二叉树,返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private void postorder(TreeNode node, List<Integer> result) {
if(node != null){
postorder(node.left, result);
postorder(node.right, result);
result.add(node.val);
}
}
}
上面是递归的方法,下面再看一下非递归的方法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal2(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private void postorder(TreeNode node, List<Integer> result) {
if(node != null){
postorder(node.left, result);
postorder(node.right, result);
result.add(node.val);
}
}
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> result = new ArrayList<>();
List<TreeNode> visited = new ArrayList<>();
if (root == null) {
return result;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
while (node.left != null && !visited.contains(node.left)) {
stack.push(node.left);
node = node.left;
}
if(node.right != null && !visited.contains(node.right)){
stack.push(node.right);
}else{
stack.pop();
result.add(node.val);
visited.add(node);
}
}
return result;
}
}
和先序遍历的非递归方法类似,要用到标记
层序遍历就是逐层遍历树结构。
广度优先搜索是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。 该算法从一个根节点开始,首先访问节点本身。 然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。
当我们在树中进行广度优先搜索时,我们访问的节点的顺序是按照层序遍历顺序的。
这是一个层序顺序遍历的例子:
通常,我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索。 如果您对队列不熟悉,可以在我们即将推出的另一张卡片中找到更多有关信息。
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论