《算法导论》第12章二叉搜索树Java实现

1.二叉树中的结点类Node,保存了树中一个结点的值，和它的父亲结点，左孩子结点与右孩子结点

//二叉树中的结点类,保存了树中一个结点的值，和它的父亲结点，左孩子结点与右孩子结点
public class Node {
	int key;//结点的值
	Node p;//父亲结点
	Node left;//左孩子结点
	Node right;//右孩子结点
	
	//添加一个构造方法，方便封装数值
	public Node(int key) {
		this.key=key;
	}
}

2.二叉搜索树类Binary_Search_Tree，按次序实现了书中正文的方法：

INORDER-TREE-WALK：中序遍历树的方法
PREDECESSOR-TREE-WALK：前序遍历树的方法
TREE-SEARCH：查询二叉树的某个结点递归版
ITERATIVE-TREE-SEARCH：查询二叉树的某个结点迭代版
TREE-MINIMUM：返回树中最小值结点
TREE-MAXIMUM：返回树中的最大值结点
TREE-SUCCESSOR：寻找某个结点在中序遍历序列的后继
TREE-PREDECESSOR：寻找某个结点在中序遍历序列的前驱
TREE-INSERT：树中插入某个结点
TRANSPLANT：搜索二叉树的更换结点操作，将树中以u为根结点的子树更换为新结点以v为根的子树
TREE-DELETE：删除树中某个结点

//搜索二叉树类
public class Binary_Search_Tree {
	private Node root;//树的根节点
	
	public Binary_Search_Tree() {
		this.root =null;
	}

	//中序遍历整个二叉树
	public void Inorder_Tree_Walk() {
		this.Inorder_Tree_Walk(this.root);
		System.out.println();
	}
	//中序遍历二叉树的某个结点
	private void Inorder_Tree_Walk(Node x) {
		if(x!=null) {
			Inorder_Tree_Walk(x.left);
			System.out.print(x.key+" ");
			Inorder_Tree_Walk(x.right);
		}
	}
	
	//前序遍历整个二叉树
	public void Preorder_Tree_Walk() {
		this.Preorder_Tree_Walk(this.root);
		System.out.println();
	}
	//前序遍历二叉树的某个结点
	private void Preorder_Tree_Walk(Node x) {
		if(x!=null) {
			System.out.print(x.key+" ");
			Preorder_Tree_Walk(x.left);
			Preorder_Tree_Walk(x.right);
		}
	}
	
	//在二叉树中查询某个值，返回包含该值的Node结点,递归版本
	public Node Tree_Search(int k) {
		return Tree_Search(root, k);//传入root结点，从root结点往下搜索
	}
	//二叉树从某个结点x向下搜索k值的方法，返回包含k值的结点，递归版本
	private Node Tree_Search(Node x,int k) {
		if(x==null||k==x.key) {
			return x;
		}
		if(k<x.key) {
			return Tree_Search(x.left, k);
		}else {
			return Tree_Search(x.right, k);
		}
	}

	//在二叉树中查询某个值，返回包含该值的Node结点,递归版本
	public Node Iterative_Tree_Search(int k) {
		return Iterative_Tree_Search(root, k);
	}
	//二叉树从某个结点x向下搜索k值的方法，返回包含k值的结点，递归版本
	private Node Iterative_Tree_Search(Node x,int k) {
		while(x!=null&&k!=x.key) {
			if(k<x.key) {
				x=x.left;
			}else {
				x=x.right;
			}
		}
		return x;
	}
	
	//搜索二叉树中最小的值，传入root根节点
	public Node Tree_MiniMum() {
		return Tree_MiniMum(root);
	}
	//从某个结点x像下搜索最小的值，返回包含该值的结点
	private Node Tree_MiniMum(Node x) {
		while(x.left!=null) {
			x=x.left;
		}
		return x;
	}
	
