数据结构与算法分析 -- 二叉查找树的实现以及一些常用操作

   二叉树的一个重要应用在于它们可以在查找中使用。

 

   今天来记录一下二叉查找树的学习心得；

 

   首先来看看，什么是二叉查找树？

   简单的说，它有一个性质。 既

   对于X节点来说，

                       它的左子树中的所有项都小于X的项，

                       它的右子树中的所有项都大于X的项。

    如图3

  

  下面我们用代码来实现一个简单的二叉查找树：

   代码如下：

 

package com.base.tree;

public class BinartSearchTree {
	public static void main(String[] args) {
		BinaryTree root=new BinaryTree();
		BinaryTree.TreeNode t=new BinaryTree.TreeNode(6);
		BinaryTree.TreeNode t2=new BinaryTree.TreeNode(2);
		BinaryTree.TreeNode t3=new BinaryTree.TreeNode(1);
		BinaryTree.TreeNode t4=new BinaryTree.TreeNode(5);
		BinaryTree.TreeNode t5=new BinaryTree.TreeNode(3);
		BinaryTree.TreeNode t6=new BinaryTree.TreeNode(4);
		BinaryTree.TreeNode t7=new BinaryTree.TreeNode(8);
		t.setLeft(t2);
		t.setRight(t7);
		t2.setLeft(t3);
		t2.setRight(t4);
		t4.setLeft(t5);
		t5.setRight(t6);
		root.setRoot(t);
		/*=================构造树，如图2-1=================*/

		root.remove(2);
		root.printTree();
	}
}


/**
 * 二叉查找树的性质：对于X节点，左边子树的所有项都小于X节点的项，右边子树的所有项都大于X节点的项。
 * @author google
 *
 */
class BinaryTree{
	private TreeNode root;
	
	public void setRoot(TreeNode root) {
		this.root = root;
	}

	public BinaryTree(){
		root=null;
	}
	
	public void makeEmpty(){
		root=null;
	}
	
	public boolean isEmpty(){
		return root==null;
	}
	
	public boolean contains(int data){
		return contains(data,root);
	}
	
	public int findMin(){
		if(isEmpty()) return -1;
		return findMin(root).data;
	}
	
	public int findMax(){
		if(isEmpty())return -1;
		return findMax(root).data;
	}
	
	public void insert(int data){
		root=insert(data, root);
	}
	
	public void remove(int data){
		root=remove(data,root);
	}
	
	public void printTree(){
		if(isEmpty())
			System.out.println("Empty Tree……");
		else
			printTree(root);
	}
	
	/**
	 * 打印树
	 * @param t
	 */
	private void printTree(TreeNode t){
		if(t!=null){
			printTree(t.left);
			System.out.println(t.data);
			printTree(t.right);	
		}
	}
	
	/**
	 * 在字树中查找与元素
	 * 
	 * @param x
	 * @param node
	 * @return
	 */
	private boolean contains(int x,TreeNode t){
		if(t==null)return false;
		if(x>t.data){
			return contains(x,t.right);
		}if(x<t.data){
			return contains(x,t.left);
		}else{
			return true;
		}
	}
	
	
	/**
	 * 删除节点，需要考虑需要删除节点的情况如下：
	 * 1.当需要删除的是一片树叶，即可立刻删除
	 * 2.有一个节点： 可以在其父节点调整链的指向，绕过该节点被删除。 图1
	 * 3.当有两个儿子节点时：
	 * 用右子树中最小数据代替该节点数据，并递归删除那个节点。       图2-2
	 * @param data
	 * @param t
	 * @return
	 */
	private TreeNode remove(int data,TreeNode t){
		if(t==null)return t;
		if(data>t.data){
			t.right=remove(data,t.right);
		}else if(data<t.data){
			t.left=remove(data,t.left);
		}else if(t.left!=null&&t.right!=null){
			//处理需要删除的节点有2个节点的情况
			//
			t.data=findMin(t.right).data;
			t.right=remove(t.data,t.right);
		}else{
			t=(t.left!=null)?t.left:t.right;
		}
		return t;
			
	}
	
	/**
	 * 将x插入到子树中
	 * @param data
	 * @param t
	 * @return
	 */
	private TreeNode insert(int data,TreeNode t){
		if(t==null)return new TreeNode(data,null,null);
		
		//比较大小， 将新建一个节点后，重新构造树
		if(data>t.data){
			t.right=insert(data,t.right);
		}else if(data<t.data){
			t.left=insert(data,t.left);
		}
		return t;
	}
	
	/**
	 * 查找最小元素, 从根开始，一路向左子树查找 （递归实现）
	 * @param t
	 * @return
	 */
	private TreeNode findMin(TreeNode t){
		if(t==null)return null;
		if(t.left==null)
			return t;
		return findMin(t.left);
	}
	
	
	/**
	 * 查找最大元素, 从根开始，一路向右子树查找 （非递归实现）
	 * @param t
	 * @return
	 */
	private TreeNode findMax(TreeNode t){
		if(t!=null)
			while(t.right!=null)
				t=t.right;
		return t;
	}


	/**
	 * 树节点类
	 * @author google
	 *
	 */
	public static class TreeNode{
		private int data;
		private TreeNode left;
		private TreeNode right;
		public TreeNode(){}
		public TreeNode(int data){
			this.data=data;
		}
		public TreeNode(int data,TreeNode left,TreeNode right){
			this.data=data;
			this.left=left;
			this.right=right;
		}
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
		}
		public TreeNode getLeft() {
			return left;
		}
		public void setLeft(TreeNode left) {
			this.left = left;
		}
		public TreeNode getRight() {
			return right;
		}
		public void setRight(TreeNode right) {
			this.right = right;
		}
	}
}

 

 其中的remove方法可能理解相对要难一点，下面附上图片，让其原理一目了然。