一般数据结构都有遍历操作,根据需求的不同,二叉树一般有以下几种遍历方式:先序遍历、中序遍历、后序遍历和层序遍历。
(1)先序遍历
如果二叉树为空,遍历结束。否则,第一步,访问根结点;第二步,先序遍历根结点的左子树;第三步,先序遍历根结点的右子树。
(2)中序遍历
如果二叉树为空,遍历结束。否则,第一步,中序遍历根结点的左子树;第二步,访问根结点;第三步,中序遍历根结点的右子树。
(3)后序遍历
如果二叉树为空,遍历结束。否则,第一步,后序遍历根结点的左子树;第二步,后序遍历根结点的右子树;第三步,访问根结点。
(4)层次遍历
从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。
如图所示的二叉树的先序遍历产生的序列是ABDHIEJCFG,中序遍历产生的序列是HDIBJEAFCG,后序遍历产生的序列是HIDJEBFGCA,层次遍历产生的序列是ABCDEFGHIJ。
二叉树(一)
如果已知先序序列为ABDECF,中序序列为DBEAFC,如何求解后序序列呢?首先,由于先序遍历树的规则为根左右,因此可以得出先序遍历序列的第一个元素必为树的根结点,则A就为根结点。再看中序遍历为左根右,再根据根结点A,可知左子树包含元素为DBE,右子树包含元素为FC。其次,递归求解左子树(左子树的先序为BDE,中序为DBE),递归求解右子树(即右子树的先序为CF,中序为FC)。如此递归到没有左右子树为止,所以树结构如图所示。
二叉树(二)
通过上面的例子可以总结出用先序遍历和中序遍历来求解二叉树的过程,步骤如下:
1)确定树的根结点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根。
2)求解树的子树。找到根在中序遍历的位置,位置左边是二叉树的左孩子,位置右边是二叉树的右孩子,如果根结点左边或右边为空,那么该方向子树为空;如果根结点左边和右边都为空,那么根结点已经为叶子结点。
3)对二叉树的左、右孩子分别进行步骤1)、2),直到求出二叉树结构为止。具体实现代码如下:
class Node{
public int data;
public Node left;
public Node right;
public Node(){
}
public Node(int data){
this.data=data;
this.left=null;
this.right=null;
}
}
public class BinaryTree{
private Node root;
public BinaryTree(){
root=null;
}
//后序遍历方法递归实现
public void postOrder(Node localRoot){
if(localRoot !=null){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data+"");
}
}
public void postOrder(){
this.postOrder(this.root);
}
public void initTree(int[]preOrder, int[]inOrder){
this.root=this.initTree(preOrder, 0, preOrder.length-1, inOrder, 0,
inOrder.length-1);
}
public Node initTree(int[]preOrder, int start1, int end1, int[]inOrder,
int start2, int end2){
if(start1>end1 || start2>end2){
return null;
}
int rootData=preOrder[start1];
Node head=new Node(rootData);
//找到根结点所在的位置
int rootIndex=findIndexInArray(inOrder, rootData, start2, end2);
int offSet=rootIndex-start2-1;
//构建左子树
Node left=initTree(preOrder, start1+1, start1+1+offSet,
inOrder, start2, start2+offset);
//构建右子树
Node fight=initTree(preOrder, start1+offSet+2, end1, inOrder,
rootIndex+1, end2);
head.left=left;
head.right=right;
return head;
}
public int findIndexInArray(int[]a, int x, int begin, int end){
for(int i=begin; i<=end; i++){
if(a[i]==x)
return i;
}
return-1;
}
public static void main(String[]args){
BinaryTree biTree=new BinaryTree();
int[]preOrder={1, 2, 4, 8, 9, 5, 10, 3, 6, 7};
int[]inOrder={8, 4, 9, 2, 10, 5, 1, 6, 3, 7};
biTree.initTree(preOrder, inOrder);
System.out.print("二叉树的后序遍历:");
biTree.postOrder();
}
}
程序运行结果为:
二叉树的后序遍历:8 9 4 10 5 2 6 7 3 1