package com.utils;


import java.util.Iterator;
import java.util.NoSuchElementException;


/**
?* 二叉排序樹，也可以成為二叉查找樹
?* 它的性質如下：
?* 1.若它的左子樹不為空，則左子樹上所有的節點均小于其根節點
?* 2.若它的右子樹不為空，則右子樹上所有的節點的值均大于根節點
?* 3.它的左右子樹也分別為二叉排序樹
?*?
?* 簡單起見，假設樹中元素都實現了Comparable接口或者他們可以按自然順序比較
?*/
public class BinarySortTree<E> {

/**
* 根節點
*/
private Entry<E> root = null;

/**
* 樹中元素個數
*/
private int size = 0;


public BinarySortTree(){

}


public int size(){
return size;
}

public E getRoot(){
return root==null?null:root.element;
}

/**
* 查找指定元素element是否在樹中存在，如果查找失敗確認其添加的位置
* 查找成功直接返回
*?
* @param t ?表示從此節點開始往下查找
* @param f ?保存t的父節點
* @param p ?若查找成功p指向此數據元素節點，否則返回查找路徑上的最后一個節點
*?
* 這是遞歸實現
*/
private boolean searchBST(Entry<E> t,Object element,Entry<E> f,Entry<E> p){
if(t == null){
p = f;
return false;
}
Comparable<? super E> e = (Comparable<? super E>) element;
int cmp = e.compareTo(t.element);
if(cmp < 0){
return searchBST(t.left,element,t,p);
}else if(cmp > 0){
return searchBST(t.right,element,t,p);
}else{
p = t;
return true;
}
}


/**
*?
* 這是非遞歸實現
*/
private boolean searchBST(Object element,Entry[] p){
Comparable<? super E> e = (Comparable<? super E>) element;
Entry<E> parent = root;
Entry<E> pp = null; //保存parent父節點
while(parent != null){
int cmp = e.compareTo(parent.element);
pp = parent;
if(cmp < 0){
parent = parent.left;
}else if(cmp > 0){
parent = parent.right;
}else{
p[0] = parent;
return true;
}
}
p[0] = pp;
return false;
}

/**
* 首先查找二叉排序樹，如果找不到指定元素
* 則插入到二叉樹中
*/
public boolean add(E element){
Entry<E> t = root;
if(t == null){ //如果根節點為空
root = new Entry<E>(element,null);
size = 1;
return false;
}
Comparable<? super E> e = (Comparable<? super E>) element;
Entry[] p = new Entry[1] ;
if(!searchBST(element,p)){ //查找失敗，插入元素
Entry<E> s = new Entry<E>(element,p[0]);
int cmp = e.compareTo((E) p[0].element);
if(cmp < 0){
p[0].left = s;
}
if(cmp > 0){
p[0].right = s;
}
size++;
return true;
}
return false;
}

/**
* 移除節點，同時調整二叉樹使之為二叉排序樹
* 實現原理：
* 假設要刪除的節點為p，其父節點為f，而p是f的左節點
* 分三種情況討論:
* 1.若p為葉子節點，直接刪除
* 2.若p有只有一個左孩子或者一個右孩子，則刪除p，使PL或者PR為f的左子樹
* 3.若p的左右子樹均不為空，由二叉排序樹的特點可知在刪除p前，中序遍歷此二叉樹
* ? 可以得到一個有序序列，在刪去p后為了保持其他元素的相對位置不變，可以這樣做：
* ? 令p的直接前驅(或直接后繼)替代p，然后刪除其直接前驅或直接后繼。其直接前驅可由
* ? 中序遍歷的特點獲得
*/
public boolean remove(Object o){
Entry[] p = new Entry[1] ;
if(searchBST(o,p)){ //查找成功，刪除元素
deleteEntry(p[0]);
return true;
}
return false;
}

private void deleteEntry(Entry<E> p){
size --;
//如果p左右子樹都不為空，找到其直接后繼，替換p
if (p.left != null && p.right != null) {
Entry<E> s = successor(p);
p.element = s.element;
p = s;
}
Entry<E> replacement = (p.left != null ? p.left : p.right);


? ? ? ? if (replacement != null) { //如果其左右子樹有其一不為空
? ? ? ? ? ? replacement.parent = p.parent;
? ? ? ? ? ? if (p.parent == null) //如果p為root節點
? ? ? ? ? ? ? ? root = replacement;
? ? ? ? ? ? else if (p == p.parent.left) //如果p是左孩子
? ? ? ? ? ? ? ? p.parent.left ?= replacement;
? ? ? ? ? ? else //如果p是右孩子
? ? ? ? ? ? ? ? p.parent.right = replacement;


? ? ? ? ? ? p.left = p.right = p.parent = null; //p的指針清空


? ? ? ? } else if (p.parent == null) { // 如果全樹只有一個節點
? ? ? ? ? ? root = null;
? ? ? ? } else { ?//左右子樹都為空,p為葉子節點
? ? ? ? ? ? if (p.parent != null) {
? ? ? ? ? ? ? ? if (p == p.parent.left)
? ? ? ? ? ? ? ? ? ? p.parent.left = null;
? ? ? ? ? ? ? ? else if (p == p.parent.right)
? ? ? ? ? ? ? ? ? ? p.parent.right = null;
? ? ? ? ? ? ? ? p.parent = null;
? ? ? ? ? ? }
? ? ? ? }


}

/**
* 返回以中序遍歷方式遍歷樹時，t的直接后繼
*/
static <E> Entry<E> successor(Entry<E> t) {
if (t == null)
return null;
else if (t.right != null) { //往右，然后向左直到盡頭
Entry<E> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else { //right為空，如果t是p的左子樹，則p為t的直接后繼
Entry<E> p = t.parent;
Entry<E> ch = t;
while (p != null && ch == p.right) { //如果t是p的右子樹，則繼續向上搜索其直接后繼
ch = p;
p = p.parent;
}
return p;
}
? ? }

public Iterator<E> itrator(){
return new BinarySortIterator();
}

//返回中序遍歷此樹的迭代器
private class BinarySortIterator implements Iterator<E>{
Entry<E> next;
? ?Entry<E> lastReturned;
? ?
? ?public BinarySortIterator(){
? ? Entry<E> s = root;
? ? if(s !=null){
? ? while(s.left != null){ //找到中序遍歷的第一個元素
? ? s = s.left;
? ? }
? ? }
? ? next = s; //賦給next
? ?}
? ?
@Override
public boolean hasNext() {
return next!=null;
}


@Override
public E next() {
Entry<E> e = next;
if (e == null)
throw new NoSuchElementException();
next = successor(e);
lastReturned = e;
return e.element;
}


@Override
public void remove() {
? ? ? ? ? ? if (lastReturned == null)
? ? ? ? ? ? ? ? throw new IllegalStateException();
? ? ? ? ? ? // deleted entries are replaced by their successors
? ? ? ? ? ? if (lastReturned.left != null && lastReturned.right != null)
? ? ? ? ? ? ? ? next = lastReturned;
? ? ? ? ? ? deleteEntry(lastReturned);
? ? ? ? ? ? lastReturned = null;
}
}

/**
* 樹節點，為方便起見不寫get，Set方法
*/
static class Entry<E>{
E element;
Entry<E> parent;
Entry<E> left;
Entry<E> right;

public Entry(E element,Entry<E> parent){
this.element = element;
this.parent = parent;
}

public Entry(){}
}

//just for test
public static void main(String[] args) {
BinarySortTree<Integer> tree = new BinarySortTree<Integer>();
tree.add(45);
tree.add(24);
tree.add(53);
tree.add(45);
tree.add(12);
tree.add(90);

System.out.println(tree.remove(400));
System.out.println(tree.remove(45));
System.out.println("root="+tree.getRoot());
Iterator<Integer> it = tree.itrator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println(tree.size());
}


}

總結

以上是生活随笔為你收集整理的二叉排序树的实现——java的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。