《第十四天》

v树是 n个结点的有限集 T，在非空树中：v有且仅有一个特定的结点，称为树的根

vn>1时，其余结点可分为 m个互不相交的有限集 ，其中每一个集合本身又是一棵树，称为根的子树

import java.util.Arrays;

public class BinaryCharTree {

	char value;
	BinaryCharTree leftChild;

	BinaryCharTree rightChild;

	public BinaryCharTree(char paraName) {
		value = paraName;
		leftChild = null;
		rightChild = null;
	}

	public static BinaryCharTree manualConstructTree() {

		BinaryCharTree resultTree = new BinaryCharTree('a');

		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;
	}

	public void preOrderVisit() {
		System.out.print("" + value + " ");

		if (leftChild != null) {
			leftChild.preOrderVisit();
		}

		if (rightChild != null) {
			rightChild.preOrderVisit();
		}
	}

	public void inOrderVisit() {
		if (leftChild != null) {
			leftChild.inOrderVisit();
		} // Of if

		System.out.print("" + value + " ");

		if (rightChild != null) {
			rightChild.inOrderVisit();
		} 
	}
	public void postOrderVisit() {
		if (leftChild != null) {
			leftChild.postOrderVisit();
		}

		if (rightChild != null) {
			rightChild.postOrderVisit();
		}

		System.out.print("" + value + " ");
	}

	
	public int getDepth() {
		
		if ((leftChild == null) && (rightChild == null)) {
			return 1;
		} 
		int tempLeftDepth = 0;
		if (leftChild != null) {
			tempLeftDepth = leftChild.getDepth();
		}
		int tempRightDepth = 0;
		if (rightChild != null) {
			tempRightDepth = rightChild.getDepth();
		}
		if (tempLeftDepth >= tempRightDepth) {
			return tempLeftDepth + 1;
		} else {
			return tempRightDepth + 1;
		}
	}

	public int getNumNodes() {

		if ((leftChild == null) && (rightChild == null)) {
			return 1;
		}
		int tempLeftNodes = 0;
		if (leftChild != null) {
			tempLeftNodes = leftChild.getNumNodes();
		}
		int tempRightNodes = 0;
		if (rightChild != null) {
			tempRightNodes = rightChild.getNumNodes();
		}
		return tempLeftNodes + tempRightNodes + 1;
	}

	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());
	}

}