	//搜索二叉树中最小大的值，传入root根节点
	public Node Tree_MaxiMum() {
		return Tree_MaxiMum(root);
	}
	//从某个结点x像下搜索最小的值，返回包含该值的结点
	private Node Tree_MaxiMum(Node x) {
		while(x.right!=null) {
			x=x.right;
		}
		return x;
	}
	
	//寻找某个结点x的后继
	public Node Tree_Successor(Node x) {
		if(x.right!=null) {
			return Tree_MiniMum(x.right);
		}
		Node y = x.p;
		while(y!=null&&x==y.right) {
			x=y;
			y=y.p;
		}
		return y;
	}
	
	//寻找某个结点x的前驱,与寻找它的后继Tree_Successor相互对称
	public Node Tree_Predecessor(Node x) {
		if(x.left!=null) {
			return Tree_MaxiMum(x.left);
		}
		Node y = x.p;
		while(y!=null && x==y.left) {
			x=y;
			y=y.p;
		}
		return y;
	}
	
	//搜索二叉树的插入操作，将值为k的结点z插入到搜索二叉树中
	public void Tree_insert(Binary_Search_Tree T,Node z) {
		Node y = null;//搜索指针
		Node x = T.root;//表示树中结点的指针，初始为root
		while(x!=null) {
			y=x;
			if(z.key<x.key) {
				x=x.left;
			}else {
				x=x.right;
			}
		}//循环终止时，x指向一个空的位置，也就是z要插入的位置，而y保留为该位置的父结点
		z.p=y;
		if(y==null) {
			T.root=z;
		}else if(z.key<y.key) {
			y.left=z;
		}else {
			y.right=z;
		}
	}
	
	//搜索二叉树的更换结点操作，将树中以u为根结点的子树更换为新结点以v为根的子树
	public void Transplant(Binary_Search_Tree T,Node u,Node v) {
		if(u.p==null) {
			T.root = v;
		}else if(u==u.p.left) {
			u.p.left=v;
		}else {
			u.p.right=v;
		}
		if(v!=null) {
			v.p=u.p;
		}
	}
	
	//搜索二叉树的删除操作，将树中结点z删除
	public void Tree_Delete(Binary_Search_Tree T,Node z) {
		if(z.left == null) {//第1种情况
			Transplant(T, z, z.right);
		}else if(z.right==null) {//第2种情况
			Transplant(T, z, z.left);
		}else { 
			Node y=Tree_MiniMum(z.right);//直接找到结点z的后继结点y
			if(y.p!=z) {//第4种情况
				Transplant(T, y, y.right);
				y.right=z.right;
				y.right.p=y;
			}else {//第3种情况
				Transplant(T, z, y);
				y.left=z.left;
				y.left.p=y;
			}
		}
	}
}

3 测试:

public class BSTtest {
	public static void main(String[] args) {
		//构建一个搜索二叉树
		Binary_Search_Tree bst = new Binary_Search_Tree();
		//插入数据
		bst.Tree_insert(bst, new Node(2));
		bst.Tree_insert(bst, new Node(3));
		bst.Tree_insert(bst, new Node(4));
		bst.Tree_insert(bst, new Node(6));
		bst.Tree_insert(bst, new Node(7));
		bst.Tree_insert(bst, new Node(13));
		bst.Tree_insert(bst, new Node(9));
		bst.Tree_insert(bst, new Node(15));
		bst.Tree_insert(bst, new Node(17));
		bst.Tree_insert(bst, new Node(18));
		bst.Tree_insert(bst, new Node(20));
		
		System.out.println("搜索二叉树的中序遍历为：");
		bst.Inorder_Tree_Walk();
		System.out.println("搜索二叉树的前序遍历为：");
		bst.Preorder_Tree_Walk();
	
		System.out.println("搜索二叉树的最大值为："+bst.Tree_MaxiMum().key);
		System.out.println("搜索二叉树的最小值为："+bst.Tree_MiniMum().key);
		
		System.out.println("删除搜索二叉树中值为13的结点后中序遍历序列为:");
		bst.Tree_Delete(bst, bst.Tree_Search(20));
		bst.Inorder_Tree_Walk();
	}
}

4.结果: