一、二叉树的递归遍历
1.先序遍历
static class BitTree {
int data;
BitTree left;
BitTree right;
}
static void visit(BitTree bitTree) {
//访问节点
}
//使用递归方法遍历二叉树
static void preOrder(BitTree bitTree) {
if (bitTree != null) {
visit(bitTree);
preOrder(bitTree.left);
preOrder(bitTree.right);
}
}
2.中序遍历
static void midOrder(BitTree bitTree) {
if (bitTree != null) {
midOrder(bitTree.left);
visit(bitTree);
midOrder(bitTree.right);
}
}
3.后序遍历
static void postOrder(BitTree bitTree) {
if (bitTree != null) {
postOrder(bitTree.left);
postOrder(bitTree.right);
visit(bitTree);
}
}
二、二叉树的层次遍历
二叉树的层次遍历是指二叉树从上到下，从左到右遍历数据。同一层中的节点访问完了，接着访问下一层级的元素。先遇到的节点先访问，后遇到的节点后访问，访问顺利类似队列。所以针对每一个节点的访问顺序是
1.先访问 当前节点的数据；
2.如果当前节点有左孩子，左孩子入队；
3.如果当前节点有右孩子，右孩子入队；
static void levelOrder(BitTree bitTree){
//这里的数组长度是情况而定，写Int最大值是随意的。
BitTree[] queue = new BitTree[Integer.MAX_VALUE];
int font,rear;
if (bitTree==null)return;
font = -1;
rear=0;
//根节点入队
queue[rear] = bitTree;
while (font!=rear){
font++;
//访问出队节点
visit(queue[font]);
//出队节点的左孩子不为null就把左孩子入队
if (queue[font].left!=null){
rear++;
queue[rear] = queue[font].left;
}
//出队节点的右孩子不为null就把右孩子入队
if (queue[font].right!=null){
rear++;
queue[rear] = queue[font].right;
}
}
}
三、二叉树的非递归遍历
中序遍历的非递归算法：访问节点时先访问其左孩子，再访问该节点，最后访问右孩子。
中序遍历的时候我们先从根节点的左孩子开始，一直深入孩子节点的左孩子，直到节点的左孩子为空返回，访问该节点。
//中序遍历的非递归算法
static void nrInOrder(BitTree bitTree){
//加入100的长度够用
int maxLength =100;
BitTree[] bitTrees = new BitTree[maxLength];
BitTree p = bitTree;
int top = -1;
//根节点为null，直接return;
if (bitTree==null)return;
while (!(top==0 && p==null)){
while (p!=null){
if (top < maxLength-1)bitTrees[++top]=p;
p = p.left;
}
if (top==-1)return;
else {
p = bitTrees[top--];
visit(p);
p = p.right;
}
}
}
四、二叉树遍历算法的应用
4.1由二叉树先序和中序序列建立二叉树
假如一个二叉树的先序序列为ABCDEFG,中序序列为：CBDAEGF,恢复此二叉树；
1.首先由先序序列找出二叉树的根为A;
2.根据A在中序序列中的位置，把中序序列分为左子树(CBD)和右子树(EGF)的序列；
3.接着通过步骤2可以把先序序列也分为左子树（BCD）和右子树（EFG）;
4.依次类推，直到左右子树全部递归完成；
其递归算法如下：
static void createBitTree(int[] pre,int[] inOrd,int n,BitTree bitTree){
if (n<=0)bitTree=null;
else {
preInOrder(pre,inOrd,0,n-1,0,n-1,bitTree);
}
}
static void preInOrder(int[] preOrd, int[] inOrd, int preStart, int preEnd,
int inStart, int inEnd, BitTree bitTree){
int m = inStart;
bitTree.setData(preOrd[preStart]);
//在中序序列中找到先序序列中根元素的位置
while (preOrd[preStart] != inOrd[m])m++;
//说明左子树为null；
if (m==inStart)bitTree.setLeft(null);
else {
bitTree.setLeft(new BitTree());
preInOrder(preOrd,inOrd,preStart+1,preStart+m-inStart,inStart,m-1,bitTree.getLeft());
}
if (m==inEnd)bitTree.setRight(null);
else {
bitTree.setRight(new BitTree());
preInOrder(preOrd,inOrd,preStart+m-inStart+1,preEnd,m+1,inEnd,bitTree.getRight());
}
}
·最后说明:二叉树的后序序列和中序序列也可以唯一确定一颗二叉树，因为中序序列可以确定左右子树，后续序列可以确定二叉树；但是前序和后序序列不可以确定一颗二叉树，因为缺少中序序列无法确定左右子树；
4.2二叉树的叶子结点计算
叶子结点就是指左右子树同时为空的节点；
static int bitTreeLeaf(BitTree bitTree){
if (bitTree==null)return 0;
if (bitTree.getLeft()==null && bitTree.getRight()==null)return 1;
return bitTreeLeaf(bitTree.getLeft())+bitTreeLeaf(bitTree.getRight());
}
4.3二叉树的深度计算
对于一颗二叉树，如果只有一个节点，左右子树都为空，则深度为1；如果是个空树深度为0；对于其它情况先求出左右子树的深度depthL和depthR,整棵树的深度为1+Max(depthL,depthR);
所以整棵树的深度算法如下：
static int depthTree(BitTree bitTree){
if (bitTree==null)return 0;
if (bitTree.getLeft()==null && bitTree.getRight()==null)return 1;
int depthL = depthTree(bitTree.getLeft());
int depthR = depthTree(bitTree.getRight());
return 1+Math.max(depthL,depthR);
}
