自己用java实现二叉树的增，删，查_java 二叉树增删改查

static class Node implements Comparable{
		Node parent;//父类节点
		Node left;//左子树节点
		Node right;//右子树节点
		Comparable value;//实现了Comparable的value 
		public Node(Node parent, Comparable value, Node left, Node right){
			this.parent=parent;
			this.left=left;
			this.right=right;
			this.value=value;
		}
}

public class MyBST<C extends Comparable<?>>  {
static class Node implements Comparable,Cloneable{
		Node parent;//父类节点
		Node left;//左子树节点
		Node right;//右子树节点
		Comparable value;//实现了Comparable的value 
		public Node(Node parent, Comparable value, Node left, Node right){
			this.parent=parent;
			this.left=left;
			this.right=right;
			this.value=value;
		}
}
}

public boolean add(C c){
		if(root==null){
			root = new MyBST.Node(null,c,null,null);			
		}else{
			Node node = root;
			Node nodeParent = root;
			boolean isNodeLeft = false;
 //按大左小右,直到node为空,nodeParent 就是要插入的父节点了，
 //注意isNodeLeft来判断到底是插入nodeParent.right还是nodeParent.left
			while(node!=null){
				nodeParent = node;
				if(node.value.compareTo(c)>0){
					//should put root.left
					node=node.left;
					isNodeLeft = true;
				}else if(node.value.compareTo(c)<0){
					//should put root.right
					node=node.right;
					isNodeLeft = false;
				}else{
					System.out.println("can‘t add duplicate value");
					return false;
				}				
			}
			node = new MyBST.Node(nodeParent,c,null,null);
			if(isNodeLeft)
				nodeParent.left = node;
			else
				nodeParent.right = node;			
		}
		return true;
	}

//先序遍历递归写法   【根节点-左子树-右子树】
public void preTravel_recrusive(MyBST.Node node){
		if(node==null)
			return;
		System.out.println(node.value);
		if(node.left!=null){
			preTravel_recrusive(node.left);
		}
		if(node.right!=null){
			preTravel_recrusive(node.right);
		}
}
//先序遍历非递归写法  借助了stack这个先进后出的数据结构  
public void preTravel(){
		Stack<Node> stack = new Stack<Node>();
		if(this.root==null)
			return;
		Node current = this.root;
		//先把root压入栈顶
		stack.push(current);
		while(current!=null || !stack.isEmpty()){
			if(current!=null){
				System.out.println(current.value);
				current = current.left;
			}else{
				current = stack.pop();
				current = current.right;
			}
			if(current!=null)
				stack.push(current);
		}
	}

public void midTravel_recrusive(MyBST.Node node){
		if(node==null)
			return;
		if(node.left!=null){
			midTravel_recrusive(node.left);
		}
		System.out.println(node.value);
		if(node.right!=null){
			midTravel_recrusive(node.right);
		}
}
//中序遍历非递归写法  借助了stack这个先进后出的数据结构  
public void midTravel(){
		Stack<Node> stack = new Stack<Node>();
		Node node = this.root;
		if(node==null)
			return;
		stack.push(node);
		//如果node为空，就要去stack里判断是否为空
		while(node!=null || !stack.isEmpty()){
			if(node!=null){
				node = node.left;
			}else{
				node = stack.pop();
				System.out.println(node.value);
				node = node.right;
			}
			if(node!=null)
				stack.push(node);
		}
}

//后序遍历   【左子树-右子树-根节点】 
public void behideTravel_recrusive(MyBST.Node node){
		if(node==null)
			return;
		if(node.left!=null){
			behideTravel_recrusive(node.left);
		}
		if(node.right!=null){
			behideTravel_recrusive(node.right);
		}
		System.out.println(node.value);
}
 
//非递归后序遍历，这个发了我很长时间调试。
//主要是理解算法和原理，方向对了，剩下的就是不断的测试各种可能性
public void behideTravel(){
		if(this.root==null){
			return ;
		}
		Stack<Node> stack = new Stack<Node>();
		Node node=null,cur=this.root,pre=null;
		stack.add(cur);
		while(!stack.isEmpty()){
			node=null;
			//注意pre要！=null
			if(cur.right!=null && !(pre!=null && (cur.left==pre||cur.right==pre))){
				stack.add(cur.right);
				node = cur.right;
			}
			//注意pre要！=null
			if(cur.left!=null && !(pre!=null && (cur.left==pre||cur.right==pre))){
				stack.add(cur.left);
				node =cur.left;
			}
			if(node!=null)
				cur = node;
			else{
				pre = cur;
				cur = stack.peek();
				//注意pre要！=null
				if( (cur.right==null || cur.left==null)	|| 
					(pre!=null && (cur.left==pre||cur.right==pre))
				  ){
					System.out.println(cur.value);
					cur = stack.pop();
				}
			}
		}
}

public boolean delete(C c){
		Node deleteNode = root;
		//isLeft 删除节点是它的父类的左还是右
		boolean isLeft = false;
		while(deleteNode!=null){
			if(deleteNode.value.compareTo(c)>0){
				deleteNode = deleteNode.left;
				isLeft = true;
			}else if (deleteNode.value.compareTo(c)<0){
				deleteNode = deleteNode.right;
				isLeft = false;
			}else{
				break;
			}
		}
		if(deleteNode==null)
			return false;
		else{
			if(deleteNode.left==null && deleteNode.right==null){//删除的节点是叶子节点
				if(deleteNode.parent==null){//注意头节点
					root = null;
					return true;
				}
				if(isLeft){
					deleteNode.parent.left=null;
				}else{
					deleteNode.parent.right=null;
				}
				deleteNode.parent=null;
			}else if(deleteNode.left!=null && deleteNode.right==null){//删除的节点有left
				if(deleteNode.parent==null){//delete node is root
					root = deleteNode.left;
				}else{
					deleteNode.parent.left=deleteNode.left;
					deleteNode.left.parent=deleteNode.parent;
				}
			}else if(deleteNode.right!=null && deleteNode.left==null){//删除的节点有right
				if(deleteNode.parent==null){//delete node is root
					root = deleteNode.right;
				}else{
					deleteNode.parent.right=deleteNode.right;
					deleteNode.right.parent=deleteNode.parent;
				}
			}else{//have right and left child tree
				Node successor = deleteNode.right;
   // 从删除的节点的右子树里找到最小的值，作为删除节点的父节点的左或右子树
   //（依据于删除节点原来是父节点的左或右）
				while(successor.left!=null){
					successor=successor.left;
				}
				if(isLeft){
					 successor.parent.left = successor.right;
				}else{
					 successor.parent.right = successor.right;
				}
				if(successor.right!=null){
					successor.right.parent=successor.parent;
				}
				
				if(deleteNode.parent==null){//注意删除的节点是头节点
					root = successor;
				}else{
					if(isLeft){
						 deleteNode.parent.left=successor;
					}else{
						 deleteNode.parent.right=successor;
					}
				}
				successor.right=deleteNode.right;
				successor.left=deleteNode.left;
				successor.parent=deleteNode.parent;
			}
			deleteNode.parent=null;
			deleteNode.right=null;
			deleteNode.left=null;
			return true;
		}
	}