/**
* 从某个节点开始先序遍历子树
* @param node
*/
public void preOrder(BinaryTreeNode node){
if (node!=null){
//遍历根节点
System.out.println(node.getData());
//遍历左子树
preOrder(node.getLeftChild());
//遍历右子树
preOrder(node.getRightChild());
}
}
/**
* 先序遍历整个二叉树
*/
public void preOrder(){
preOrder(root);
}
2.3.2、中序遍历
中序遍历(Inorder Traversal)是先遍历左子树， 再遍历根结点， 最后才遍历右子树。 即若二叉树非空， 则依次进行如下操作：
中序遍历左子树；
访问根结点；
中序遍历右子树。
图9：中序遍历二叉树示意图
/**
* 从某个节点开始中序遍历子树
* @param node
*/
public void inOrder(BinaryTreeNode node){
if (node!=null){
//中序遍历左子树
inOrder(node.getLeftChild());
//访问根节点
System.out.println(node.getData());
//中序遍历右子树
inOrder(node.getRightChild());
}
}
/**
* 中序遍历整个二叉树
*/
public void inOrder(){
inOrder(root);
}
2.3.3、后序遍历
后序遍历(Postorder Traversal)是先遍历左子树， 再遍历右子树， 最后才遍历根结点。即若二叉树非空， 则依次进行如下操作：
后序遍历左子树；
后序遍历右子树；
访问根结点。
图10：后序遍历二叉树示意图
/**
* 从某个节点开始后序遍历子树
* @param node
*/
public void postOrder(BinaryTreeNode node){
if (node!=null){
//后序遍历左子树
preOrder(node.getLeftChild());
//后序遍历右子树
preOrder(node.getRightChild());
//访问根节点
System.out.println(node.getData());
}
}
/**
* 后序遍历整个二叉树
*/
public void postOrder(){
preOrder(root);
}
由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。
2.3.4、层次遍历
层次遍历是指从二叉树的第一层(根结点)开始， 从上至下逐层遍历， 在同一层中， 则按从左到右的顺序对结点逐个访问。
图11：层次遍历二叉树示意图
由层次遍历的操作可以推知， 在进行层次遍历时， 对一层结点访问完后， 再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问， 就完成了对下一层从左到右的访问。
因此， 在进行层次遍历时， 需设置一个队列结构， 遍历从二叉树的根结点开始， 首先将根结点指针入队， 然后从队头取出一个元素， 每取出一个元素， 执行两个操作： 访问该元素所指结点； 若该元素所指结点的左、 右孩子结点非空， 则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程循环进行， 直至队列为空， 表示二叉树的层次遍历结束。
所以， 对一棵非空的二叉树进行层次遍历可按照如下步骤进行:
(1) 初始化一个队列；
(2) 二叉树的根结点放入队列；
(3) 重复步骤(4)~(7)直至队列为空；
(4) 从队列中取出一个结点 x;
(5) 访问结点x;
(6) 如果 x 存在左子结点， 将左子结点放入队列；
(7) 如果 x 存在右子结点， 将右子结点放入队列。
3、线索二叉树
在上面我们了解了二叉树的常见遍历方法，接下来看一看二叉树的线索化。
3.1、二叉树的线索化
