二叉树的java实现

package other;

import java.util.Stack;

class TreeNode {
	private String key;
	private TreeNode lchild; //左孩子
	private TreeNode rchild; //右孩子
	private TreeNode parent; //双亲节点

	public TreeNode(String key) {
		this.key = key;
	}

	public String getKey() {
		return key;
	}

	public void setKey(String key) {
		this.key = key;
	}

	public TreeNode getLchild() {
		return lchild;
	}

	public void setLchild(TreeNode lchild) {
		this.lchild = lchild;
	}

	public TreeNode getRchild() {
		return rchild;
	}

	public void setRchild(TreeNode rchild) {
		this.rchild = rchild;
	}

	public TreeNode getParent() {
		return parent;
	}

	public void setParent(TreeNode parent) {
		this.parent = parent;
	}

	public String toString() { // 打印出树种某个节点的信息
		StringBuffer sb = new StringBuffer();
		sb.append("key:" + this.key + "   ");
		if (this.getLchild() != null) {
			sb.append("   left child:" + this.getLchild().getKey());
		}
		if (this.getRchild() != null) {
			sb.append("   right child:" + this.getRchild().getKey());
		}
		return sb.toString();
	}
}

public class TreeTest {

	private static Stack<TreeNode> s;
	private static TreeNode root;

	public static TreeNode createTree(){
		    root = new TreeNode("6");
			TreeNode l = new TreeNode("3");
			TreeNode r = new TreeNode("8");
			l.setParent(root);
			r.setParent(root);

			TreeNode ll = new TreeNode("2");
			TreeNode rl = new TreeNode("7");
			l.setLchild(ll);
			r.setLchild(rl);
			ll.setParent(l);
			rl.setParent(r);

			root.setLchild(l);
			root.setRchild(r);
			root.setParent(null);
			return root;
	}
	
	public static void main(String[] args) {

		// 简单的构造一个树，当然是先构造树上的每一个节点
	
		root = createTree();
		System.out.println(treeDepth(root));
//		preOrderTraverse(root); // 递归先序遍历树
//		
//		
//		//
//		TreeNode finded = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
//		System.out.println(finded);
//
//		TreeNode finded2 = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
//		System.out.println(finded2);
		
//		inOrderNonTraverse(root);
	}

	// 递归先序遍历二叉树，后序和中序相似,只是调换输出子树根节点的次序
	public static void preOrderTraverse(TreeNode t) {
		System.out.println("递归先序遍历");

		if (t != null) {
			System.out.println(t.getKey());
			preOrderTraverse(t.getLchild());
			preOrderTraverse(t.getRchild());
		}

	}

	public static void inOrderNonTraverse(TreeNode t) { // 中序遍历二叉树的非递归
														
		s = new Stack<TreeNode>();
		s.clear();

		s.push(t);// 根节点入栈
		while (!s.isEmpty()) {
			while (!s.isEmpty()&&s.peek()!= null)
				s.push(s.peek().getLchild());// 向左走到尽头
			s.pop();//空指针退栈，别忘了
			if (!s.isEmpty()) {
				TreeNode current = s.pop();
				System.out.println(current.getKey());
				s.push(current.getRchild());
			}
		}
	}

	// 二叉查找树，必须满足左子树的关键字小于等于根，右子树的节点大于等于根，这样中序遍历该树，可得到一个有序序列

	/*
	 * 在二叉查找树上找关键字为key的节点，递归方法
	 */
	public static TreeNode treeSearchTranverse(TreeNode root, String key) {
		if (root == null || root.getKey().equals(key))
			return root;
		if (root.getKey().compareTo(key) > 0) { // 小于根节点的关键字，肯定在左子树上
			return treeSearchTranverse(root.getLchild(), key);
		} else {
			return treeSearchTranverse(root.getRchild(), key);
		}
	}

	/*
	 * 在二叉查找树上找关键字为key的节点，非递归方法
	 */
	public static TreeNode treeSearchNonTranverse(TreeNode root, String key) {
		while (root != null && !root.getKey().equals(key)) {
			if (key.compareTo(root.getKey()) < 0) {
				root = root.getLchild(); // 指向左孩子
			} else {
				root = root.getRchild();
			}

		}
		return root;
	}

	/*
	 * 返回查找树中的最小关键字，只需一直沿着节点的left指针即可
	 */
	public static TreeNode TreeMin(TreeNode x) {
		while (x.getLchild() != null) {
			x = x.getLchild();
		}
		return x;
	}

	/*
	 * 返回查找树中的最大关键字，只需一直沿着节点的right指针即可
	 */
	public static TreeNode TreeMax(TreeNode x) {
		while (x.getRchild() != null) {
			x = x.getRchild();
		}
		return x;
	}

	/*
	 * 返回中序遍历查找树时节点x的后继，无需对关键字进行比较，因为二叉查找树的结构,x的后继就是具有大于x.getKey()的关键字中最小者的那个节点
	 */
	public static TreeNode TreeSuccessor(TreeNode x) {
		if (x.getRchild() != null) //根据中序遍历
			return TreeMin(x.getRchild());

		TreeNode y = x.getParent();
		while(y!=null&&x==y.getRchild()){ //x是y的右孩子或x是根节点？？？
			x=y;
			y=y.getParent();
		}
		return y;  //x是y的左孩子
	}
	
	/*
	 * 在二叉查找树中插入一个节点z，使之仍然保持查找树的特性???????????不懂，指针x跟踪路径，从根节点开始，下降，而y始终指向x的父节点。
	 */
	public static void insertNode(TreeNode z){
		TreeNode y =null;
		TreeNode x = getRoot(); //根的父节点为空
		
		while(x!=null){
			y=x;
			if(z.getKey().compareTo(x.getKey())<0) x=x.getLchild();
			else x=x.getRchild();
			
			
		}
		z.setParent(y); //插入的z节点的双亲节点
		if(y==null){
			setRoot(z);//当前树为空树，设置根节点
		}
		else if(z.getKey().compareTo(y.getKey())<0){
			y.setLchild(z);
		}
		else y.setRchild(z);
	}

	
	public static TreeNode getRoot() {
		return root;
	}

	public static void setRoot(TreeNode root) {
		TreeTest.root = root;
	}

	/*
	 * 在二叉查找树中删除一个节点z，使之仍然保持查找树的特性
	 */
	public static TreeNode deleteNode(TreeNode z){
		
		TreeNode x,y;
		if(z.getLchild()==null||z.getRchild()==null){
			y=z;
		}
		else y = TreeSuccessor(z);
		
		if(y.getLchild()!=null){
			x=y.getLchild();
		}
		else x = y.getRchild();
		
		if(x!=null){
			x.setParent(y.getParent());
		}
		
		if(y.getParent()==null){
			setRoot(x);
		}
		else if(y==y.getParent().getLchild()){
			y.getParent().setLchild(x);
		}
		else{
			y.getParent().setRchild(x);
		}
		
		if(y!=z){
			z.setKey(y.getKey());
		}
		return y;
	}
	
	public static int treeDepth(TreeNode t){ //计算树的深度
		TreeNode lchild,rchild;
		int lchildDepth,rchildDepth;
		
		if(t==null) return 0;
		else {
			System.out.println("树节点不为空时：");
			lchild = t.getLchild();
			rchild = t.getRchild();
			lchildDepth = treeDepth(lchild);
			rchildDepth = treeDepth(rchild);
			
			
			return lchildDepth>rchildDepth?(lchildDepth+1):(rchildDepth+1);
		}
	}

}