今天实现递归版本的二叉树深度遍历，并实现两个基于此遍历的方法，即求二叉树深度与二叉树结点数。
1.二叉树的深度遍历深度优先遍历，顾名思义就是一直往深处遍历，直到无路可走再回头换个方向继续往深处遍历，一直到所有结点都被遍历过为止。
在二叉树中，有前序遍历、中序遍历、后序遍历，他们都是对二叉树的深度遍历，区别在于处理结点的时机不同。前序遍历是先处理根结点，然后递归遍历左右子树，而中序遍历、后序遍历则分别是左根右和左右根的处理顺序。
1. 二叉树
二叉树中的结点包括三个元素，即结点的值，指向左子树的指针，指向右子树的指针，构造器用于生成一个树结点。
char value;
BinaryCharTree leftChild;
BinaryCharTree rightChild;
public BinaryCharTree( char paraName ) {
value = paraName;
leftChild = null;
rightChild = null;
}
2. 建立一个二叉树
建立二叉树时，先初始化树结点，再用left，right引用将各结点连起来形成一棵树就可以了。
public static BinaryCharTree manualConstructTree( ) {
// Step 1. Construct a tree with only one node.
BinaryCharTree resultTree = new BinaryCharTree('a');
// Step 2. Construct all nodes. The first node is the root.
BinaryCharTree tempTreeB = new BinaryCharTree('b');
BinaryCharTree tempTreeC = new BinaryCharTree('c');
BinaryCharTree tempTreeD = new BinaryCharTree('d');
BinaryCharTree tempTreeE = new BinaryCharTree('e');
BinaryCharTree tempTreeF = new BinaryCharTree('f');
BinaryCharTree tempTreeG = new BinaryCharTree('g');
// Step 3. Link all nodes.
resultTree.leftChild = tempTreeB;
resultTree.rightChild = tempTreeC;
tempTreeB.rightChild = tempTreeD;
tempTreeC.leftChild = tempTreeE;
tempTreeD.leftChild = tempTreeF;
tempTreeD.rightChild = tempTreeG;
return resultTree;
} // Of manualConstructTree
3. 二叉树的深度遍历
这里递归的实现二叉树的深度遍历，二叉树的定义本身就是递归的，左子树、右子树本身就是更小规模的二叉树。因此在递归遍历时主要注意递归的基准情形，显然当遍历到一个left、right引用都为空的结点时，就无需继续往下递归，而是可以返回上一层了。
- 先序遍历
处理顺序是根左右
public void preOrderVisit( ) {
System.out.print("" + value + " ");
if( leftChild != null ) {
leftChild.preOrderVisit( );
} // Of if
if( rightChild != null ) {
rightChild.preOrderVisit( );
} // Of if
} // of preOrderVisit
- 中序遍历
处理顺序是左根右
public void inOrderVisit( ) {
if( leftChild != null ) {
leftChild.inOrderVisit( );
} // Of if
System.out.print("" + value + " ");
if( rightChild != null ) {
rightChild.inOrderVisit( );
} // Of if
} // Of inOrderVisit
- 后序遍历
处理顺序是左右根
public void postOrderVisit( ) {
if( leftChild != null ) {
leftChild.postOrderVisit( );
} // Of if
if( rightChild != null ) {
rightChild.postOrderVisit( );
} // Of if
System.out.print("" + value + " ");
} // Of postOrderVisit
4. 求二叉树深度
这是对二叉树深度遍历的应用，显然二叉树的深度为左右子树中深度最大者再+1，因此我们递归的求出左右子树深度，然后以二者中的较大值+1为返回值即求出二叉树深度。对于基准情形，显然，当遍历到一个叶子结点时就无需继续往下递归，而可以返回上一层了，对于一个叶子结点子树，其返回的深度应该为1。
public int getDepth( ) {
// It is a leaf.
if( ( leftChild == null ) && ( rightChild == null ) ) {
return 1;
} // Of if
// The depth of the left child.
int tempLeftDepth = 0;
if( leftChild != null ) {
tempLeftDepth = leftChild.getDepth( );
} // Of if
// The depth of the right child.
int tempRightDepth = 0;
if (rightChild != null) {
tempRightDepth = rightChild.getDepth();
} // Of if
// The depth should increment by 1.
if (tempLeftDepth >= tempRightDepth) {
return tempLeftDepth + 1;
} else {
return tempRightDepth + 1;
} // Of if
} // Of getDepth
5. 求二叉树的结点数目
二叉树的结点数目等于左右子树结点数目之和再+1，先递归求出左右子树结点数目，以它们的结点数之和+1为返回值即求得。对于基准情形，显然仍是遍历到叶子结点时开始返回上一层，一个叶子结点子树的结点数目应该返回1。
public int getNumNodes( ) {
// It is a leaf.
if ((leftChild == null) && (rightChild == null)) {
return 1;
} // Of if
// The number of nodes of the left child.
int tempLeftNodes = 0;
if (leftChild != null) {
tempLeftNodes = leftChild.getNumNodes();
} // Of if
// The number of nodes of the right child.
int tempRightNodes = 0;
if (rightChild != null) {
tempRightNodes = rightChild.getNumNodes();
} // Of if
// The total number of nodes.
return tempLeftNodes + tempRightNodes + 1;
} // Of getNumNodes
6. 测试
public static void main(String args[]) {
BinaryCharTree tempTree = manualConstructTree();
System.out.println("rnPreorder visit:");
tempTree.preOrderVisit();
System.out.println("rnIn-order visit:");
tempTree.inOrderVisit();
System.out.println("rnPost-order visit:");
tempTree.postOrderVisit();
System.out.println("rnrnThe depth is: " + tempTree.getDepth());
System.out.println("The number of nodes is: " + tempTree.getNumNodes());
}// Of main
执行结果如下：
- 递归的好处就是程序逻辑清晰，简洁优美。
- 遍历是完成许多其他任务的基础。
- 在二叉树这种本身就是递归定义的数据结构之上使用递归，真是格外的顺畅。
