一棵二叉查找樹(BST)是一顆二叉樹，其中每個節點都含有一個Comparable的鍵且每個節點的鍵(以及相關的值)都大于其左子樹中的任意節點的鍵而小于右子樹的任意結點的鍵。

數據表示

和鏈表一樣，我們嵌套定義了一個私有類來表示二叉查找樹上的一個節點。每個節點都含有一個鍵、一個值、一條左鏈接、一條右鏈接和一個節點計數器

查找節點

思路：

A、如果二叉查找樹為空，查找失敗(search miss)，返回null；

B、如果根節點的鍵等于要查找的鍵，返回根節點的值(search hit)。

C、否則，繼續在相應的子樹中查找。如果要查找的鍵小于根節點的鍵，在左子樹中查找；如果要查找的鍵大于根節點的鍵，在右子樹中查找。

D、重復ABC步驟，直至search miss或者search hit。

插入節點

思路：

A、如果二叉查找樹是空的，生成一個新節點，并返回該節點，相當于插入新節點后的二叉樹根節點。

B、如果根節點鍵和要插入的鍵相等，更新根節點的值。

C、如果要插入的鍵小于根節點的鍵，在左子樹插入，并將根節點的左鏈接指向插入后的左子樹。

D、如果要插入的鍵小于根節點的鍵，在右子樹插入，并將根節點的右鏈接指向插入后的右子樹。

E、更新根節點的size，并返回根節點，作為插入新節點后的二叉樹根節點。

F、重復ABCD，直至插入或者更新成功。

刪除節點

刪除節點是二叉搜索樹中，最復雜的一種操作，但是也不是特別難，我們分類討論：

要刪除節點有零個孩子，即葉子節點

如圖所示，只需要將parent.left設置為null，然后Java垃圾自動回收機制會自動刪除current節點。

2.要刪除節點有一個孩子

如圖所示，只需要將parent.left設置為curren.right即可。

3.要刪除節點有兩個孩子

這種情況比較復雜，首先我們引入后繼節點的概念，如果將一棵二叉樹按照中序周游的方式輸出，則任一節點的下一個節點就是該節點的后繼節點。例如：上圖中24的后繼節點為26，64的后繼節點為70.找到后繼節點以后，問題就變得簡單了，因為但刪除節點有右子樹，所以它的后繼節點就是右子樹中的最小節點。

分為兩種情況：

• 后繼節點為待刪除節點的右子，只需要將curren用successor替換即可，注意處理好current.left和successor.right.

注意：這種情況下，successor一定沒有左孩子，一但它有左孩子，哪它必然不是current的后繼節點。

• 后繼節點為待刪除結點的右孩子的左子樹，這種情況稍微復雜點，請看動態圖片演示。

刪除節點分4步

(1)將只想即將被刪除的的節點鏈接保存為t

(2)將x指向它的后繼節點min(t.right)

(3)將x的右鏈接指向deleteMin(x.right)

(4)將x的左鏈接設為t.left

實現

package find;public class BST, Value> { private Node root; public Value get(Key key) { return get(root, key); } //插入操作 public void put(Key key, Value val) { root = put(root, key, val); } //查詢 private Value get(Node x, Key key) { if (x == null) { return null; } int cmp = key.compareTo(x.key); if (cmp < 0) { return get(x.left, key); } else if (cmp > 0) { return get(x.right, key); } else { return x.val; } } private Node put(Node x, Key key, Value val) { if (x == null) { return new Node(key, val, 1); } int cmp = key.compareTo(x.key); if (cmp < 0) { x.left = put(x.left, key, val); } else if (cmp > 0) { x.right = put(x.right, key, val); } else { x.val = val; } x.N = size(x.left) + size(x.right) + 1; return x; } public int size() { return size(root); } private int size(Node x) { if (x == null) { return 0; } else { return x.N; } } public Key min() { return min(root).key; } private Node min(Node x) { if (x.left == null) { return x; } return min(x.left); } public Key floor(Key key) { Node x = floor(root, key); if (x == null) { return null; } return x.key; } private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) { return x; } else if (cmp < 0) { return floor(x.left, key); } Node t = floor(x.right, key); if (t != null) { return t; } else { return x; } } public void deleteMin() { root = deleteMin(root); } private Node deleteMin(Node x) { if (x == null) { return x.right; } x.left = deleteMin(x.left); x.N = size(x.left) + size(x.right) + 1; return x; } public void delete(Key key) { root = delete(root, key); } private Node delete(Node x, Key key) { if (x == null) { return null; } int cmp = key.compareTo(key); if (cmp < 0) { x.left = delete(x.left, key); } else if (cmp > 0) { x.right = delete(x.right, key); } else { if (x.right == null) { return x.left; } else if (x.left == null) { return x.right; } Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; } private class Node { private Key key; private Value val; private Node left, right; private int N; public Node(Key key, Value val, int N) { this.key = key; this.val = val; this.N = N; } }}

總結

以上是生活随笔為你收集整理的xdocument查找节点值_二叉查找树（java）的全部內容，希望文章能夠幫你解決所遇到的問題。

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