數(shù)據(jù)結(jié)構(gòu)（一）數(shù)組實(shí)現(xiàn)一個(gè)簡單的ArrayList
數(shù)據(jù)結(jié)構(gòu)（二）鏈表實(shí)現(xiàn)LinkedList
數(shù)據(jù)結(jié)構(gòu)（三）用兩種方式簡單實(shí)現(xiàn)棧
數(shù)據(jù)結(jié)構(gòu)（四）棧和隊(duì)列的簡單應(yīng)用
數(shù)據(jù)結(jié)構(gòu)（五）用兩種方式簡單實(shí)現(xiàn)隊(duì)列
數(shù)據(jù)結(jié)構(gòu)（六）二分搜索樹(Binary Search Tree)（上）
數(shù)據(jù)結(jié)構(gòu)（六）二分搜索樹(Binary Search Tree)（下）
數(shù)據(jù)結(jié)構(gòu)（七）兩種方式實(shí)現(xiàn)set
數(shù)據(jù)結(jié)構(gòu)（八）兩種方式實(shí)現(xiàn)map
數(shù)據(jù)結(jié)構(gòu)（九）set解決LeetCode349號問題
定義
簡單來說二分搜索樹是具有以下行的二叉樹
- 1.若任意節(jié)點(diǎn)的左子樹不空东羹，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
- 2.若任意節(jié)點(diǎn)的右子樹不空案疲，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值祝沸；
- 3.任意節(jié)點(diǎn)的左矮烹、右子樹也分別為二叉查找樹；
-
4.沒有鍵值相等的節(jié)點(diǎn)罩锐。
二分搜索樹
二分搜索樹是比較重要的一種數(shù)據(jù)結(jié)構(gòu)奉狈，應(yīng)用也比較廣泛，希望大家多學(xué)習(xí)涩惑，多理解仁期，多應(yīng)用。
實(shí)現(xiàn)
下邊我簡單實(shí)現(xiàn)了一下二分搜索樹竭恬，話不多說跛蛋，直接上源碼。
import java.util.Stack;
public class BST<E extends Comparable<E>> {
private class Node {
public E e;
public Node left, right;
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BST() {
root = null;
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// 向二分搜索樹中添加新的元素e
public void add(E e) {
root = add(root, e);
}
// 向以node為根的二分搜索樹中插入元素e痊硕，遞歸算法
// 返回插入新節(jié)點(diǎn)后二分搜索樹的根
private Node add(Node node, E e) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0)
node.left = add(node.left, e);
else if (e.compareTo(node.e) > 0)
node.right = add(node.right, e);
return node;
}
// 看二分搜索樹中是否包含元素e
public boolean contains(E e) {
return contains(root, e);
}
// 看以node為根的二分搜索樹中是否包含元素e, 遞歸算法
private boolean contains(Node node, E e) {
if (node == null)
return false;
if (e.compareTo(node.e) == 0)
return true;
else if (e.compareTo(node.e) < 0)
return contains(node.left, e);
else // e.compareTo(node.e) > 0
return contains(node.right, e);
}
// 二分搜索樹的前序遍歷
public void preOrder() {
preOrder(root);
}
// 前序遍歷以node為根的二分搜索樹, 遞歸算法
private void preOrder(Node node) {
if (node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
// 二分搜索樹的中序遍歷
public void inOrder() {
inOrder(root);
}
// 中序遍歷以node為根的二分搜索樹, 遞歸算法
private void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
// 二分搜索樹的后序遍歷
public void postOrder() {
postOrder(root);
}
// 后序遍歷以node為根的二分搜索樹, 遞歸算法
private void postOrder(Node node) {
if (node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
private void preOrderNR() {
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
if (root.left != null)
stack.push(root.left);
if (root.right != null)
stack.push(root.right);
}
}
//效果和minimum是一樣的這個(gè)是非遞歸的實(shí)現(xiàn)赊级，那個(gè)是遞歸的實(shí)現(xiàn)。
public E minNum() {
if (size == 0) {
throw new IllegalArgumentException("bst is empty");
}
Node node = root;
while (node.left != null) {
node = node.left;
}
return node.e;
}
/**
* 遞歸的方式實(shí)現(xiàn)找到二分搜索樹的最小值寿桨。
*
* @return 返回二分搜索樹最小節(jié)點(diǎn)的值
*/
public E mininum() {
if (size == 0) {
throw new IllegalArgumentException("bst is empty");
}
return mininum(root).e;
}
/**
* 以node為節(jié)點(diǎn)的二分搜索樹的最小節(jié)點(diǎn)此衅。
*
* @param node
* @return
*/
private Node mininum(Node node) {
if (node.left == null)
return node;
return mininum(node.left);
}
//從二分搜索樹種刪除最小值所在的接點(diǎn)强戴，并返回最小接點(diǎn)的值。
public E removeMin() {
E ret = mininum();
root = removeMin(root);
return ret;
}
//刪除以node為根的二分搜索樹的最小節(jié)點(diǎn)
//返回刪除節(jié)點(diǎn)后新的二分搜索樹的根
private Node removeMin(Node node) {
if (node.left == null) {
Node right = node.right;
node.right = null;
size--;
return right;
}
node.left = removeMin(node.left);
return node;
}
public E maxNum(){
if (size == 0) {
throw new IllegalArgumentException("bst is empty");
}
Node node = root;
while (node.right != null) {
node = node.right;
}
return node.e;
}
public E maxmum() {
if (size == 0) {
throw new IllegalArgumentException("bst is empty");
}
return maxmum(root).e;
}
private Node maxmum(Node node) {
if (node.right == null)
return node;
return maxmum(node.right);
}
/**
* 刪除二分搜索樹最大值的節(jié)點(diǎn)挡鞍。
*
* @return
*/
public E removeMax() {
E ret = maxmum();
removeMax(root);
return ret;
}
private Node removeMax(Node node) {
if (node.left == null) {
Node right = node.right;
node.right = null;
size--;
return right;
}
node.left = removeMax(node);
return node;
}
/**
* 從二分搜索樹中刪除元素為e的節(jié)點(diǎn)骑歹。
*
* @param e
*/
public void remove(E e) {
root = remove(root, e);
}
//刪除以node為根的二分搜索樹中元素為e的節(jié)點(diǎn)，遞歸算法
//返回刪除節(jié)點(diǎn)后二分搜索樹的根
private Node remove(Node node, E e) {
if (node == null)
return null;
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {// e == node.e
if (node.left == null) {
Node right = node.right;
node. right = null;
size--;
return right;
}
if (node.right == null) {
Node left = node.left;
node.left = null;
size--;
return left;
}
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateString(root, 0, res);
return res.toString();
}
// 生成以node為根節(jié)點(diǎn)墨微，深度為depth的描述二叉樹的字符串
private void generateString(Node node, int depth, StringBuilder res) {
if (node == null) {
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + node.e + "\n");
generateString(node.left, depth + 1, res);
generateString(node.right, depth + 1, res);
}
private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; I++)
res.append("--");
return res.toString();
}
}
解析
首先大家可以看到我們的泛型與之前的不太一樣道媚，這里必須是可以比較的泛型，因?yàn)槎炙阉鳂涫前凑沾笮砼帕械那滔兀瑑?nèi)部有序最域。下邊我們一一來介紹他的方法。
Binary Search Tree
- add
這里我們用的是遞歸的實(shí)現(xiàn)锈麸，所以我們先來看一下結(jié)束的條件镀脂，就是當(dāng)前的節(jié)點(diǎn)是空的時(shí)候，極限情況就是這個(gè)二分搜索樹是空的忘伞，那么插入一個(gè)元素薄翅，只需要把這個(gè)節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)上，并且給size加一就可以氓奈，下邊就是就是遞歸的具體條件了翘魄，如果他比當(dāng)前節(jié)點(diǎn)小的話，那么那么就去他的左子樹去處理舀奶，如果比當(dāng)前節(jié)點(diǎn)大的話就去他的右子樹去處理暑竟，因?yàn)楫?dāng)前出是不存在鍵值相同的節(jié)點(diǎn)，所以就這樣去遍歷直到找到合適的位置育勺，這樣就完成了二分搜索樹的插入工作但荤。如上邊的圖，我們插入11怀大，比根節(jié)點(diǎn)小雏逾，去左子樹比較防泵，比18這個(gè)節(jié)點(diǎn)小树叽，再去他的左子樹比較载矿，比10大馏鹤，去右子樹蛮穿，10這個(gè)節(jié)點(diǎn)右葉子節(jié)點(diǎn)是空的蓉坎，所以直接插入到那個(gè)位置就可以了黎烈。 - contains
這里我們也是用的遞歸的方法實(shí)現(xiàn)的垒手，同樣的道理我們也是找一下結(jié)束的條件蒜焊，當(dāng)前的節(jié)點(diǎn)為空的時(shí)候說明走到結(jié)束了也沒有找到相同的值的節(jié)點(diǎn)，所以返回false科贬，下邊就是判斷如果當(dāng)前節(jié)點(diǎn)與傳入的元素相同則返回true泳梆；如果比當(dāng)前節(jié)點(diǎn)的值小則去左子樹去遍歷鳖悠；如果比當(dāng)前節(jié)點(diǎn)值大則去右子樹遍歷。這樣查找的方法也結(jié)束了优妙。 - miniNum
查找最小數(shù)乘综，因?yàn)槎炙阉鳂涞奶攸c(diǎn)就是左子樹肯定比當(dāng)前節(jié)點(diǎn)小，所以找最小值只需要找左下角的葉子節(jié)點(diǎn)就可以了套硼，所以我們只需要遍歷左子樹直到左子樹的左葉子節(jié)點(diǎn)是空的卡辰，就放回這個(gè)節(jié)點(diǎn)就可以了。上邊的圖可以看到邪意，最左邊的是最小值九妈，就是10。 - maxmum
這個(gè)方法跟上邊的方法思想是一樣的所以這里不做過多的解釋了雾鬼。 - minNum
這里是用循環(huán)的方式實(shí)現(xiàn)的刪除最小節(jié)點(diǎn)的元素萌朱，就是一直看左子樹，知道左子樹為空的時(shí)候就是他的最小值策菜。 -
maxNum
這個(gè)方法和上邊的方法是一樣的嚷兔，我們這里也不做過多的解釋了。
remove.png - removeMin
這里用遞歸的方式去尋找的做入，所以要找結(jié)束條件冒晰，就是到最小值了，所以這個(gè)節(jié)點(diǎn)左葉子節(jié)點(diǎn)為空竟块，然后我們獲取右葉子節(jié)點(diǎn)壶运，保存的臨時(shí)變量里，然后把這個(gè)節(jié)點(diǎn)的右葉子節(jié)點(diǎn)置為null浪秘，size減一蒋情，返回右葉子節(jié)點(diǎn)，如果不是空那么就繼續(xù)找這個(gè)節(jié)點(diǎn)的左子樹耸携。 - removeMax
這個(gè)方法的思想和上邊的是相同的棵癣。
今天我們先分析這些方法，下次我們分析剩下的那幾個(gè)方法夺衍。希望大家多多關(guān)注與支持狈谊。
