??二叉搜索樹的概念
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹
-
若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
-
若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
-
它的左右子樹也分別為二叉搜索樹
比如以下就為一個(gè)人二叉搜索樹
int[] array ={5,3,4,1,7,8,2,6,0,9};
??二叉搜索樹功能實(shí)現(xiàn)
我們創(chuàng)建一個(gè)二叉樹如下所示，方便后續(xù)操作：
class TreeNode {
public int key ;
public TreeNode left;
public TreeNode right;
public TreeNode(int key) {
this.key = key;
}
}
public TreeNode root;//根節(jié)點(diǎn)
??查找關(guān)鍵字key
若根節(jié)點(diǎn)不為空：
- 如果根節(jié)點(diǎn)key==查找key，返回true
- 如果根節(jié)點(diǎn)key > 查找key，在其左子樹查找
- 如果根節(jié)點(diǎn)key < 查找key，在其右子樹查找
否則，返回false
??代碼實(shí)現(xiàn)：
public Boolean find(int key) {
TreeNode cur = root;
while (cur != null) {
if (key == cur.key) {
return true;
} else if (key < cur.key) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return false;
}
??插入關(guān)鍵字key
插入操作可以分為以下兩種情況：
- 如果樹為空樹，即根 == null，直接插入
- 如果樹不是空樹，按照查找邏輯確定插入位置，插入新結(jié)點(diǎn)
??代碼實(shí)現(xiàn)：
public void insert(int key) {
if(root == null) {
root = new TreeNode(key);
return;
}
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
if (key == cur.key) {
return ;
} else if (key < cur.key) {
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
TreeNode node = new TreeNode(key);
if (key < parent.key) {
parent.left = node;
} else {
parent.right = node;
}
}
??刪除關(guān)鍵字key
設(shè)待刪除結(jié)點(diǎn)為 cur, 待刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 parent，我們又可以分為四種情況
- cur.left == null
- cur 是 root，則 root = cur.right
- cur 不是 root，cur 是 parent.left，則 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，則 parent.right = cur.right
如下圖所示：
- cur.right == null
- cur 是 root，則 root = cur.left
- cur 不是 root，cur 是 parent.left，則 parent.left = cur.left
- cur 不是 root，cur 是 parent.right，則 parent.right = cur.left
與·上述情況類似，不做過多贅述
- cur.left != null && cur.right != null
需要使用替換法進(jìn)行刪除，即在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題
我們使用target來遍歷尋找右子樹中關(guān)鍵碼最小的節(jié)點(diǎn)，targetParent用來記錄target的父親節(jié)點(diǎn)
找到相應(yīng)節(jié)點(diǎn)后與待刪除的cur節(jié)點(diǎn)的值進(jìn)行替換
最后刪除target結(jié)點(diǎn)即可
- cur左右孩子均不存在
直接置為null就好
??代碼實(shí)現(xiàn)：
private void removeNode(TreeNode parent, TreeNode cur) {
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(parent.left == cur) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = cur.left;
}else if(parent.left == cur) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else {
TreeNode target = cur.right;
TreeNode targetParent = cur;
while (target.left != null) {
targetParent = target;
target = target.left;
}
cur.key = target.key;
if(target == targetParent.left) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
??搜索二叉樹性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個(gè)操作的性能。
對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：
最優(yōu)情況下，二叉搜索樹為完全二叉樹，其平均比較次數(shù)為：
最差情況下，二叉搜索樹退化為單支樹，其平均比較次數(shù)為：
文章來源：http://www.zghlxwxcb.cn/news/detail-709333.html
?總結(jié)
關(guān)于《【數(shù)據(jù)結(jié)構(gòu)】 二叉搜索樹的實(shí)現(xiàn)》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評(píng)指正，如果文章對(duì)您有幫助或者覺得作者寫的還不錯(cuò)可以點(diǎn)一下關(guān)注，點(diǎn)贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-709333.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 二叉搜索樹的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
