二叉树的四种遍历方式
以下面这张图建立一个二叉树，实现二叉树的四种遍历方式：先序遍历，中序遍历，后序遍历，层级遍历；前面三种方式都是使用递归来实现，如果递归不理解，那么前面三种实现起来绝对是很吃力的，最后一种方式是使用队列的方式来遍历，队列的先进先出特性完全可以用来实现层级遍历。
四种遍历方式的源码：
// 先序遍历
public void preOrderTraverse() {
System.out.println("先序遍历");
this.preOrderTraverse(root);
System.out.println();
}
// 先序遍历
private void preOrderTraverse(Node root) {
if (root != null) {// 1 4 5 2 3 6 7
// 遍历根
System.out.print(root.value + " ");
// 遍历左子树
preOrderTraverse(root.leftChild);
// 遍历右子树
preOrderTraverse(root.rightChild);
}
}
// 中序遍历
public void inOrderTraverse() {
System.out.println("中序遍历");
this.inOrderTraverse(root);
System.out.println();
}
// 中序遍历
private void inOrderTraverse(Node root) {
if (root != null) {// 4 5 1 3 2 6 7
// 遍历左子树
inOrderTraverse(root.leftChild);
// 输出根
System.out.print(root.value + " ");
// 遍历右子树
inOrderTraverse(root.rightChild);
}
}
// 后序遍历
public void postOrderTraverse() {
System.out.println("后序遍历");
this.postOrderTraverse(root);
System.out.println();
}
// 后序遍历
public void postOrderTraverse(Node root) {
if (root != null) {// 5 4 3 7 6 2 1
// 遍历左
postOrderTraverse(root.leftChild);
// 遍历右
postOrderTraverse(root.rightChild);
// 输出根
System.out.print(root.value + " ");
}
}
public void levelOrderByStack() {
System.out.println("按照层次遍历二叉树");
if(root == null) return;
Queue<Node> queue = new LinkedList<Node>() ;
queue.add(root);
while(queue.size() != 0)
{
int len = queue.size();
for(int i=0;i <len; i++)
{
Node temp = queue.poll();
System.out.print(temp.value+" ");
if(temp.leftChild != null) queue.add(temp.leftChild);
if(temp.rightChild != null) queue.add(temp.rightChild);
}
}
System.out.println();
}
public static void main(String[] args) {
// 创建一个二叉树
Node node5 = new Node(5, null, null);
Node node4 = new Node(4, null, node5);
Node node3 = new Node(3, null, null);
Node node7 = new Node(7, null, null);
Node node6 = new Node(6, null, node7);
Node node2 = new Node(2, node3, node6);
Node node1 = new Node(1, node4, node2);
BinaryTree btree = new Test2(node1);
// 先序
btree.preOrderTraverse();
// 中序
btree.inOrderTraverse();
// 后序
btree.postOrderTraverse();
System.out.println();
btree.levelOrderByStack();;
}
结果图：