java语言实现的二叉树的各种操作（包括递归与非递归遍历二叉树求二叉树的高度，节点总数，叶子节点等）

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 < rear） {
			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