package com.itany.erchachazhaoshu;
public class BinarySearchTree<T extends Comparable<? super T>>
{
//定义二叉查找树的根节点 每个查找二叉树都有一个自己的root 节点 root外界看不到
private BinaryNode<T> root;
public BinarySearchTree()
{
root=null;
}
//节点类
private static class BinaryNode<T>
{
private T element;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNode(T element)
{
this(element, null, null);
}
public BinaryNode(T element,BinaryNode<T> left,BinaryNode<T> right)
{
this.element=element;
this.left=left;
this.right=right;
}
}
public void makeEmpty()
{
root=null;
}
public boolean isEmpty()
{
return root==null;
}
public boolean contains(T t)
{
return contains(t,root);
}
//外界是不认识节点的 仅仅会返回T 布尔 或者根本无返回值
public T findMax() throws Exception
{
if(isEmpty())
throw new Exception();
return findMax(root).element;
}
public T findMin() throws Exception
{
if(isEmpty())
throw new Exception();
return findMin(root).element;
}
public void insert(T t)
{
root=insert(t,root);
}
public void remove(T t)
{
root=remove(t,root);
}
public void printTree()
{
if(isEmpty())
System.out.println("Empty Tree");
else
printTree(root);
}
//中序遍历
private void printTree(BinaryNode<T> root)
{
//假设递归到了叶子节点 没有左右的部分就不运行遍历 并且if也完毕了对非空的推断
if(null!=root)
{
printTree(root.left);
System.out.println(root.element);
printTree(root.right);
}
}
//此处使用的是尾递归
private boolean contains(T t,BinaryNode<T> root)
{
//必须在一開始就推断是否为null 否则在调用方法或元素时 会产生空指针异常 也是一个基准条件
if(root==null)
return false;
int compareRes=t.compareTo(root.element);
if(compareRes==0)
return true;
else if(compareRes<0)
return contains(t,root.left);//不会使栈频繁进出 仅仅会覆盖当前栈
else
return contains(t,root.right);
}
// 方法二 使用循环取代尾递归找出最大 是返回相应的那个节点
private BinaryNode<T> findMax(BinaryNode<T> root)
{
if(root==null)
return null;
else
{
while(root.right!=null)
{
root=root.right ;
}
}
return root;
}
//方法一 使用递归查找 返回最小节点的引用
private BinaryNode<T> findMin(BinaryNode<T> root)
{
//必须在一開始就推断是否为null 否则在调用方法或元素时 会产生空指针异常
if(root==null)
return null;
//基准条件
else if(root.left==null)
return root;
else
return findMin(root.left);
}
//返回一个插入了之后的整个节点 逐级返回
private BinaryNode<T> insert(T t,BinaryNode<T> root)
{
if(root==null)
return new BinaryNode<T>(t,null,null);
else
{
int com=t.compareTo(root.element);
if(com==0)
;
else if(com<0)
//不断更新当前root的left值 并返回root
root.left=insert(t,root.left);
else
root.right=insert(t,root.right);
return root;
}
}
//删除和添加一样 都要返回改动之后的节点
private BinaryNode<T> remove(T t,BinaryNode<T> root)
{
//没有找到删除的 什么也不做 直接返回该root
if(root==null)
return root;
int com=t.compareTo(root.element);
if(com<0)
{
root.left=remove(t,root.left);
}
else if(com>0)
{
root.right=remove(t,root.right);
}
else
{
//有两个儿子的情况
if(root.left!=null && root.right!=null)
{
root.element=findMin(root.right).element;
root.right=remove(root.element,root.right);//更新删除之后
}
else//包含一个儿子都没有的情况 有一个儿子的情况
return (root.left!=null)?root.left:root.right;
}
return root;
}
}
package com.itany.erchachazhaoshu;
public class Test
{
public static void main(String[] args)
{
BinarySearchTree bt=new BinarySearchTree();
bt.insert(3);
bt.insert(13);
bt.insert(1);
try
{
System.out.println("max:"+bt.findMax());
System.out.println("max:"+bt.findMin());
System.out.println(bt.contains(3));
bt.remove(13);
System.out.println(bt.contains(13));
}
catch (Exception e)
{
e.printStackTrace();
}
}
}