[数据结构与算法]树与二叉树——二叉树的深度遍历

这一篇主要用来总结一下学习到的关于二叉树的基本知识。这一篇也要开始使用英文注释了。因为中文有可能会乱码，所以所有的注释最好都用英文吧！

首先，用Java先生成一个二叉树：节点值、左孩子、右孩子。（这里节点值用的是char类型）

public class BinaryCharTree {

	/*
	 * the value in char.
	 */
	char value;

	/*
	 * the left child.
	 */
	BinaryCharTree leftChild;

	/*
	 * the right child.
	 */
	BinaryCharTree rightChild;

	/*
	 * the first constructor.
	 */
	public BinaryCharTree(char paraName) {
		value = paraName;
		leftChild = null;
		rightChild = null;
	}

	public static BinaryCharTree manualConstructTree() {
		// Step 1.Contrast a tree with only one node.
		BinaryCharTree resultTree = new BinaryCharTree('a');

		// Step 2.Contrast 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;
	}

1、前序遍历：根 左 右

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

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

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

2、中序遍历：左 根 右

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

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

		if (rightChild != null) {
			rightChild.inOrderVisit();
		} // Of if
	}

3、后序遍历：左 右 根

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

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

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

4、树的深度：需要先判断根节点，如果一个节点没有左右子树，则为根节点，根节点的深度设定为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) {
			tempLeftDepth = rightChild.getDepth();
		} // Of if

		// The depth should increment by 1.
		if (tempLeftDepth >= tempRightDepth) {
			return tempLeftDepth + 1;
		} else {
			return tempRightDepth + 1;
		}
	}// Of getDepth

5、树的节点个数：我认为思想是与树的深度很相似的，都需要先判断根节点，接着是用递归的思想。

递归：关于树，我认为用处最大的就是递归，三种遍历用到了递归，树的深度、节点个数也需要用到递归。

public int getNumNode() {
		// 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.getNumNode();
		}

		// The number of nodes of the left child.
		int tempRightNodes = 0;
		if (rightChild != null) {
			tempRightNodes = rightChild.getNumNode();
		}

		// The total number of nodes.
		return tempLeftNodes + tempRightNodes + 1;
	}// Of getNumNodes.