admin管理员组

文章数量:1794759

树的遍历

树的遍历

树作为一种高效的查找数据结构，被广泛应用在各种查询场景。在需要对树进行遍历时，主要有四种方式：前序遍历、中序遍历、后序遍历以及层次遍历。接下来我们针对下图中的树进行四种遍历的总结及实现。
遍历一棵树，无非就是遍历这个树的所有结点。因为树中每个结点的左孩子和右孩子也都是树，因此我们在遍历树的时候，只需记录当前结点的值，然后针对左子树和右子树进行递归遍历，就可以遍历整棵树了。在遍历过程中，针对特定结点，需要遍历的地方有三个：当前结点，左子树，右子树。我们默认按照先左后右的顺序来处理两个子树。

一、前序遍历

前序遍历中的前，代表当前结点需要在最前面进行遍历。遍历子树时，我们之前提到默认情况下是先遍历左子树，再遍历右子树，遍历规则保持不变。因此前序遍历的遍历顺序就为：当前结点->左子树的前序遍历->右子树的前序遍历。因此这棵树的前序遍历就是：5->3->1->2->4->6。
我们一个部分一个部分的分析。首先对于根结点，先遍历它的本身5，然后去遍历左子树，3->1->2->4就是它左子树的前序遍历，然后遍历右子树为6。组合在一起就是该树的前序遍历了。针对前序遍历，共有两种实现方式：递归实现与非递归实现。下面给出java代码的实现。

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(int val){this.val = val;}
}
/* 递归实现 */
public List<Integer> preOrder(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;res.add(root.val);res.addAll(preOrder(root.left));res.addAll(preOrder(root.right));return res;
}
/* 非递归实现 */
public List<Integer> preOrder(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode temp = stack.pop();res.add(temp.val);//这里要先将右子树压入栈，因为栈是先进先出，确保左子树在右子树之前出栈if(temp.right != null) stack.push(temp.right);if(temp.left != null) stack.push(temp.left);}return res;
}

二、中序遍历

中序遍历的中是指在遍历时，将当前结点放在中间遍历，其遍历顺序为：中序遍历左子树->当前结点->中序遍历右子树。对于这棵树进行中序遍历的结果为：1->2->3->4->5->6。从根节点的角度来看， 1->2->3->4是其左子树的中序遍历，6是其右子树的中序遍历。可以发现，对于二叉查找树，其中序遍历的结果是有序的。这也是中序遍历的一个性质。接下来给出java代码实现。

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(int val){this.val = val;}
}
/* 递归实现 */
public List<Integer> midOrder(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;res.addAll(midOrder(root.left));res.add(root.val);res.addAll(midOrder(root.right));return res;
}/* 非递归实现 */
public List<Integer> midOrder(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur!=null || !stack.isEmpty()){// 先遍历左子树（找到最左子结点）while(cur!=null){stack.push(cur);cur = cur.left;}// 遍历当前结点（最左子结点）TreeNode temp = stack.pop();res.add(temp.val);// 中序遍历右子树cur = temp.right;}return res;
}

三、后序遍历

后序遍历中的后，指当前结点在最后遍历。遍历顺序为：后序遍历左子树->后序遍历右子树->当前结点。这棵树的后序遍历就为：2->1->4->3->6->5。从根节点的角度来看，2->1->4->3为其左子树的后序遍历，6为其右子树的后序遍历。下面给出java代码实现。

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(int val){this.val = val;}
}
/* 递归实现 */
public List<Integer> postOrder(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;res.addAll(preOrder(root.left));res.addAll(preOrder(root.right));res.add(root.val);return res;
}
/* 非递归实现 */
//这里利用前序遍历的思想，前序遍历的遍历顺序为中->左->右
//而后序遍历的顺序为左->右->中，将前序遍历中的压栈顺序交换一下
//先压左子树，再压右子树，则顺序变为中->右->左，正好与后序遍历相反
//因此先进行左右子树交换的前序遍历，然后将结果反转
public List<Integer> postOrder(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode temp = stack.pop();res.add(temp.val);//这里交换压栈顺序，先压左if(temp.left != null) stack.push(temp.left);if(temp.right != null) stack.push(temp.right);}Collections.reverse(res);return res;
}

四、层次遍历

层次遍历指从根结点开始一层一层的遍历，其实现本质上就是图的bfs遍历，因为树也是图的一种。从根节点开始，进行bfs。对于该树来说，层次遍历的结果为：5->3->6->1->4->2。下面给出java代码实现。

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(int val){this.val = val;}
}public List<Integer> bfs(TreeNode root){List<Integer> res = new ArrayList<>();if(root == null) return res;// BFS时需要使用队列存储遍历顺序Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){//通过记录每一层的size可以确保每一次遍历queue时遍历的是同一层次从元素，在有些时候很有用int size = queue.size();for(int i = 0; i < size; i++){TreeNode temp = queue.poll();res.add(temp.val);if(temp.left != null) queue.offer(temp.left);if(temp.right != null) queue.offer(temp.right);}}return res;
}

以上就是四种树的遍历方式以及实现的总结，如果有什么问题，还请各位多多指正。

本文标签： 树的遍历