package?ch05;

/**
?*?
?*二叉鏈式存儲結(jié)構(gòu)下的二叉樹
?*?
?*/
import?ch03.linkQueue;
import?ch03.linkStack;

public?class?BiTree?{

	private?BiTreeNode?root;//?樹的根結(jié)點

	public?BiTree（）?{//?構(gòu)造一棵空樹
		this.root?=?null;
	}

	public?BiTree（BiTreeNode?root）?{//?構(gòu)造一棵樹
		this.root?=?root;
	}

	//?由先根遍歷的數(shù)組和中根遍歷的數(shù)組建立一棵二叉樹
	//?其中參數(shù)preOrder是整棵樹的?先根遍歷，inOrder是整棵樹的中根遍歷，preIndex是
	//?先根遍歷從preOrder字符串中的開始位置，inIndex是中根遍歷從字符串inOrder中的開始位置，count表示樹結(jié)點的個數(shù)
	public?BiTree（String?preOrder?String?inOrder?int?preIndex?int?inIndex
			int?count）?{
		if?（count?>?0）?{//?先根和中根非空
			char?r?=?preOrder.charAt（preIndex）;//?取先根字符串中的第一個元素作為根結(jié)點
			int?i?=?0;
			for?（;?i?				//?尋找根結(jié)點在中根遍歷字符串中的索引
				if?（r?==?inOrder.charAt（i?+?inIndex））
					break;

			root?=?new?BiTreeNode（r）;//?建立樹的根結(jié)點
			root.lchild=new?BiTree（preOrder?inOrder?preIndex?+?1?inIndex
					i）.root;//?建立樹的左子樹
			root.rchild=new?BiTree（preOrder?inOrder?preIndex?+?i?+?1
					inIndex?+?i?+?1?count?-?i?-?1）.root;//?建立樹的右子樹
		}
	}

	//?由標明空子樹的先根遍歷序列建立一棵二叉樹
	private?static?int?index?=?0;//?用于記錄preStr的索引值

	public?BiTree（String?preStr）?{
		char?c?=?preStr.charAt（index++）;//?取出字符串索引為index的字符，且index增1
		if?（c?!=?‘#‘）?{//?字符不為#
			root?=?new?BiTreeNode（c）;//?建立樹的根結(jié)點
			root.lchild=new?BiTree（preStr）.root;//?建立樹的左子樹
			root.rchild=new?BiTree（preStr）.root;//?建立樹的右子樹
		}?else
			root?=?null;
	}

	//?先根遍歷二叉樹基本操作的遞歸算法
	public?void?preRootTraverse（BiTreeNode?T）?{
		if?（T?!=?null）?{
			System.out.print（T.data）;?//?訪問根結(jié)點
			preRootTraverse（T.lchild）;//?訪問左子樹
			preRootTraverse（T.rchild）;//?訪問右子樹
		}
	}

	//?先根遍歷二叉樹基本操作的非遞歸算法
	public?void?preRootTraverse（）?{
		BiTreeNode?T?=?root;
		if?（T?!=?null）?{
			linkStack?S?=?new?linkStack（）;//?構(gòu)造棧
			S.push（T）;//?根結(jié)點入棧
			while?（!S.isEmpty（））?{
				T?=?（BiTreeNode）?S.pop（）;//?移除棧頂結(jié)點，并返回其值
				System.out.print（T.data）;?//?訪問結(jié)點
				while?（T?!=?null）?{
					if?（T.lchild?!=?null）?//?訪問左孩子
						System.out.print（T.lchild.data）;?//?訪問結(jié)點

					if?（T.rchild?!=?null）//?右孩子非空入棧
						S.push（T.rchild）;

					T?=?T.lchild;
				}
			}
		}
	}

	//?中根遍歷二叉樹基本操作的遞歸算法
	public?void?inRootTraverse（BiTreeNode?T）?{
		if?（T?!=?null）?{
			inRootTraverse（T.lchild）;//?訪問左子樹
			System.out.print（T.data）;?//?訪問根結(jié)點
			inRootTraverse（T.rchild）;//?訪問右子樹
		}
	}

	//?中根遍歷二叉樹基本操作的非遞歸算法
	public?void?inRootTraverse（）?{
		BiTreeNode?T?=?root;
		if?（T?!=?null）?{
			linkStack?S?=?new?Lin