二叉排序樹(shù)又稱(chēng)為二叉查找樹(shù)荆永，具備以下性質(zhì)：
①若它的左子樹(shù)不空废亭，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
②若它的右子樹(shù)不空具钥，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值豆村；
③它的左、右子樹(shù)也分別為二叉排序樹(shù)骂删；
二叉排序樹(shù)使用鏈?zhǔn)酱鎯?chǔ)掌动，插入和刪除的效率較好，又可以較高效的實(shí)現(xiàn)查找某個(gè)元素的功能桃漾。
中序遍歷二叉排序樹(shù)時(shí)能夠得到一個(gè)有序序列坏匪。
測(cè)試二叉排序樹(shù).png
二叉排序樹(shù)結(jié)點(diǎn)類(lèi)
/**
* @author Shaw
* @version 創(chuàng)建時(shí)間：2018年12月9日 下午3:33:43
* 類(lèi)說(shuō)明:二叉排序樹(shù)結(jié)點(diǎn)類(lèi)
*/
class BiTNode {
//數(shù)據(jù)域
private int data;
//左右結(jié)點(diǎn)域
private BiTNode lchild, rchild;
public BiTNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BiTNode getLchild() {
return lchild;
}
public void setLchild(BiTNode lchild) {
this.lchild = lchild;
}
public BiTNode getRchild() {
return rchild;
}
public void setRchild(BiTNode rchild) {
this.rchild = rchild;
}
@Override
public String toString() {
return "BiTNode [data=" + data + ", lchild=" + lchild + ", rchild=" + rchild + "]";
}
}
二叉排序樹(shù)核心類(lèi)
二叉排序樹(shù)的建立就是不斷執(zhí)行插入操作的過(guò)程。
二叉排序樹(shù)的刪除分為三種情況討論：
①當(dāng)刪除結(jié)點(diǎn)僅有左子樹(shù)時(shí)撬统，只需將此結(jié)點(diǎn)的左孩子替換它自己适滓，就相當(dāng)于刪除了該結(jié)點(diǎn)。
②當(dāng)刪除結(jié)點(diǎn)僅有右子樹(shù)時(shí)恋追，只需將此結(jié)點(diǎn)的右孩子替換它自己即可凭迹。
③當(dāng)刪除結(jié)點(diǎn)左右子樹(shù)都不為空時(shí)，可以在左子樹(shù)中找到小于但最接近該值的結(jié)點(diǎn)替換它苦囱，即找到中序遍歷中的前驅(qū)嗅绸；也可以在右子樹(shù)中找到大于但最接近該值的結(jié)點(diǎn)替換，即中序遍歷中的后驅(qū)撕彤。
本例中采用的是前驅(qū)替換鱼鸠。
/**
*
* @author Shaw
* @version 創(chuàng)建時(shí)間：2018年12月9日 下午3:34:11
* 類(lèi)說(shuō)明:二叉排序樹(shù)類(lèi)
*/
class BinarySortTree {
public BiTNode root;
public BinarySortTree() {
root = null;
}
// 中序遍歷
public void InOrderTraverse(BiTNode node) {
if (node == null) {
return;
}
InOrderTraverse(node.getLchild());
System.out.print(node.getData() + " ");
InOrderTraverse(node.getRchild());
}
// 二叉排序樹(shù)查找
public BiTNode search_BST(int key) {
BiTNode current = root;
while (current != null) {
// 查找成功返回對(duì)應(yīng)結(jié)點(diǎn)
if (key == current.getData()) {
return current;
} else if (key < current.getData()) {
current = current.getLchild();
} else {
current = current.getRchild();
}
}
return null;
}
// 二叉排序樹(shù)插入
public void insert_BST(int key) {
// 空樹(shù)情況
if (root == null) {
root = new BiTNode(key);
return;
}
// 結(jié)點(diǎn)已在樹(shù)中存在時(shí)
if (search_BST(key) != null) {
return;
}
BiTNode node = new BiTNode(key);
BiTNode current = root;
BiTNode parent = null;
// 循環(huán)獲取待插入結(jié)點(diǎn)的父結(jié)點(diǎn)位置
while (current != null) {
parent = current;
if (key < current.getData()) {
current = current.getLchild();
} else if (key > current.getData()) {
current = current.getRchild();
} else {
break;
}
}
// 判斷插入的是左結(jié)點(diǎn)還是右結(jié)點(diǎn)
if (key < parent.getData()) {
parent.setLchild(node);
} else {
parent.setRchild(node);
}
}
// 二叉排序樹(shù)刪除
public boolean delete_BST(int key) {
// current結(jié)點(diǎn)指向待刪除的結(jié)點(diǎn)
BiTNode current = root;
// parent結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的父節(jié)點(diǎn)
BiTNode parent = null;
// 通過(guò)循環(huán)查找確定current和parent結(jié)點(diǎn)
while (current != null) {
// 待刪除的結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值猛拴，查找左子樹(shù)
if (key < current.getData()) {
parent = current;
current = current.getLchild();
}
// 待刪除的結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，查找右子樹(shù)
else if (key > current.getData()) {
parent = current;
current = current.getRchild();
}
// 查找到結(jié)點(diǎn)后退出
else {
break;
}
}
// 空樹(shù)的情況
if (current == null) {
return false;
}
// 右子樹(shù)為空的情況
// 待刪除結(jié)點(diǎn)的左結(jié)點(diǎn)"繼承"該結(jié)點(diǎn)的位置
if (current.getRchild() == null) {
// 不是空樹(shù)的情況
if (parent != null) {
// 待刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左結(jié)點(diǎn)
if (parent.getLchild() == current) {
// 將待刪除結(jié)點(diǎn)的左結(jié)點(diǎn)設(shè)置為父結(jié)點(diǎn)的左結(jié)點(diǎn)
parent.setLchild(current.getLchild());
} else {
// 待刪除的結(jié)點(diǎn)是父結(jié)點(diǎn)的右結(jié)點(diǎn)時(shí)將該結(jié)點(diǎn)的左結(jié)點(diǎn)設(shè)置為父結(jié)點(diǎn)的右結(jié)點(diǎn)
parent.setRchild(current.getLchild());
}
} else {
// 空樹(shù)時(shí)將左結(jié)點(diǎn)賦值給根結(jié)點(diǎn)
root = current.getLchild();
}
}
// 左子樹(shù)為空的情況
// 待刪除結(jié)點(diǎn)的右結(jié)點(diǎn)"繼承"該結(jié)點(diǎn)的位置
else if (current.getLchild() == null) {
if (parent != null) {
if (parent.getLchild() == current) {
parent.setLchild(current.getLchild());
} else {
parent.setRchild(current.getRchild());
}
} else {
root = current.getRchild();
}
}
// 左右子樹(shù)均不為空的情況
// 在二叉排序樹(shù)中序中選擇該結(jié)點(diǎn)的前驅(qū)或者后繼替換該結(jié)點(diǎn)蚀狰，
// 也就是選擇比該結(jié)點(diǎn)小或者比它大的最接近的兩個(gè)數(shù)中的一個(gè)愉昆，本例選擇的是比該結(jié)點(diǎn)小的結(jié)點(diǎn)
else {
// 用于替換的結(jié)點(diǎn)
BiTNode replaceNode = current.getLchild();
// 替換結(jié)點(diǎn)的父節(jié)點(diǎn),初始化為待刪除的結(jié)點(diǎn)
BiTNode replaceParentNode = current;
// 用于替換的結(jié)點(diǎn)存在右子結(jié)點(diǎn)時(shí)，因?yàn)橛医Y(jié)點(diǎn)大于根結(jié)點(diǎn)的值麻蹋，所以右子結(jié)點(diǎn)更接近被刪除的結(jié)點(diǎn)
while (replaceNode.getRchild() != null) {
replaceParentNode = replaceNode;
replaceNode = replaceNode.getRchild();
}
// 替換結(jié)點(diǎn)不存在右子結(jié)點(diǎn)時(shí)
// 相等時(shí)由于使用的是前驅(qū)值代替跛溉，所以需要補(bǔ)充的是左子結(jié)點(diǎn)的值
if (replaceParentNode == current) {
replaceParentNode.setLchild(replaceNode.getLchild());
}
// replaceParentNode與current不相等時(shí)
// replaceNode肯定是大于replaceParentNode的值的,所以需要補(bǔ)充的是右子結(jié)點(diǎn)的值
else {
replaceParentNode.setRchild(replaceNode.getLchild());
}
// 替換對(duì)應(yīng)的值
current.setData(replaceNode.getData());
}
return true;
}
}
測(cè)試程序：
public class BinarySortTreeMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 36, 39, 42, 62 };
BinarySortTree binarySortTree = new BinarySortTree();
System.out.println("原始序列：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
binarySortTree.insert_BST(a[i]);
}
System.out.println("\n二叉排序后的序列：");
binarySortTree.InOrderTraverse(binarySortTree.root);
System.out.print("\n查找37：");
BiTNode node = binarySortTree.search_BST(37);
if (node != null) {
System.out.println(true);
} else {
System.out.println(false);
}
System.out.print("查找22：");
node = binarySortTree.search_BST(22);
if (node != null) {
System.out.println(true);
} else {
System.out.println(false);
}
System.out.print("刪除47：");
System.out.println(binarySortTree.delete_BST(47));
System.out.println("刪除47后的序列：");
binarySortTree.InOrderTraverse(binarySortTree.root);
System.out.print("\n刪除22：");
System.out.println(binarySortTree.delete_BST(22));
}
}
測(cè)試結(jié)果：
二叉排序樹(shù)測(cè)試結(jié)果圖.png
總結(jié)
二叉排序樹(shù)以鏈接方式存儲(chǔ)，保持了鏈接存儲(chǔ)結(jié)構(gòu)在執(zhí)行插入或刪除操作時(shí)不用移動(dòng)元素的優(yōu)點(diǎn)扮授，插入刪除的時(shí)間性能較好芳室。對(duì)于二叉排序樹(shù)的查找，比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹(shù)的層數(shù)刹勃。最少為1次堪侯，最多也不會(huì)超過(guò)樹(shù)的深度。
缺點(diǎn)：當(dāng)本例中的數(shù)組是{35,36,37,39,42,47,51,58,73,88,93,99}時(shí)深夯，即數(shù)組元素從小到大有序時(shí)抖格，此時(shí)的二叉排序樹(shù)如圖所示是一棵右斜樹(shù)。當(dāng)同樣查找99結(jié)點(diǎn)時(shí)咕晋，測(cè)試?yán)有枰?次比較雹拄，本例卻需要12次比較，二者差異很大掌呜。也就是說(shuō)滓玖，二叉排序樹(shù)的查找性能主要取決于二叉排序樹(shù)的形狀，但本例中的二叉排序樹(shù)的形狀是由給定數(shù)組來(lái)構(gòu)造的质蕉，即形狀是不確定的势篡。為此，我們需要構(gòu)造平衡二叉樹(shù)來(lái)解決這個(gè)問(wèn)題模暗。
右斜樹(shù).png
