二叉树（Java实现）

public class BinaryTree {

	private Node root;
	
	public Node find(int key){
		Node current = root;
		while(null != current){
			if(current.id == key){
				return current;
			}else if(key > current.id){
				current = current.right;
			}else{
				current = current.left;
			}
		}
		return null;
	}
	
	public void insert(int id,String v){
		// 1.创建节点
		Node node = new Node();
		node.id = id;
		node.value = v;
		
		// 2.根节点为null时，将当前直接置为根节点
		if(null == root){
			root = node;
		
		// 3.遍历节点
		}else{
			Node parent = root;
			Node current = root;
			while(null != current){
				parent = current;
				if(id < current.id){//left
					current = current.left;
					if(null == current){
						parent.left = node;
						return;
					}
				}else {//right
					current = current.right;
					if(null == current){
						parent.right = node;
						return;
					}
				}
			}
		}
	}
	
	public boolean delete(int key){
		// 1.查找被删除节点
		Node parent = root;
		Node current = root;
		boolean isLeftChild = false;
		while(current.id != key){
			parent = current;
			if(key > current.id){
				current = current.right;
				isLeftChild = false;
			}else{
				current = current.left;
				isLeftChild = true;
			}
			
			if(null == current){
				return false;
			}
		}

		// 2.1被删除节点没有子节点
		if(null == current.left && null == current.right){
			if(current == root){
				root = null;
			}else{
				if(isLeftChild){
					parent.left = null;
				}else{
					parent.right = null;
				}
			}
		}
		
		// 2.2被删除节点有一个子节点
		else if(null == current.left){
			if(current == root){
				root = current.right;
			}else if(isLeftChild){
				parent.left = current.right;
			}else{
				parent.right = current.right;
			}
		}
		
		else if (null == current.right){
			if(current == root){
				root = current.left;
			}else if(isLeftChild){
				parent.left = current.left;
			}else {
				parent.right = current.left;
			}
		}
		
		// 2.3被删除节点有两个子节点
		else{
			Node succeedNode = getSucceedNode(current);//后继节点
			if(current == root){
				root = succeedNode;
			}else if(isLeftChild){
				parent.left = succeedNode;
			}else{
				parent.right = succeedNode;
			}
			
			succeedNode.left = current.left;
		}
		return true;
	}
	
	// 获取被删除节点的后继节点（专为被删除节点有两个子节点使用）
	private Node getSucceedNode(Node delNode){
		Node parent = delNode;
		Node succeed = delNode;
		Node current = delNode.right;//从右节点开始
		
		//获取左子节点，一直到最后一个左子孙节点，就是比删除节点的次大节点
		while(null != current){
			parent = succeed;
			succeed = current;
			current = current.left;
		}
		
		if(succeed != delNode.right){
			parent.left = succeed.right;//后继节点要被替换到delNode的位置，所以需要把后继节点的右节点替换给parent的左节点
			succeed.right = delNode.right;//后继节点的现右子节点就是delNode的右子节点
		}
		
		return succeed;
	}
	
	//前序遍历
	public String perOrder(Node node){
		StringBuilder sb = new StringBuilder();
		if(null != node){
			sb.append(node.id).append(" ");
			sb.append(perOrder(node.left)).append(" ");
			sb.append(perOrder(node.right)).append(" ");
		}
		return sb.toString();
	}
	//中序遍历
	public String inOrder(Node node){
		StringBuilder sb = new StringBuilder();
		if(null != node){
			sb.append(inOrder(node.left)).append(" ");
			sb.append(node.id).append(" ");
			sb.append(inOrder(node.right)).append(" ");
		}
		return sb.toString();
	}
	//后序遍历
	public String postOrder(Node node){
		StringBuilder sb = new StringBuilder();
		if(null != node){
			sb.append(postOrder(node.left)).append(" ");
			sb.append(postOrder(node.right)).append(" ");
			sb.append(node.id).append(" ");
		}
		return sb.toString();
	}
	
	//节点类
	class Node{
		public int id;//节点key
		public String value;//节点值
		public Node left;
		public Node right;
		
		@Override
		public String toString() {
			return "id:"+id+",value:"+value;
		}
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}
}