package zychaowill.datastructure.tree;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;/** *  * @Description 基本二叉排序树 * @author Zychaowill * @date 2017/04/22 * @version V1.0 */public class BinNode {	// 左右孩子结点	private BinNode lchild, rchild;	// 当前结点的值（可按需更换为T）	private int value;		public BinNode() {}	// 通过左右孩子和新值构造新增结点	public BinNode(BinNode lchild, BinNode rchild, int value) {//		super();		this.lchild = lchild;		this.rchild = rchild;		this.value = value;	}		/**	 * @description 添加新节点（左孩子/右孩子），采用左孩子的值小于父节点的值，	 * 				右孩子的值大于等于父节点的值	 * @param value 新节点的值	 */	public void addChild(int value) {		if (value < this.value) { // 向左子树添加新节点			if (lchild != null) { // 若左子树不为空，则递归检测左子树				lchild.addChild(value);			} else { // 若左子树为空，则创建新节点作为父节点的左孩子				lchild = new BinNode(null, null, value);			}		} else { // 向右子树添加新节点			if (rchild != null) { // 若右子树不为空，则递归检测右子树				rchild.addChild(value);			} else { // 若右子树为空，则创建新节点作为父节点的右孩子				rchild = new BinNode(null, null, value);			}		}	}		/**	 * @description 通过递归实现的中序遍历输出树所有结点	 * @param root 二叉树的根节点或而查询树的某一个子树结点	 */	public static void printTree(BinNode root) {		if (root != null) {			printTree(root.lchild);			System.out.print(root.value);			printTree(root.rchild);		}	}		/**	 * @description 通过递归实现的先序遍历输出树的所有结点	 * @param root 二叉树的根节点或而查询树的某一个子树结点	 */	public static void preOrder(BinNode root) {		if (root != null) {			System.out.print(root.value);			preOrder(root.lchild);			preOrder(root.rchild);		}	}		/**	 * @description 基于栈实现的先序遍历输出树的所有结点	 * 				栈的特性: LIFO（后进先出）	 * @param root 二叉树的根节点或而查询树的某一个子树结点	 */	public static void preOrderStack(BinNode root) {		if (root != null) {			Stack
    
      stack = new Stack<>();			stack.push(root);						BinNode node;			while (!stack.isEmpty()) {				node = stack.pop();				System.out.print(node.value);								if (node.rchild != null) {					stack.push(node.rchild);				}				if (node.lchild != null) {					stack.push(node.lchild);				}			}		}	}		/**	 * @description 基于队列实现的先序遍历输出树的所有结点	 * 				队列的特性: FIFO（先进先出）	 * @param root 二叉树的根节点或而查询树的某一个子树结点	 */	public static void readLevel(BinNode root) {		if (root != null) {			Queue
     
       queue = new LinkedList<>();			queue.add(root);						BinNode node;			while (!queue.isEmpty()) {				node = queue.poll();				System.out.print(node.value);								if (node.lchild != null) {					queue.add(node.lchild);				}				if (node.rchild != null) {					queue.add(node.rchild);				}			}		}	}		/**	 * Start iterator level reading.	 * @description 基于队列实现的先序遍历输出树的所有结点	 * 				队列的特性: FIFO（先进先出）	 * @param root  二叉树的根节点或而查询树的某一个子树结点	 * @param level 二叉树的层次（深度）	 */	private static void levelIterator(BinNode root, int level) {		if (root == null || level < 1) {			return;		}				if (root != null) {			if (level == 1) {				System.out.print(root.value);			}						levelIterator(root.lchild, level - 1);			levelIterator(root.rchild, level - 1);		}	}		/**	 * @description 通过递归求取二叉树的层次（深度），为levelIterator(BinNode root, int level)做准备	 * @param root	 * @return	 */	public static int depth(BinNode root) {		if (root != null) {			int ldepth = depth(root.lchild);			int rdepth = depth(root.rchild);						return (ldepth > rdepth ? ldepth + 1 : rdepth + 1);		}		return 0;	}		/**	 * @description 递归实现二叉树的层次遍历的主控制器，调用depth(BinNode root)	 * 				和levelInterator(BinNode root, int level)实现	 * @param root	 */	public static void iteratorLevel(BinNode root) {		int depth = depth(root);				for (int i = 1; i <= depth; i++) {			levelIterator(root, i);		}	}	/**	 * End iterator level reading.	 */		// test	public static void main(String[] args) {		int[] values = {4, 1, 3, 2, 5, 6, 7};		BinNode root = new BinNode(null, null, values[0]);				for (int i = 1; i < values.length; i++) {			root.addChild(values[i]);		}				printTree(root);		System.out.println();		preOrder(root);		System.out.println();		preOrderStack(root);		System.out.println();				readLevel(root);		System.out.println();		iteratorLevel(root);		System.out.println();	}}