import?java.util.Stack;

public?class?BiTree?{
	private?BiTree?leftTree;//?左子樹
	private?BiTree?rightTree;//?右子樹
	private?object?data;//?節點數據

	public?final?static?int?MAX?=?40;
	BiTree[]?elements?=?new?BiTree[MAX];//?層次遍歷時保存各個節點
	int?front;//?層次遍歷時隊首
	int?rear;//?層次遍歷時隊尾

	//?構造函數
	public?BiTree（）?{
		//?TODO?Auto-generated?constructor?stub
	}

	public?BiTree（object?data）?{
		this.data?=?data;
	}

	public?BiTree（object?data?BiTree?lefTree?BiTree?righTree）?{
		this.data?=?data;
		this.leftTree?=?lefTree;
		this.rightTree?=?righTree;
	}

	//?遞歸前序遍歷二叉樹
	public?void?preOrder（BiTree?tree）?{
		if?（tree?!=?null）?{
			visit（tree.data）;
			preOrder（tree.leftTree）;
			preOrder（tree.rightTree）;

		}
	}
	//?非遞歸實現前序遍歷
	public?void?iterativePreOrder（BiTree?tree）?{
		Stack?stack?=?new?Stack（）;
		if?（tree?!=?null）?{
			stack.push（tree）;
			while?（!stack.isEmpty（））?{
				tree?=?stack.pop（）;
				visit（tree.data）;
				if?（tree.rightTree?!=?null）
					stack.push（tree.rightTree）;
				if?（tree.leftTree?!=?null）
					stack.push（tree.leftTree）;
			}
		}
	}
	//?遞歸中序遍歷二叉樹
	public?void?inOrder（BiTree?tree）?{
		if?（tree?!=?null）?{
			inOrder（tree.leftTree）;
			visit（tree.data）;
			inOrder（tree.rightTree）;
		}
	}

	//?非遞歸實現中序遍歷
	public?void?iterativeInOrder（BiTree?tree）?{
		Stack?stack?=?new?Stack（）;
		while?（tree?!=?null）?{
			while?（tree?!=?null）?{
				if?（tree.rightTree?!=?null）
					stack.push（tree.rightTree）;//?當前節點右子入棧
				stack.push（tree）;//?當前節點入棧
				tree?=?tree.leftTree;
			}
			tree?=?stack.pop（）;
			while?（!stack.empty（）?&&?tree.rightTree?==?null）?{
				visit（tree.data）;
				tree?=?stack.pop（）;
			}
			visit（tree.data）;
			if?（!stack.empty（））
				tree?=?stack.pop（）;
			else
				tree?=?null;
		}
	}

	//?遞歸后序遍歷二叉樹
	public?void?postOrder（BiTree?tree）?{
		if?（tree?!=?null）?{
			postOrder（tree.leftTree）;
			postOrder（tree.rightTree）;
			visit（tree.data）;
		}
	}

	//?非遞歸實現后序遍歷
	public?void?iterativePostOrder（BiTree?tree）?{
		BiTree?tempTree?=?tree;
		Stack?stack?=?new?Stack（）;
		while?（tree?!=?null）?{
			//?左子樹入棧
			for?（;?tree.leftTree?!=?null;?tree?=?tree.leftTree）
				stack.push（tree）;
			//?當前節點無右子或右子已經輸出
			while?（tree?!=?null
					&&?（tree.rightTree?==?null?||?tree.rightTree?==?tempTree））?{
				visit（tree.data）;
				tempTree?=?tree;//?記錄上一個已輸出節點
				if?（stack.empty（））
					return;
				tree?=?stack.pop（）;
			}
			//?處理右子
			stack.push（tree）;
			tree?=?tree.rightTree;
		}
	}

	//?層次遍歷二叉樹
	public?void?layerOrder（BiTree?tree）?{
		elements[0]?=?tree;
		front?=?0;
		rear?=?1;
		while?（front?			try?{
				if?（elements[front].data?!=?null）?{
					System.out.print（elements[front].data?+?“?“）;

					if?（elements[front].leftTree?!=?null）
						elements[rear++]?=?elements[front].leftTree;
					if?（elements[front].rightTree?!=?null）
						elements[rear++]?=?elements[front].rightTree;
					fr