[数据结构与算法]排序二叉树的编码实现

类定义

public class BinarySearchTree {
	private Node tree;//树的根节点
	public static class Node{
		private int data;//具体存储的数据
		private Node left;
		private Node right;
		public Node(int data) {
			this.data=data;
		}
	}
}

插入数据 :
首先从根节点开始向下查找自己需要插入数据的具体位置。

public void insert(int data) {
		if(tree==null) {
			tree=new Node(data);
			return;
		}
		Node p=tree;
		while(p!=null) {
			if(data>p.data) {
				if(p.right==null) {
					p.right=new Node(data);
					return;
				}
				p=p.right;
			} else {
				if(p.left==null) {
					p.left=new Node(data);
					return;
				}
				p=p.left;
			}
		}
	}

删除操作:
删除操作有 3 种情况：要删除的节点无子节点、要删除的节点只有一个子节点、要删除的节点有两个子节点。

public void delete(int data){
		Node p=tree;
		Node pp=null; //pp用于指向p的父节点
		while(p!=null && p.data!=data){
		pp=p;
		if(data>p.data) p=p.right;
		else p=p.left;
		}
		if(p==null) return;
		if(p.left!=null && p.right !=null){//要删除的节点有2个子节点
		Node minp=p.right;
		Node minpp=p ;
		while(minp.left!=null){
		minpp=minp;
		minp=minp.left;
		}
		p. data=minp.data;
		p=minp;
		pp=minpp;
		}
		Node child=null;
		if(p.left!=null) child=p.left;
		if(p.right !=null) child=p.right;
		if(pp==null) tree=child;
		else if(pp.left==p) pp.left=child;
		else pp.right=child;
		}