目录
- 一、二叉树的三种遍历方式
- 1、先(根)序遍历（根左右）
- 2、中(根)序遍历（左根右）
- 3、后(根)序遍历（左右根）
- 二、代码实现二叉树的三种遍历方式
- 1、递归方式实现
- 2、迭代方式实现
一、二叉树的三种遍历方式
二叉树的遍历主要有三种：先(根)序遍历（根左右），中(根)序遍历（左根右），后(根)序遍历（左右根），以下图为例分别说明。
1、先(根)序遍历（根左右）
先序遍历的原则是：先根、再左、再右。 即：ABCDEFGH
2、中(根)序遍历（左根右）
中序遍历的原则是：先左、再根、再右。 即：BDCEAFHG
3、后(根)序遍历（左右根）
后序遍历的原则是：先左、再右、再根。 即：DECBHGFA
二、代码实现二叉树的三种遍历方式
/**
* 下文中用到的TreeNode类
*/
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
1、递归方式实现
/**
* 先序遍历的原则是：先根、再左、再右。
* @param root
* @param list
*/
private void preorder(TreeNode root, List<Integer> list){
if(root != null){
list.add(root.val);
preorder(root.left,list);
preorder(root.right,list);
}
}
/**
* 中序遍历的原则是：先左、再根、再右
* @param root
* @param list
*/
private void inorder(TreeNode root, List<Integer> list){
if(root != null){
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}
/**
* 后序遍历的原则是：先左、再右、再根
* @param root
* @param list
*/
private void postorder(TreeNode root, List<Integer> list){
if(root != null){
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
}
2、迭代方式实现
/**
* 先序遍历的原则是：先根、再左、再右。
* 1.辅助变量 tempNode 初始化为根节点
* 2.当 tempNode != null 时，就保存这个节点值到 list 中，然后将其入栈并置 tempNode为它自己的左子节点
* 3.当 tempNode == null 时，说明已经遍历到二叉树的左下节点了，这时前序遍历应该遍历右子树了，首先 pop 出已经遍历保存过的父节点，然后置 tempNode 为 pop 出的父节点的右子节点
* @param root
* @param list
*/
private void preorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while(!stack.isEmpty() || tempNode != null){
if (tempNode != null) {
list.add(tempNode.val);
stack.push(tempNode);
tempNode = tempNode.left;
} else {
tempNode = stack.pop();
tempNode = tempNode.right;
}
}
}
/**
* 中序遍历的原则是：先左、再根、再右
* 1.辅助变量 tempNode 初始化 root
* 3.当栈非空或 tempNode 非 null 时，循环
* 3.1 tempNode != null 时，说明还有左子节点存在，将 tempNode 入栈，并且将 tempNode 置为它自己的左子节点
* （和前序遍历的区别在于这里遍历到先不保存到 list 中，出栈的时候再将其保存到 list 中）
* 3.2 tempNode == null 时，说明到二叉树左下的节点了，这时栈顶的父节点出栈赋值给 tempNode ，并保存节点值到 list ，将 tempNode 置为栈顶节点的右子节点继续循环
* @param root
* @param list
*/
private void inorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while(!stack.isEmpty() || tempNode != null){
if (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
} else {
tempNode = stack.pop();
list.add(tempNode.val);
tempNode = tempNode.right;
}
}
}
/**
* 后序遍历的原则是：先左、再右、再根
* 1.对应前序遍历的反操作：
* 2.前序遍历从尾部添加元素，后序遍历从头部添加元素
* 3.前序遍历去左子树，后序遍历去右子树
* @param root
* @param list
*/
private void postorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while (!stack.isEmpty() || tempNode != null) {
if (tempNode != null) {
stack.push(tempNode);
list.add(0, tempNode.val);
tempNode = tempNode.right;
} else {
tempNode = stack.pop();
tempNode = tempNode.left;
}
}
}
到此这篇关于Java中二叉树的先序、中序、后序遍历以及代码实现的文章就介绍到这了,更多相关Java二叉树的先序、中序、后序遍历内容请搜索本网站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本网站！
您可能感兴趣的文章:
- Java中实现二叉树的遍历与重构
- 学习Java之二叉树的编码实现过程详解
- 关于Java的二叉树、红黑树、B+树详解
- Java实现多叉树和二叉树之间的互转
- Java Morris遍历算法及其在二叉树中的应用
- Java数据结构之树和二叉树的相关资料
- java面试题解LeetCode27二叉树的镜像实例
- Java二叉树中LCA问题解决方法两则
