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)//加到左子節(jié)點(diǎn)
{
node.left=add(node.left,e);
}
else if(e.compareTo(node.e)>0)//加到右子節(jié)點(diǎn)
{
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(){//后續(xù)遍歷
postOrder(root,null);
}
public void postOrder(DiyPrintInterface<E> diyPrintInterface){//后續(xù)遍歷
if(diyPrintInterface!=null)
postOrder(root,diyPrintInterface);
}
private void postOrder(TreeNode node,DiyPrintInterface<E> diyPrintInterface){//后續(xù)遍歷
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)//增加元素非遞歸實(shí)現(xiàn)
{
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()//非遞歸實(shí)現(xiàn)查詢元素
{
printNR(null);
}
public void printNR(DiyPrintInterface<E> diyPrintInterface)//非遞歸實(shí)現(xiàn)查詢元素
{
if(root==null)
return;
Stack<TreeNode> stack=new Stack<>();
TreeNode current=root;
while (current!=null||!stack.isEmpty())//使用的是中序遍歷的方式 ①
{ //中序遍歷是先訪問左邊再訪問中間，最后訪問右邊
while (current!=null) //那么就先訪問最左邊阶冈，然后依次入棧
{ //當(dāng)已經(jīng)到達(dá)了最左邊，則可以操作左邊了
stack.push(current); //比如呢诬，最后這個(gè)current節(jié)點(diǎn)肯定為空
current=current.left; //這時(shí)已經(jīng)是最左邊了
} //那么讓他出棧
if(!stack.isEmpty()) //則這個(gè)棧頂元素就是最左邊的節(jié)點(diǎn)
{ //打印當(dāng)前節(jié)點(diǎn)
current=stack.pop(); //當(dāng)前節(jié)點(diǎn)是否還有右節(jié)點(diǎn)，有击碗，把當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)進(jìn)行同樣的操作 ①
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 {//棧不空,節(jié)點(diǎn)空
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就是最小的節(jié)點(diǎn)
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;
}
}
}
二分搜索樹java實(shí)現(xiàn)(遞歸與非遞歸)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來她倘，“玉大人璧微，你說我怎么就攤上這事∮擦海” “怎么了前硫？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長荧止。 經(jīng)常有香客問我屹电，道長阶剑，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任嗤详，我火速辦了婚禮个扰，結(jié)果婚禮上瓷炮，老公的妹妹穿的比我還像新娘葱色。我一直安慰自己，他們只是感情好娘香，可當(dāng)我...
- 文/花漫 我一把揭開白布苍狰。 她就那樣靜靜地躺著，像睡著了一般烘绽。 火紅的嫁衣襯著肌膚如雪淋昭。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼材失，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了硫豆？” 一聲冷哼從身側(cè)響起龙巨，我...
- 序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎熊响，沒想到半個(gè)月后旨别，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡汗茄，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年秸弛，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片剔难。...
- 正文 年R本政府宣布纯趋，位于F島的核電站憎兽，受9級特大地震影響冷离，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜纯命，卻給世界環(huán)境...
- 文/蒙蒙 一西剥、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧亿汞，春花似錦瞭空、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至吴裤，卻和暖如春旧找，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背麦牺。 一陣腳步聲響...
- 正文 我出身青樓魏颓，卻偏偏與公主長得像，于是被迫代替她去往敵國和親潮秘。 傳聞我的和親對象是個(gè)殘疾皇子琼开，可洞房花燭夜當(dāng)晚...
