一:概述
二叉树的深度遍历3种方式:前序遍历、中序遍历、后序遍历。下面是具体的这三种方式的遍历代码。
二:具体概述
用递归的方式实现前序遍历、中序遍历、后序遍历。
public class TreeNodeTraveral {
/**
* 构建二叉树
*
* @param inputList 输入序列
*/
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
TreeNode node = null;
if (inputList == null || inputList.isEmpty()) {
return null;
}
Integer data = inputList.removeFirst();
// 在这里判断是否为空很关键:如果元素为空,则不再进一步递归
if (data != null) {
node = new TreeNode(data);
node.leftChild = createBinaryTree(inputList);
node.rightChild = createBinaryTree(inputList);
}
return node;
}
/**
* 二叉树前序遍历
*
* @param node 二叉树结点
*/
public static void preOrderTraveral(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
preOrderTraveral(node.leftChild);
preOrderTraveral(node.rightChild);
}
/**
* 中序遍历
*
* @param node 二叉树节点
*/
public static void inOrderTraveral(TreeNode node) {
if (node == null) {
return;
}
inOrderTraveral(node.leftChild);
System.out.println(node.data);
inOrderTraveral(node.rightChild);
}
/**
* 后序遍历
*
* @param node 二叉树节点
*/
public static void postOrderTraveral(TreeNode node) {
if (node == null) {
return;
}
postOrderTraveral(node.leftChild);
postOrderTraveral(node.rightChild);
System.out.println(node.data);
}
/**
* 二叉树节点
*/
public static class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkedList<Integer> inputList = new LinkedList<Integer>
(Arrays.asList(new Integer[]{4,5,9,null,null,8,null,null,7,null,3}));
TreeNode treeNode = createBinaryTree(inputList);
System.out.println("前序遍历:");
preOrderTraveral(treeNode);
System.out.println("中序遍历:");
inOrderTraveral(treeNode);
System.out.println("后序遍历:");
postOrderTraveral(treeNode);
}
}
二叉树用递归的方式来实现前序、中序、后序遍历,是最为自然的方式,代码也会比较简单。
这三种方式的区别,仅仅是输出的执行位置不同:前序遍历的输出在前,中序遍历
的输出在中间,后序遍历的输出在最后
代码中值得注意的是二叉树的构建。二叉树的构建方法有很多,在这里把一个线性的 链表转化成非线性的二叉树,链表节点 的顺序恰恰是二叉树前序遍历的顺序。链表中的空值,代表二叉树节点的左孩子或有孩子为空的情况。
在代码的main函数中,通过{4,5,9,null,null,8,null,null,7,null,3}这样一个线性序列,构建成的二叉树如下