数据结构-二叉树Java实现

编程实现如下功能： 1、假设二叉树的结点值是字符，根据输入的一颗二叉树的标明了空子树的完整先根遍历序列，建立一棵以二叉链表表示的二叉树。 2、对二叉树进行先根、中根和后根遍历操作，并输出遍历序列，同时观察输出序列是否与逻辑上的序列一致。 3、统计二叉树的结点个数和叶子结点个数，并分别输出其值。

package ch05;

/**
 * 
 *二叉链式存储结构下的二叉树
 * 
 */
import ch03.linkQueue;
import ch03.linkStack;

public class BiTree {

	private BiTreeNode root;// 树的根结点

	public BiTree（） {// 构造一棵空树
		this.root = null;
	}

	public BiTree（BiTreeNode root） {// 构造一棵树
		this.root = root;
	}

	// 由先根遍历的数组和中根遍历的数组建立一棵二叉树
	// 其中参数preOrder是整棵树的 先根遍历，inOrder是整棵树的中根遍历，preIndex是
	// 先根遍历从preOrder字符串中的开始位置，inIndex是中根遍历从字符串inOrder中的开始位置，count表示树结点的个数
	public BiTree（String preOrder String inOrder int preIndex int inIndex
			int count） {
		if （count > 0） {// 先根和中根非空
			char r = preOrder.charAt（preIndex）;// 取先根字符串中的第一个元素作为根结点
			int i = 0;
			for （; i < count; i++）
				// 寻找根结点在中根遍历字符串中的索引
				if （r == inOrder.charAt（i + inIndex））
					break;

			root = new BiTreeNode（r）;// 建立树的根结点
			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）;// 建立树的根结点
			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）; // 访问根结点
			preRootTraverse（T.lchild）;// 访问左子树
			preRootTraverse（T.rchild）;// 访问右子树
		}
	}

	// 先根遍历二叉树基本操作的非递归算法
	public void preRootTraverse（） {
		BiTreeNode T = root;
		if （T != null） {
			linkStack S = new linkStack（）;// 构造栈
			S.push（T）;// 根结点入栈
			while （!S.isEmpty（）） {
				T = （BiTreeNode） S.pop（）;// 移除栈顶结点，并返回其值
				System.out.print（T.data）; // 访问结点
				while （T != null） {
					if （T.lchild != null） // 访问左孩子
						System.out.print（T.lchild.data）; // 访问结点

					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）; // 访问根结点
			inRootTraverse（T.rchild）;// 访问右子树
		}
	}

	// 中根遍历二叉树基本操作的非递归算法
	public void inRootTraverse（） {
		BiTreeNode T = root;
		if （T != null） {
			linkStack S = new Lin