建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
java二叉排序樹(shù)的概念和操作-創(chuàng)新互聯(lián)
一：概念
二叉搜索樹(shù)又稱二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù):
若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹(shù)也分別為二叉搜索樹(shù)。
二：操作——查找
先和根節(jié)點(diǎn)做對(duì)比，相等返回，如果不相等，
關(guān)鍵碼key>根節(jié)點(diǎn)key,在右子樹(shù)中找(root=root.rightChild)
關(guān)鍵碼key<根節(jié)點(diǎn)key,在左子樹(shù)中找(root=root.leftChild)
否則返回false
三：操作——插入
根據(jù)二叉排序樹(shù)的性質(zhì)，左孩子比根節(jié)點(diǎn)的值小，右孩子比根節(jié)點(diǎn)的值大。關(guān)鍵碼key先于根節(jié)點(diǎn)key作比較，然后再判斷與根節(jié)點(diǎn)的左或者右作比較，滿足二叉排序樹(shù)性質(zhì)時(shí)，即為合理位置，然后插入。
四： 操作-刪除（難點(diǎn)）
設(shè)待刪除結(jié)點(diǎn)為 cur, 待刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 parent
1. 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
2. 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
3. cur.left != null && cur.right != null - 需要使用替換法進(jìn)行刪除，即在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來(lái)處理該結(jié)點(diǎn)的刪除問(wèn)題
五：實(shí)現(xiàn)
public class BinarySearchTree, V>
{
public static class Node, V>
{
K key;
V value;
Node left;
Node right;
public String toString()
{
return String.format("{%s, %s}", key, value);
}
}
private Node root = null;
public V get(K key)
{
Node parent = null;
Node cur = root;
while (cur != null)
{
parent = cur;
int r = key.compareTo(cur.key);
if (r == 0)
{
return cur.value;
}
else if (r < 0) {
cur = cur.left;
} else
{
cur = cur.right;
}
}
return null;
}
public V put(K key, V value){
if (root == null)
{ root = new Node<>();
root.key = key;
root.v
display(root);
return null;
}
Node parent = null;
Node cur = root;
while (cur != null)
{
parent = cur; int r = key.compareTo(cur.key);
if (r == 0)
{
V oldValue = cur.value;
cur.value = value;
display(root);
return oldValue;
}
else if (r < 0)
{
cur = cur.left;
}
else{
cur = cur.right;
}
}
Node node = new Node<>();
node.key = key;
node.value = value;
int r = key.compareTo(parent.key);
if (r < 0)
{ parent.left = node;
}
else { parent.right = node;
}
display(root);
return null;
}
public V remove(K key)
{ Node parent = null;
Node cur = root;
while (cur != null)
{
int r = key.compareTo(cur.key);
if (r == 0)
{
V oldValue = cur.value;
deleteNode(parent, cur);
display(root);
return oldValue; }
else if (r < 0)
{ parent = cur; cur = cur.left; }
else { parent = cur; cur = cur.right;
}
}
display(root);
return null;
}
private void deleteNode(Node parent, Node cur)
{
if (cur.left == null)
{
if (cur == root)
{
root = cur.right;
}
else if (cur == parent.left)
{ parent.left = cur.right; }
else { parent.right = cur.right; }
} else if (cur.right == null)
{
if (cur == root)
{ root = cur.left; }
else if (cur == parent.left)
{ parent.left = cur.left; }
else { parent.right = cur.left; }
} else {
// 去 cur 的右子樹(shù)中尋找最小的 key 所在的結(jié)點(diǎn) scapegoat
// 即 scapegoat.left == null 的結(jié)點(diǎn)
Node goatParent = cur;
Node scapegoat = cur.right;
while (scapegoat.left != null)
{ goatParent = scapegoat; scapegoat = cur.left; }
cur.key = scapegoat.key;
cur.value = scapegoat.value;
if (scapegoat == goatParent.left)
{
goatParent.left = scapegoat.right;
}
else { goatParent.right = scapegoat.right; }
}
}
private static ,V> void display(Node node)
{
System.out.print("前序: ");
preOrder(node); System.out.println();
System.out.print("中序: ")
inOrder(node);
System.out.println(); }
private static ,V> void preOrder(Node node)
{ if (node == null)
{ return; }
System.out.print(node + " ");
preOrder(node.left);
preOrder(node.right); }
private static ,V> void inOrder(Node node)
{ if (node == null)
{ return; }
inOrder(node.left);
System.out.print(node + " ");
inOrder(node.right); }
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree<>();
int[] keys = { 5, 3, 7, 4, 2, 6, 1, 9, 8 };
for (int key : keys)
{
tree.put(key, String.valueOf(key)); }
System.out.println("=================================="); tree.put(3, "修改過(guò)的 3"); System.out.println("=================================="); tree.remove(9);
tree.remove(1); t
ree.remove(3);
``` }
} **六：性能分析**
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹(shù)中各個(gè)操作的性能。
對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)，若每個(gè)元素查找的概率相等，則二叉搜索樹(shù)平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹(shù)的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹(shù)。
**七： 和 java 類集的關(guān)系**
TreeMap 和 TreeSet 即 java 中利用搜索樹(shù)實(shí)現(xiàn)的 Map 和 Set；另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
分享名稱：java二叉排序樹(shù)的概念和操作-創(chuàng)新互聯(lián)
標(biāo)題來(lái)源：http://www.dlmjj.cn/article/cchcih.html
