二叉树
?二叉树本来就是递归的方式，不管是在建立还是遍历都要用到递归思想，递归的感觉就像对其中一颗二叉树的操作的重复调用，主要注意每个函数里面需要重复调用的那个操作。
package basic;
/**
* BinaryCharTree
*
* @author 9535.
*/
public class BinaryCharTree {
/**
* The value in char
*/
char value;
/**
* The leftchild
*/
BinaryCharTree leftChild;
/**
* The rightchild
*/
BinaryCharTree rightChild;
/**
*********************
* The first construct.
*
* @param paraName The value.
*********************
*/
public BinaryCharTree(char paraName) {
value = paraName;
leftChild = null;
rightChild = null;
}// Of the first construct
/**
*********************
* Manually construct a tree.Just for testing.
*
*********************
*/
public static BinaryCharTree manualBinaryCharTree() {
// Step 1. The root.
BinaryCharTree resultTree = new BinaryCharTree('a');
// Step 2. The others.
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. Linked.
resultTree.leftChild = tempTreeB;
resultTree.rightChild = tempTreeC;
tempTreeB.rightChild = tempTreeD;
tempTreeC.leftChild = tempTreeE;
tempTreeD.leftChild = tempTreeF;
tempTreeD.rightChild = tempTreeG;
// Step 4.
return resultTree;
}// Of manualBinaryCharTree
/**
*********************
* pre-order visit.
*
*********************
*/
public void preOrder() {
System.out.print(value + " ");
// 递归需要有条件语句判断，防止栈溢出错误。
if (leftChild != null) {
leftChild.preOrder();
} // Of if
if (rightChild != null) {
rightChild.preOrder();
} // Of if
}// Of preOrder
/**
*********************
* in-order visit.
*
*********************
*/
public void inOrder() {
// 递归需要有条件语句判断，防止栈溢出错误。
if (leftChild != null) {
leftChild.inOrder();
} // Of if
System.out.print(value + " ");
if (rightChild != null) {
rightChild.inOrder();
} // Of if
}// Of inOrder
/**
*********************
* post-order visit.
*
*********************
*/
public void postOrder() {
// 递归需要有条件语句判断，防止栈溢出错误。
if (leftChild != null) {
leftChild.postOrder();
} // Of if
if (rightChild != null) {
rightChild.postOrder();
} // Of if
System.out.print(value + " ");
}// Of postOrder
/**
*********************
* getDepth.From bottom to the top.
*
* @return The depth. It is 1 if there is only one node, i.e., the root.
*********************
*/
public int getDepth() {
if ((leftChild == null) && (rightChild == null)) {
return 1;
} // Of if
int resultLeft = 0;
if (leftChild != null) {
resultLeft = leftChild.getDepth();
} // Of if
int resultRight = 0;
if (rightChild != null) {
resultRight = rightChild.getDepth();
} // Of if
if (resultLeft >= resultRight) {
return resultLeft + 1;
} else {
return resultRight + 1;
}
}// Of getDepth
/**
*********************
* Get the number of nodes.
*
* @return The number of nodes.
*********************
*/
public int getNumNodes() {
if ((leftChild == null) && (rightChild == null)) {
return 1;
} // Of if
int resultLeft = 0;
if (leftChild != null) {
resultLeft = leftChild.getNumNodes();
} // Of if
int resultRight = 0;
if (rightChild != null) {
resultRight = rightChild.getNumNodes();
} // Of if
return resultLeft + resultRight + 1;
}// Of getNumNodes
/**
*********************
* The entrance of the program.
*
* @param args Not used now.
*********************
*/
public static void main(String args[]) {
BinaryCharTree tempTree = manualBinaryCharTree();
System.out.println("\r\nPreorder visit:");
tempTree.preOrder();
System.out.println("\r\nIn-order visit:");
tempTree.inOrder();
System.out.println("\r\nPost-order visit:");
tempTree.postOrder();
System.out.println("\r\n\r\nThe depth is: " + tempTree.getDepth());
System.out.println("The number of nodes is: " + tempTree.getNumNodes());
}// Of main
}// Of class CircleIntQueue
?