本文共 4373 字,大约阅读时间需要 14 分钟。
public class BinarySearchTree<T extends Comparable<T>> { private Node<T> root;//根节点 private int count;//节点数 /* * 类部节点类 */ private static class Node<E>{ E value; Node<E> parent;//父亲节点 Node<E> left;//左节点 Node<E> right;//右节点 public Node(E value,Node<E> parent,Node<E> left,Node<E> right){ this.value=value; this.parent=parent; this.left=left; this.right=right; } } public BinarySearchTree(){ root=null;//初始化为空 } /* * 插入元素 */ public boolean insert(T t){ if(root==null){//如果当前为空,则插入元素作为根节点 root=new Node<T>(t,null,null,null); return true; } Node<T> newNode=new Node<T>(t,null,null,null);//创建一个节点 Node<T> pointer=root; while(true){ //如果当前的值比根节点值大,则当前值应当在根节点的右边 if(newNode.value.compareTo(pointer.value)>0){ if(pointer.right==null)//插入右边 { newNode.parent=pointer;//如果右边为空那么只要让当前节点的父节点为pointer pointer.right=newNode; //pointer的右孩子为当前节点 count++; return true; }else{ pointer=pointer.right;//继续遍历 } }else if(newNode.value.compareTo(pointer.value)<0){ if(pointer.left==null){//直接插入左边 newNode.parent=pointer; pointer.left=newNode; count++; return true; }else{ pointer=pointer.left; } }else{//相等了,不需要插入 return false; } } } /* * 查找元素 */ public T get(T t){ Node<T> n=getN(t); return n==null?null:n.value; } /* * 查找节点 */ private Node<T> getN(T t){ Node<T> cur=root; while(cur!=null){ //如果根节点的值比他小,那么该值应该在右边 if(cur.value.compareTo(t)<0)//右边子树找 { cur=cur.right; }else if(cur.value.compareTo(t)>0){ cur=cur.left; }else{ //找到节点 break; } } return cur; } /* * 获取某节点为根的树的最小元素 */ public T min(Node<T> n){ Node<T> min=minN(n); return min==null?null:min.value; } private Node<T> minN(Node<T> n){ Node<T> min=n; while(min!=null&&min.left!=null){ min=min.left; } return min; } /* * 获取某节点为根的树的最大元素 */ public T max(Node<T> n){ Node<T> max=maxN(n); return max==null?null:max.value; } private Node<T> maxN(Node<T> n){ Node<T> max=n; while(max!=null&&max.right!=null){ max=max.right; } return max; } /* * 中序遍历 */ public void leftRootRight(){ printLRR(root); } private void printLRR(Node<T> node){ if(node!=null){ //中序遍历为左中右 printLRR(node.left); System.out.println(node.value); printLRR(node.right); } } /* * 获取元素前驱 */ public T prev(T t){ Node<T> cur=getN(t); if(cur!=null){ return locatePrev(cur); } return null; } private T locatePrev(Node<T> cur){ Node<T> prev=locatePrevN(cur); return prev==null?null:prev.value; } /* * 定位到前驱节点 */ private Node<T> locatePrevN(Node<T> cur){ if(cur!=null){ //如果该节点左边有元素的话,则他的直接前驱应当为左边最大的一个元素 if(cur.left!=null) return maxN(cur.left); //如果左边没有元素的话,应该为在左边的祖先节点 //即有一个祖先有右孩子 Node<T> p=cur.parent; //如果当前节点不为空并且当前cur为p的左孩子时,就继续向上查找,直到找到右孩子 while(p!=null&&cur==p.left){ cur=p; p=p.parent; } return p==null?null:p; } return null; } public T next(T t){ Node<T> cur=getN(t); if(cur!=null){ return locateNext(cur); } return null; } private T locateNext(Node<T> cur){ Node<T> next=locateNextN(cur); return next==null?null:next.value; } private Node<T> locateNextN(Node<T> cur){ if(cur==null) return null; //如果当前节点有右孩子,那么就在右孩子中的最小的一个就为直接后继 if(cur.right!=null) return minN(cur.right); //如果当前节点没有右孩子,那么一直往上找,直到某个节点有左孩子 Node<T> p=cur.parent; while(p!=null&&cur==p.right){ cur=p; p=p.parent; } return p; } public boolean remove(T t){ Node<T> cur=getN(t);//先找到当前节点 if(cur!=null){//如果不为空,就做删除操作 if(doRemove(cur)){ cur=null; count--; return true; } } return false; } private boolean doRemove(Node<T> cur){ boolean isRoot=cur==root; //如果左节点和右节点都为空,那么直接删除,并且删除父亲节点中的指向就好了 if(cur.left==null&&cur.right==null){ if(isRoot) return true; if(cur==cur.parent.right) cur.parent.right=null; else cur.parent.left=null; return true; }else if(cur.left!=null&&cur.right!=null){ Node<T> replaceNode=locateNextN(cur); if(replaceNode==null) replaceNode=locatePrevN(cur); cur.value=replaceNode.value; doRemove(replaceNode); return true; }else{ //该节点有1个孩子, 直接将其父节点对应(左或右)孩子接到其非空孩子 Node<T> needLinkedNode = null; if (cur.left == null && cur.right != null){ //该节点有右孩子 needLinkedNode = cur.right; } else if(cur.left != null && cur.right == null){ //该节点有左孩子 needLinkedNode = cur.left; } if(isRoot){ //若该节点为根 root = needLinkedNode; return true; } if (cur == cur.parent.right) //该节点为父节点右孩子 cur.parent.right = needLinkedNode; else cur.parent.left = needLinkedNode; return true; } }}
//测试
public static void main(String[] args) {
// TODO Auto-generated method stub BinarySearchTree<Integer> a=new BinarySearchTree<>(); a.insert(3); a.insert(5); a.insert(1); a.insert(13); a.insert(4); a.insert(7); a.leftRootRight(); }转载地址:http://svjqi.baihongyu.com/