二叉树的四种遍历方式（前序遍历、中序遍历、后序遍历、测层序遍历）
二叉树的遍历遍历是数据结构中的常见的操作，把所有元素都访问一遍。线性数据结构的遍历比较简单①、正序遍历②、逆序遍历根据节点访问顺序的不同，二叉树的常见遍历方式用四种①、前序遍历（Preorder Traversal）②、中序遍历（Inorder Traversal）③、后序遍历（Postorder Traversal）④、层序遍历（Level Order Traversal）前序遍历（Preord
·
一、二叉树的遍历
-
遍历是数据结构中的常见的操作，把所有元素都访问一遍。
-
线性数据结构的遍历比较简单
①、正序遍历
②、逆序遍历 -
根据节点访问顺序的不同，二叉树的常见遍历方式用四种
①、前序遍历（Preorder Traversal）
②、中序遍历（Inorder Traversal）
③、后序遍历（Postorder Traversal）
④、层序遍历（Level Order Traversal）
（一）1、前序遍历（Preorder Traversal）
- 访问顺序：根节点、前序遍历左子树、前序遍历右子树
- 7、4、2、1、3、5、9、8、11、10、12
前序遍历的方法为：
public void preorderTraversal() {
preorderTraversal(root);
}
public void preorderTraversal(Node<E> node) {
if(node == null) return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
（一）2、前序遍历 - 非递归
利用栈实现
(1)、设置node = root
(2)、循环执行以下操作
- 如果
node != null
①.对node进行访问
②.对node.right入栈
③.设置node = node.left - 如果
node == null
①.如果栈为空,结束遍历
②.如果栈不为空,弹出栈顶元素并赋值给node
（二）1、中序遍历（Inorder Traversal）
- 访问顺序：中序遍历左子树、根节点、中序遍历右子树
- 1、2、3、4、5、7、8、9、10、11、12
/* 中序遍历 */
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if(node == null) return;
inorderTraversal(node.left);
System.out.println(node.element);
inorderTraversal(node.right);
}
- 如果是访问顺序是下面这样呢？
中序遍历右子树、根节点、中序遍历左子树
12、11、10、9、8、7、5、4、3、2、1
/* 中序遍历 */
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if(node == null) return;
inorderTraversal(node.right);
System.out.println(node.element);
inorderTraversal(node.left);
}
- 二叉搜索树的中序遍历结果是升序或者降序的
（二）2、中序遍历 - 非递归
利用栈实现
(1)、设置node = root
(2)、循环执行以下操作
- 如果
node != null
①.对node入栈
②.设置node = node.left - 如果
node == null
①、如果栈为空，结束遍历。
②、如果栈不为空，弹出栈顶元素并赋值给node - 对
node进行访问 - 设置
node = node.rigth
（三）1、后序遍历（Postorder Traversal）
- 访问顺序：后序遍历左子树、后序遍历右子树、根节点
- 1、3、2、5、4、8、10、12、11、9、7
/* 后序遍历 */
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if(node == null) return;
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.println(node.element);
}
（三）2、后序遍历 - 非递归
利用栈实现
(1)、将root入栈
(2)、循环执行以下操作，直到栈为空
- 如果栈顶节点是叶子节点 或者 上一次访问的节点是栈顶节点的子节点
①.弹出栈顶节点，进行访问 - 否则
①、将栈顶节点right、left按顺序入栈。
（四）层序遍历（Level Order Traversal）
- 访问顺序：从上到下，从左到右依次访问每一个节点
- 7、4、9、2、5、8、11、1、3、10、12
- 实现思路：使用队列
①、将根节点入队
②、循环执行以下操作，直到队列为空
Ⅰ将队头节点A出队，进行访问。
Ⅱ将A的左子节点入队。
Ⅲ将A的右子节点入队。
/* 层序遍历 */
public void levelOrderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
打印二叉树工具
- 工具：https://github.com/CoderMJLee/BinaryTrees
- 使用步骤：
①、调用BinaryTreeInfo接口
②、调用打印APIBinaryTrees.println(bst);
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import com.mj.printer.BinaryTreeInfo;
public class BinarySearchTree<E> implements BinaryTreeInfo {
private int size;
private Node<E> root;
private Comparator<E> comparator;
public BinarySearchTree() {
this(null);
}
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
/* 元素的数量 */
public int size() {
return size;
}
/* 是否为空 */
public boolean isEmpty() {
return size==0;
}
/* 清空所有的元素 */
public void clear() {
}
/* 添加元素 */
public void add(E element) {
elementNotNullCheck(element);
if(root == null) {
//添加第一个节点
root = new Node<>(element, null);
size++;
return;
}
//添加的不是第一个节点
//找到父节点
Node<E> node = root;
Node<E> parent = null;
int cmp = 0;
while (node != null) {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
}else if (cmp < 0) {
node = node.left;
}else {//相等
node.element = element;
return;
}
}
//看看插入到父节点的哪个位置
Node<E> newNode = new Node<>(element, parent);
if (cmp > 0) {
parent.right = newNode;
}else {
parent.left = newNode;
}
size++;
}
/* 删除元素 */
public void remove(E element) {
}
/* 是否包含某元素 */
public boolean contains(E element) {
return false;
}
//前序遍历
public void preorder(Visitor<E> visitor) {
if(visitor == null) return;
preorder(root,visitor);
}
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null) return;
visitor.visit(node.element);//先访问自己的元素
preorder(node.left,visitor);//前序遍历自己的左子树
preorder(node.right,visitor);//前序遍历自己的右子树
}
//中序遍历
public void inorder(Visitor<E> visitor) {
if(visitor == null) return;
inorder(root,visitor);
}
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null) return;
inorder(node.left,visitor);//中序遍历自己的左子树
visitor.visit(node.element);//先访问自己的元素
inorder(node.right,visitor);//中序遍历自己的右子树
}
//后序遍历
public void postorder(Visitor<E> visitor) {
if(visitor == null) return;
postorder(root,visitor);
}
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null) return;
postorder(node.left,visitor);//后序遍历自己的左子树
postorder(node.right,visitor);//后序遍历自己的右子树
visitor.visit(node.element);//先访问自己的元素
}
public void levelOrder(Visitor<E> visitor) {
if (root == null || visitor == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
visitor.visit(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/**
* @return 返回值等于0,代表e1和e2相等;
* 返回值大于0,代表e1大于e2;
* 返回值小于0,代表e1小于e2;
*/
@SuppressWarnings("unchecked")
public int compare(E e1,E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>)e1).compareTo(e2);
}
//由于二叉搜索树不能为空，所以要做一个检测
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null!!");
}
}
public static interface Visitor<E>{
boolean visit(E element);
}
private static class Node<E>{
E element;
Node<E> left;
Node<E> right;
@SuppressWarnings("unused")
Node<E> parent;
public Node(E element,Node<E> parent) {
this.element = element;
this.parent = parent;
}
}
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
return ((Node<E>)node).left;
}
@Override
public Object right(Object node) {
return ((Node<E>)node).right;
}
@Override
public Object string(Object node) {
Node<E> myNode = (Node<E>) node;
String parentString = "null";
if (myNode.parent != null) {
parentString = myNode.parent.element.toString();
}
return myNode.element+"_p("+parentString+")";
}
}
测试打印二叉树：
import java.util.Comparator;
import com.mj.BinarySearchTree.Visitor;
import com.mj.file.Files;
import com.mj.printer.BinaryTrees;
public class Main {
static void test9() {
Integer date[] = new Integer[] {
7,4,9,2,1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.println(bst);
System.out.print("前序遍历：");
bst.preorder(new Visitor<Integer>() {
public void visit(Integer integer) {
System.out.print(integer+" ");
}
});
System.out.println();
System.out.print("中序遍历：");
bst.inorder(new Visitor<Integer>() {
public void visit(Integer integer) {
System.out.print(integer+" ");
}
});
System.out.println();
System.out.print("后序遍历：");
bst.postorder(new Visitor<Integer>() {
public void visit(Integer integer) {
System.out.print(integer+" ");
}
});
System.out.println();
System.out.print("层序遍历：");
bst.levelOrder(new Visitor<Integer>() {
public void visit(Integer integer) {
System.out.print(integer+" ");
}
});
}
public static void main(String[] args) {
test9();
}
}
运行结果：
┌─7_p(null)─┐
│ │
┌─4_p(7) 9_p(7)
│
┌─2_p(4)
│
1_p(2)
前序遍历：7 4 2 1 9
中序遍历：1 2 4 7 9
后序遍历：1 2 4 9 7
层序遍历：7 4 9 2 1
上述的遍历只是从头遍历到尾部，一直遍历下去，无法停止【即上面有多少个元素就遍历多少次】。但是不可以随时终止这个遍历，如何实现随时终止遍历的操作呢？
//前序遍历
public void preorder(Visitor<E> visitor) {
if(visitor == null) return;
preorder(root,visitor);
}
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
visitor.stop = visitor.visit(node.element);//先访问自己的元素
preorder(node.left,visitor);//前序遍历自己的左子树
preorder(node.right,visitor);//前序遍历自己的右子树
}
//中序遍历
public void inorder(Visitor<E> visitor) {
if(visitor == null) return;
inorder(root,visitor);
}
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
inorder(node.left,visitor);//中序遍历自己的左子树
if(visitor.stop) return;
visitor.stop = visitor.visit(node.element);//先访问自己的元素
inorder(node.right,visitor);//中序遍历自己的右子树
}
//后序遍历
public void postorder(Visitor<E> visitor) {
if(visitor == null) return;
postorder(root,visitor);
}
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
postorder(node.left,visitor);//后序遍历自己的左子树
postorder(node.right,visitor);//后序遍历自己的右子树
if(visitor.stop) return;
visitor.stop = visitor.visit(node.element);//先访问自己的元素
}
//层序遍历
public void levelOrder(Visitor<E> visitor) {
if (root == null || visitor == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if(visitor.visit(node.element)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
public static abstract class Visitor<E>{
boolean stop;
/**
* @return 如果返回true，就代表停止遍历
*/
abstract boolean visit(E element);
}
import java.util.Comparator;
import com.mj.BinarySearchTree.Visitor;
import com.mj.file.Files;
import com.mj.printer.BinaryTrees;
public class Main {
static void test9() {
Integer date[] = new Integer[] {
7,4,9,2,1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.println(bst);
System.out.print("前序遍历：");
bst.preorder(new Visitor<Integer>() {
public boolean visit(Integer integer) {
System.out.print(integer+" ");
return integer == 2 ? true : false;
}
});
System.out.println();
System.out.print("中序遍历：");
bst.inorder(new Visitor<Integer>() {
public boolean visit(Integer integer) {
System.out.print(integer+" ");
return integer == 4 ? true : false;
}
});
System.out.println();
System.out.print("后序遍历：");
bst.postorder(new Visitor<Integer>() {
public boolean visit(Integer integer) {
System.out.print(integer+" ");
return integer == 4 ? true : false;
}
});
System.out.println();
System.out.print("层序遍历：");
bst.levelOrder(new Visitor<Integer>() {
public boolean visit(Integer integer) {
System.out.print(integer+" ");
return integer == 9 ? true : false;
}
});
}
public static void main(String[] args) {
test9();
}
}
┌─7_p(null)─┐
│ │
┌─4_p(7) 9_p(7)
│
┌─2_p(4)
│
1_p(2)
前序遍历：7 4 2
中序遍历：1 2 4
后序遍历：1 2 4
层序遍历：7 4 9
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)