定義二叉樹的節(jié)點(diǎn)：包含左節(jié)點(diǎn)扫俺，右節(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)的值
/**
* 定義二叉搜索樹的節(jié)點(diǎn)
* @param <AnyType>
*/
private static class BinaryNode<AnyType>{
BinaryNode(AnyType theElement){
this(theElement, null, null);
}
//通過構(gòu)造函數(shù)創(chuàng)建節(jié)點(diǎn)
BinaryNode(AnyType theElement, BinaryNode<AnyType> left, BinaryNode<AnyType> right){
this.theElement = theElement;
this.left = left;
this.right = right;
}
AnyType theElement;
BinaryNode left;
BinaryNode right;
}
節(jié)點(diǎn)之間的比較方法：通過自定義的Comparator或默認(rèn)的Compare方法
/**
* 定義比較方法：若傳入了比較方式，則用傳入的比較方式，否則用默認(rèn)方式
* 返回為0表示 lhs = rhs
* 返回為負(fù)數(shù)表示 lhs < rhs
* 返回為正數(shù)表示 lhs > rhs
* @param lhs
* @param rhs
* @return
*/
private int myCompare(AnyType lhs, AnyType rhs){
if (cmp != null){
return cmp.compare(lhs, rhs);
} else {
return ((Comparable)lhs).compareTo(rhs);
}
}
查找結(jié)點(diǎn)：比較傳入的元素與當(dāng)前結(jié)點(diǎn)元素的值按价，若傳入的元素小于當(dāng)前節(jié)點(diǎn)的元素赚爵，則繼續(xù)查找當(dāng)前結(jié)點(diǎn)的左子樹瓢湃，若大于矢炼，則繼續(xù)查找當(dāng)前結(jié)點(diǎn)的右子樹，若等于，表示找到該節(jié)點(diǎn)揖闸，返回true揍堕。
/**
* 搜索二叉樹中是否包含某個(gè)元素節(jié)點(diǎn)
* @param x
* @param t
* @return
*/
private boolean contains(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return false;
}
//比較元素與當(dāng)前結(jié)點(diǎn)的元素
int compareResult = myCompare(x, t.theElement);
//小于當(dāng)前元素，則搜索左子樹
if (compareResult < 0){
contains(x, t.left);
}
//大于當(dāng)前元素汤纸，則搜索右子樹
else if (compareResult > 0){
contains(x, t.right);
}
//等于情況衩茸，表示存在，直接返回
return true;
}
插入節(jié)點(diǎn)：若當(dāng)前結(jié)點(diǎn)為空贮泞，則將新節(jié)點(diǎn)放置此處楞慈，否則判斷傳入的值與當(dāng)前節(jié)點(diǎn)的值，若傳入的值小于當(dāng)前結(jié)點(diǎn)的值則繼續(xù)搜索當(dāng)前結(jié)點(diǎn)的左子樹啃擦，若大于囊蓝，則繼續(xù)搜索當(dāng)前結(jié)點(diǎn)的右子樹。
/**
* 實(shí)現(xiàn)插入操作
* @param x
* @param t
* @return
*/
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
//當(dāng)前節(jié)點(diǎn)為空议惰，則將該節(jié)點(diǎn)在此處
if (t == null){
return new BinaryNode<AnyType>(x, null, null);
}
//進(jìn)行比較
int compareResult = myCompare(x, t.theElement);
//元素小于當(dāng)前結(jié)點(diǎn)元素，則加入到左子樹
if (compareResult < 0){
t.left = insert(x, t.left);
} else if (compareResult > 0){
t.right = insert(x, t.right);
} else {
//do nothing
}
return t;
}
刪除某個(gè)節(jié)點(diǎn)：先根據(jù)給定的值找到要?jiǎng)h除的節(jié)點(diǎn)乡恕，若沒有找到該節(jié)點(diǎn)言询，則不會(huì)進(jìn)行刪除操作。
a. 刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)傲宜，即沒有孩子运杭，則直接刪除即可，不會(huì)破壞樹的結(jié)構(gòu)函卒。
Paste_Image.png
b. 若節(jié)點(diǎn)中只包含左子樹辆憔，或只包含右子樹，則直接刪除該節(jié)點(diǎn)报嵌，并將其左子樹或右子樹設(shè)置為父節(jié)點(diǎn)的左子樹或右子樹即可虱咧。
Paste_Image.png
c. 當(dāng)刪除的節(jié)點(diǎn)中包含左右子樹時(shí)，一般的策略是用其右子樹的最小數(shù)據(jù)代替要?jiǎng)h除的節(jié)點(diǎn)锚国，并遞歸刪除該節(jié)點(diǎn)腕巡。因?yàn)橛易訕涞淖钚」?jié)點(diǎn)是不可能有左子樹的，因此第二次刪除較為容易血筑。
Paste_Image.png
如上圖绘沉，我們要?jiǎng)h除的節(jié)點(diǎn)是5，則找到該節(jié)點(diǎn)豺总，然后找到節(jié)點(diǎn)值為5的右子樹的最小節(jié)點(diǎn)车伞，即節(jié)點(diǎn)值為6的節(jié)點(diǎn)--->將節(jié)點(diǎn)值為6的節(jié)點(diǎn)代替要?jiǎng)h除的節(jié)點(diǎn)5---->然后遞歸刪除原本的節(jié)點(diǎn)6
/**
* 實(shí)現(xiàn)移除某個(gè)節(jié)點(diǎn)
* @param x
* @param t
* @return
*/
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return t;
}
//比較大小
int compareResult = myCompare(x, t.theElement);
//元素小于當(dāng)前結(jié)點(diǎn)元素，則搜索左子樹
if (compareResult < 0){
t.left = remove(x, t.left);
}
//元素大于當(dāng)前結(jié)點(diǎn)元素喻喳，則搜索右子樹
else if (compareResult > 0){
t.right = remove(x, t.right);
}
//相等另玖，表示找到對(duì)應(yīng)的節(jié)點(diǎn)，如果該節(jié)點(diǎn)存在左右孩子
else if (t.left != null && t.right != null){
//搜索到右子樹的最小節(jié)點(diǎn)，并替代當(dāng)前結(jié)點(diǎn)
t.theElement = (AnyType) findMin(t.right).theElement;
//并遞歸刪除右子樹的最小節(jié)點(diǎn)
t.right = remove(t.theElement, t.right);
}
//否則日矫，將不為空的孩子節(jié)點(diǎn)替代掉當(dāng)前結(jié)點(diǎn)
else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
查找最大的節(jié)點(diǎn)：不斷向右邊搜索節(jié)點(diǎn)赂弓，直到該節(jié)點(diǎn)不存在右邊子節(jié)點(diǎn)。
查找最小的節(jié)點(diǎn)：不斷向左邊搜索節(jié)點(diǎn)哪轿，直到該節(jié)點(diǎn)不存在左邊子節(jié)點(diǎn)盈魁。
/**
* 實(shí)現(xiàn)獲取二叉樹中最小的節(jié)點(diǎn)
* 遞歸查找左子樹，直到當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)為空窃诉，則返回當(dāng)前節(jié)點(diǎn)
* @param t
* @return
*/
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
if (t == null){
return null;
} else if (t.left == null){
return t;
}
return findMin(t.left);
}
/**
* 實(shí)現(xiàn)獲取二叉樹中最大的節(jié)點(diǎn)
* 遞歸查找右子樹杨耙，直到當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為空，返回當(dāng)前節(jié)點(diǎn)
* @param t
* @return
*/
private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
if (t == null){
return null;
} else if (t.right == null){
return t;
}
return findMax(t.right);
}
實(shí)現(xiàn)三種遍歷樹的方式：
/**
* 前序遍歷
* 訪問順序?yàn)椋焊?jié)點(diǎn)->左節(jié)點(diǎn)->右節(jié)點(diǎn)
* @param node
*/
public void preOrder(BinaryNode<AnyType> node){
if (node != null){
System.out.print(node.right + " ");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 中序遍歷
* 訪問順序?yàn)椋鹤蠊?jié)點(diǎn)->根節(jié)點(diǎn)->右節(jié)點(diǎn)
* @param node
*/
public void inOrder(BinaryNode<AnyType> node){
if (node != null){
inOrder(node.left);
System.out.print(node.theElement + " ");
inOrder(node.right);
}
}
/**
* 后序遍歷
* 訪問順序?yàn)椋鹤蠊?jié)點(diǎn)->右節(jié)點(diǎn)->根節(jié)點(diǎn)
* @param node
*/
public void postOrder(BinaryNode<AnyType> node){
if (node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.theElement + " ");
}
}
完整代碼：
package BinaryTree;
import org.omg.CORBA.Any;
import java.nio.BufferUnderflowException;
import java.util.Comparator;
/**
* Created by Administrator on 2017/3/7/007.
* 實(shí)現(xiàn)搜索二叉樹的基本操作
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
/**
* 定義二叉搜索樹的節(jié)點(diǎn)
* @param <AnyType>
*/
private static class BinaryNode<AnyType>{
BinaryNode(AnyType theElement){
this(theElement, null, null);
}
//通過構(gòu)造函數(shù)創(chuàng)建節(jié)點(diǎn)
BinaryNode(AnyType theElement, BinaryNode<AnyType> left, BinaryNode<AnyType> right){
this.theElement = theElement;
this.left = left;
this.right = right;
}
AnyType theElement;
BinaryNode left;
BinaryNode right;
}
/**
* 定義二叉樹的根節(jié)點(diǎn)
*/
private BinaryNode<AnyType> root;
/**
* 定義比較方式
*/
private Comparator<? super AnyType> cmp;
public BinarySearchTree(){
this(null);
}
/**
* 構(gòu)造函數(shù)飘痛，傳入比較方式
* @param c
*/
public BinarySearchTree(Comparator<? super AnyType> c){
root = null;
cmp = c;
}
/**
* 定義比較方法：若傳入了比較方式珊膜，則用傳入的比較方式，否則用默認(rèn)的方法
* @param lhs
* @param rhs
* @return
*/
private int myCompare(AnyType lhs, AnyType rhs){
if (cmp != null){
return cmp.compare(lhs, rhs);
} else {
return ((Comparable)lhs).compareTo(rhs);
}
}
/**
* 使二叉樹變?yōu)榭? */
public void makeEmpty(){
root = null;
}
/**
* 檢查二叉樹是否為空
* @return
*/
public boolean isEmpty(){
return root == null;
}
/**
* 檢查二叉樹中是否包含某個(gè)元素
* @param x
* @return
*/
public boolean contains(AnyType x){
return contains(x, root);
}
/**
* 搜索查找二叉樹中最小的元素
* @return
*/
public AnyType findMin(){
if (isEmpty()) throw new BufferUnderflowException();
return findMin(root).theElement;
}
/**
* 搜索查找二叉樹中最大的元素
* @return
*/
public AnyType findMax(){
if (isEmpty()) throw new BufferUnderflowException();
return findMax(root).theElement;
}
/**
* 插入元素
* @param x
*/
public void insert(AnyType x){
root = insert(x, root);
}
/**
* 刪除元素
* @param x
*/
public void remove(AnyType x){
root = remove(x, root);
}
/**
* 搜索二叉樹中是否包含某個(gè)元素節(jié)點(diǎn)
* @param x
* @param t
* @return
*/
private boolean contains(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return false;
}
//比較元素與當(dāng)前結(jié)點(diǎn)的元素
int compareResult = myCompare(x, t.theElement);
//小于當(dāng)前元素宣脉，則搜索左子樹
if (compareResult < 0){
contains(x, t.left);
}
//大于當(dāng)前元素车柠，則搜索右子樹
else if (compareResult > 0){
contains(x, t.right);
}
//等于情況，表示存在塑猖，直接返回
return true;
}
/**
* 實(shí)現(xiàn)獲取二叉樹中最小的節(jié)點(diǎn)
* 遞歸查找左子樹竹祷，直到當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)為空，則返回當(dāng)前節(jié)點(diǎn)
* @param t
* @return
*/
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
if (t == null){
return null;
} else if (t.left == null){
return t;
}
return findMin(t.left);
}
/**
* 實(shí)現(xiàn)獲取二叉樹中最大的節(jié)點(diǎn)
* 遞歸查找右子樹羊苟，直到當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為空塑陵，返回當(dāng)前節(jié)點(diǎn)
* @param t
* @return
*/
private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
if (t == null){
return null;
} else if (t.right == null){
return t;
}
return findMax(t.right);
}
/**
* 實(shí)現(xiàn)插入操作
* @param x
* @param t
* @return
*/
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
//當(dāng)前節(jié)點(diǎn)為空，則將該節(jié)點(diǎn)在此處
if (t == null){
return new BinaryNode<AnyType>(x, null, null);
}
//進(jìn)行比較
int compareResult = myCompare(x, t.theElement);
//元素小于當(dāng)前結(jié)點(diǎn)元素蜡励，則加入到左子樹
if (compareResult < 0){
t.left = insert(x, t.left);
} else if (compareResult > 0){
t.right = insert(x, t.right);
} else {
//do nothing
}
return t;
}
/**
* 實(shí)現(xiàn)移除某個(gè)節(jié)點(diǎn)
* @param x
* @param t
* @return
*/
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
if (t == null){
return t;
}
//比較大小
int compareResult = myCompare(x, t.theElement);
//元素小于當(dāng)前結(jié)點(diǎn)元素令花，則搜索左子樹
if (compareResult < 0){
t.left = remove(x, t.left);
}
//元素大于當(dāng)前結(jié)點(diǎn)元素，則搜索右子樹
else if (compareResult > 0){
t.right = remove(x, t.right);
}
//相等凉倚，表示找到對(duì)應(yīng)的節(jié)點(diǎn)兼都，如果該節(jié)點(diǎn)存在左右孩子
else if (t.left != null && t.right != null){
//搜索到右子樹的最小節(jié)點(diǎn)，并替代當(dāng)前結(jié)點(diǎn)
t.theElement = (AnyType) findMin(t.right).theElement;
//并遞歸刪除右子樹的最小節(jié)點(diǎn)
t.right = remove(t.theElement, t.right);
}
//否則稽寒，將不為空的孩子節(jié)點(diǎn)替代掉當(dāng)前結(jié)點(diǎn)
else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
/**
* 前序遍歷
* 訪問順序?yàn)椋焊?jié)點(diǎn)->左節(jié)點(diǎn)->右節(jié)點(diǎn)
* @param node
*/
public void preOrder(BinaryNode<AnyType> node){
if (node != null){
System.out.print(node.right + " ");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 中序遍歷
* 訪問順序?yàn)椋鹤蠊?jié)點(diǎn)->根節(jié)點(diǎn)->右節(jié)點(diǎn)
* @param node
*/
public void inOrder(BinaryNode<AnyType> node){
if (node != null){
inOrder(node.left);
System.out.print(node.theElement + " ");
inOrder(node.right);
}
}
/**
* 后序遍歷
* 訪問順序?yàn)椋鹤蠊?jié)點(diǎn)->右節(jié)點(diǎn)->根節(jié)點(diǎn)
* @param node
*/
public void postOrder(BinaryNode<AnyType> node){
if (node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.theElement + " ");
}
}
}
