package cn.ololee.bstnew;
import sun.reflect.generics.tree.Tree;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BST<E extends Comparable<E>> {
class TreeNode
{
E e;
TreeNode left;
TreeNode right;
int height;
int count;
public TreeNode(E e) {
this.e = e;
left=right=null;
count=1;
height=0;
}
}
public interface DiyPrintInterface<E extends Comparable<E>>{
void print(E e,int count);
}
private TreeNode root;
private int size;
private int nonrepeatSize=0;
public NRImpl NR=new NRImpl();
public void add(E e)
{
root=add(root,e);
}
private TreeNode add(TreeNode node,E e)
{
if(node==null)
{
node=new TreeNode(e);
size++;
nonrepeatSize++;
return node;
}
if(e.compareTo(node.e)<0)//加到左子节点
{
node.left=add(node.left,e);
}
else if(e.compareTo(node.e)>0)//加到右子节点
{
node.right=add(node.right,e);
}
else {
node.count++;
size++;
}
return node;
}
public void print()//中序遍历
{
print(root,null);
}
public void diyPrint(DiyPrintInterface diyPrintInterface)//中序遍历
{
if(diyPrintInterface!=null)
print(root,diyPrintInterface);
}
private void print(TreeNode node,DiyPrintInterface diyPrintInterface)//中序遍历
{
if(node==null)
return;
print(node.left,diyPrintInterface);
if(diyPrintInterface!=null)
diyPrintInterface.print(node.e,node.count);
else
print(node.e,node.count);
print(node.right,diyPrintInterface);
}
private void print(E e,int count)
{
if(count!=0)
{
for (int i = 0; i < count; i++) {
System.out.print(e+",");
}
}
else
System.out.print(e+",");
}
public void preOrder()//前序遍历
{
preOrder(root,null);
}
public void preOrder(DiyPrintInterface<E> diyPrintInterface)//前序遍历
{
if(diyPrintInterface!=null)
preOrder(root,diyPrintInterface);
}
private void preOrder(TreeNode node,DiyPrintInterface<E> diyPrintInterface)//前序遍历
{
if(node==null)
return;
if(diyPrintInterface!=null)
{
diyPrintInterface.print(node.e,node.count);
}
else
print(node.e,node.count);
preOrder(node.left,diyPrintInterface);
preOrder(node.right,diyPrintInterface);
}
public void inOrder()
{
print(root,null);
}
public void inOrder(DiyPrintInterface<E> diyPrintInterface)
{
if(diyPrintInterface!=null)
print(root,diyPrintInterface);
}
public void postOrder(){//后续遍历
postOrder(root,null);
}
public void postOrder(DiyPrintInterface<E> diyPrintInterface){//后续遍历
if(diyPrintInterface!=null)
postOrder(root,diyPrintInterface);
}
private void postOrder(TreeNode node,DiyPrintInterface<E> diyPrintInterface){//后续遍历
if(node==null)
return;
postOrder(node.left,diyPrintInterface);
postOrder(node.right,diyPrintInterface);
if(diyPrintInterface!=null)
diyPrintInterface.print(node.e,node.count);
else
print(node.e,node.count);
}
public boolean contains(E e)
{
return contains(root,e);
}
private boolean contains(TreeNode node,E e)
{
if(node==null)
return false;
int compare=e.compareTo(node.e);
if(compare==0)
return true;
else if(compare<0)
return contains(node.left,e);
else
return contains(node.right,e);
}
public E getMin()
{
if(size==0)
throw new IllegalArgumentException("BST is empty");
return getMin(root).e;
}
private TreeNode getMin(TreeNode node)
{
if(node.left==null)
return node;
return getMin(node.left);
}
public E getMax()
{
if(size==0)
throw new IllegalArgumentException("BST is empty");
return getMax(root);
}
private E getMax(TreeNode node)
{
if(node.right==null)
return node.e;
return getMax(node.right);
}
public E deleteMin()
{
E ret=getMin();
root=deleteMin(root);
return ret;
}
private TreeNode deleteMin(TreeNode node)
{
if(node.left==null) {
TreeNode right=node.right;
node.right=null;
resize(right.count);
return right;
}
node.left=deleteMin(node.left);
return node;
}
public E deleteMax()
{
E ret=getMax();
root=deleteMax(root);
return ret;
}
private TreeNode deleteMax(TreeNode node)
{
if(node.right==null)
{
TreeNode left=node.left;
node.left=null;
resize(left.count);
return left;
}
node.right=deleteMax(node.right);
return node;
}
public void delete(E e)
{
root=delete(root,e);
}
private TreeNode delete(TreeNode node,E e)
{
if(node==null)
return null;
int compare=e.compareTo(node.e);
if(compare<0)
{
node.left=delete(node.left,e);
}
else if(compare>0)
{
node.right=delete(node.right,e);
}
else {
if(node.left==null)
{
TreeNode right=node.right;
node.right=null;
size-=node.count;
nonrepeatSize--;
return right;
}
else if(node.right==null)
{
TreeNode left=node.left;
node.left=null;
size-=node.count;
nonrepeatSize--;
return left;
}
else {
TreeNode rightMin=getMin(node.right);
node.e=rightMin.e;
node.count=rightMin.count;
node.right=deleteMin(node.right);
}
}
return node;
}
public int getSize() {
return size;
}
public int getNonrepeatSize() {
return nonrepeatSize;
}
private void resize(int count)
{
size-=count;
}
public int getHeight()
{
return getHeight(root,0);
}
public int getHeight(TreeNode node,int depth)
{
if(node==null)
{
return depth;
}
return Math.max(getHeight(node.left,depth+1),getHeight(node.right,depth+1));
}
public void levelOrder()
{
levelOrder(null);
}
public void levelOrder(DiyPrintInterface<E> diyPrintInterface)
{
if (root==null)
return;
Queue<TreeNode> queue=new LinkedList<>();
if(root!=null)
{
queue.add(root);
}
TreeNode current=root;
while (!queue.isEmpty())
{
current=queue.poll();
if(diyPrintInterface!=null)
diyPrintInterface.print(current.e,current.count);
else
print(current.e,current.count);
if(current.left!=null)
queue.add(current.left);
if(current.right!=null)
queue.add(current.right);
}
}
class NRImpl
{
public void addNR(E e)//增加元素非递归实现
{
if (root==null)
{
size++;
nonrepeatSize++;
root=new TreeNode(e);
return;
}
TreeNode current=root;
while (current!=null)
{
int compare=e.compareTo(current.e);
if(compare<0)
{
if(current.left==null)
{
size++;
nonrepeatSize++;
current.left=new TreeNode(e);
return;
}
else
current=current.left;
}
else if(compare>0)
{
if(current.right==null)
{
size++;
nonrepeatSize++;
current.right=new TreeNode(e);
return;
}
else
current=current.right;
}
else {
current.count++;
size++;
return;
}
}
}
public void printNR()//非递归实现查询元素
{
printNR(null);
}
public void printNR(DiyPrintInterface<E> diyPrintInterface)//非递归实现查询元素
{
if(root==null)
return;
Stack<TreeNode> stack=new Stack<>();
TreeNode current=root;
while (current!=null||!stack.isEmpty())//使用的是中序遍历的方式 ①
{ //中序遍历是先访问左边再访问中间，最后访问右边
while (current!=null) //那么就先访问最左边，然后依次入栈
{ //当已经到达了最左边，则可以操作左边了
stack.push(current); //比如，最后这个current节点肯定为空
current=current.left; //这时已经是最左边了
} //那么让他出栈
if(!stack.isEmpty()) //则这个栈顶元素就是最左边的节点
{ //打印当前节点
current=stack.pop(); //当前节点是否还有右节点，有，把当前节点右节点进行同样的操作 ①
if(diyPrintInterface!=null)
{
diyPrintInterface.print(current.e,current.count);
}
else
print(current.e,current.count);
current=current.right;
}
}
}
public void preOrderNR(){
preOrderNR(null);
}
public void preOrderNR(DiyPrintInterface<E> diyPrintInterface) {
if(root==null)
return;
Stack<TreeNode> stack=new Stack<>();
TreeNode current=root;
//前序遍历,先中间再左边再右边
while (current!=null||!stack.isEmpty())
{
if(current!=null)
{
if(diyPrintInterface!=null)
diyPrintInterface.print(current.e,current.count);
else
print(current.e,current.count);
if(current.right!=null)
stack.push(current.right);
current=current.left;
}
else
current=stack.pop();
}
}
public void inOrderNR(){
printNR();
}
public void inOrderNR(DiyPrintInterface<E> diyPrintInterface){
printNR(diyPrintInterface);
}
public void postOrderNR(){
postOrderNR(null);
}
public void postOrderNR(DiyPrintInterface<E> diyPrintInterface){
if(root==null)
return;
TreeNode current=root;
Stack<TreeNode> stack=new Stack<>();
HashMap<E,Integer> map=new HashMap<>();
while (current!=null||!stack.isEmpty())
{
if(current!=null)
{
stack.push(current);
map.put(current.e,1);
current=current.left;
}
else {//栈不空,节点空
current=stack.peek();
if(map.get(current.e)==2)
{
stack.pop();
if(diyPrintInterface!=null)
diyPrintInterface.print(current.e,current.count);
else
print(current.e,current.count);
current=null;
}
else {
map.put(current.e,2);
current=current.right;
}
}
}
}
public boolean containsNR(E e)
{
if(root==null)
return false;
TreeNode current=root;
int compare;
while (current!=null)
{
compare=e.compareTo(current.e);
if(compare==0)
return true;
else if(compare<0)
current=current.left;
else
current=current.right;
}
return false;
}
public E getMinNR(){
TreeNode current=root;
while (current.left!=null)
current=current.left;
return current.e;
}
public E getMaxNR() {
TreeNode current=root;
while (current.right!=null)
current=current.right;
return current.e;
}
public E deleteMinNR()
{
TreeNode min=root,parent = root;
while (min.left!=null) {
parent=min;
min=min.left;
}
//min就是最小的节点
E ret=min.e;
parent.left=min.right;
min.right=null;
resize(min.count);
return ret;
}
public E deleteMaxNR()
{
TreeNode max=root,parent=root;
while (max.right!=null)
{
parent=max;
max=max.right;
}
E ret=max.e;
parent.right=max.left;
max.left=null;
resize(max.count);
return ret;
}
}
}
网友评论