完整代码在:https://github.com/nicktming/code/tree/master/data_structure
二叉查找树
每个节点都含有一个
Comparable的键并且每个节点的键都大于其左子树中的任意节点的键而小于右子树的任意节点的键.
插入
对于二叉查找树而已,新插入的节点肯定在叶子节点上,根据二叉查找的性质一直往下寻找即可,遇到比自己小的节点往左子树寻找,遇到比自己大的节点往右子树寻找,遇到相等的说明这个
key的节点已经插入过直接更新value.直接上图和代码会更清楚.
bst_1.jpeg
import java.util.LinkedList;
import java.util.Queue;
public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
public String toString() {
return "[" + key + "," + value + "]";
}
}
public void put(Key key, Value value) {
root = put(root, key, value);
}
private Node put(Node h, Key key, Value value) {
if (h == null) return new Node(key, value);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, value); //左子树
else if (cmp > 0) h.right = put(h.right, key, value); //右子树
else h.value = value;
return h;
}
public void layerTraverse() {
layerTraverse(root);
}
/*
* 横向遍历
*/
private void layerTraverse(Node h) {
if (h == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(h);
while (!queue.isEmpty()) {
Queue<Node> tmp = new LinkedList<Node>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur + " ");
if (cur != null) {
tmp.add(cur.left);
tmp.add(cur.right);
}
}
queue = tmp;
System.out.println();
}
}
public static void main(String[] args) {
BST<String, Integer> bst = new BST<String, Integer>();
bst.put("S", 0);
bst.put("E", 1);
bst.put("A", 2);
bst.put("R", 3);
bst.put("C", 4);
bst.put("H", 5);
bst.put("E", 6);
bst.put("X", 7);
bst.layerTraverse();
}
}
查找
如果理解了插入,其实查找就是非常简单了,一样的道理往左右子树寻找即可.
public Value get(Key key) {
return get(root, key);
}
public Value get(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) return get(h.left, key);
else if (cmp > 0) return get(h.right, key);
else return h.value;
}
删除
删除是二叉查找树里面相对来说稍微复杂的地方,因此作为预热,我们先看一下如何删除二叉查找树的最小键.
删除最小键
由于二叉查找树的性质,最小键肯定是最左边的键.
那删除最小键后应该怎么办呢？看图
bst_2.jpeg
直接把最小键的右子树当成最小键父亲的左孩子即可,看代码.
public void deleteMin () {
root = deleteMin(root);
}
public Node deleteMin(Node h) {
if (h == null) return null; //如果是空树 直接返回
if (h.left == null) return h.right; //如果找到最小键 直接返回最小键的右孩子
h.left = deleteMin(h.left); //当前节点的左孩子等于当前节点的左子树删除最小键返回的子树根节点
return h;
}
热身过后,看看如何删除二叉查找树里面的任意键.
有三种情况:
- 被删除的键只有右孩子
思想与删除最小值是不是很类似- 被删除的键只有左孩子
思想与删除最大值是不是很类似- 被删除的键有左右孩子
把被删除节点的右子树的最小键换到当前节点,然后删除它的右子树的最小键即可
看看第三种情况的图
bst_3.jpeg
如果真正理解了
deleteMin的操作,代码很容易写出来
private Node min (Node h) {
if (h == null) return null;
while (h.left != null) h = h.left;
return h;
}
public void delete (Key key) {
root = delete(root, key);
}
private Node delete(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = delete(h.left, key);
else if (cmp > 0) h.right = delete(h.right, key);
else {
if (h.left == null) return h.right; // 情况1
if (h.right == null) return h.left; // 情况2
/* 情况3 */
Node min_of_h_right = min(h.right); // 当前节点h右子树的最小键
Node root_of_h_right = deleteMin(h.right); // 当前节点h右子树删除最小键后的根节点
min_of_h_right.right = root_of_h_right; // 最小键的右孩子 是 h右子树删除最小键后的根节点
min_of_h_right.left = h.left; // 最小键的左孩子 是 h的左孩子
h = min_of_h_right; // 把当前节点设为最小键 然后返回给上一层
}
return h;
}
整体代码
import java.util.LinkedList;
import java.util.Queue;
import com.collection.Test;
public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
public String toString() {
return "[" + key + "," + value + "]";
}
}
public void put(Key key, Value value) {
root = put(root, key, value);
}
private Node put(Node h, Key key, Value value) {
if (h == null) return new Node(key, value);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, value); //左子树
else if (cmp > 0) h.right = put(h.right, key, value); //右子树
else h.value = value;
return h;
}
public void layerTraverse() {
layerTraverse(root);
}
/*
* 横向遍历
*/
private void layerTraverse(Node h) {
if (h == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(h);
while (!queue.isEmpty()) {
Queue<Node> tmp = new LinkedList<Node>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur + " ");
if (cur != null) {
tmp.add(cur.left);
tmp.add(cur.right);
}
}
queue = tmp;
System.out.println();
}
}
public Value get(Key key) {
return get(root, key);
}
public Value get(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) return get(h.left, key);
else if (cmp > 0) return get(h.right, key);
else return h.value;
}
public void deleteMin () {
root = deleteMin(root);
}
public Node deleteMin(Node h) {
if (h == null) return null; //如果是空树 直接返回
if (h.left == null) return h.right; //如果找到最小键 直接返回最小键的右孩子
h.left = deleteMin(h.left); //当前节点的左孩子等于当前节点的左子树删除最小键返回的子树根节点
return h;
}
private Node min (Node h) {
if (h == null) return null;
while (h.left != null) h = h.left;
return h;
}
public void delete (Key key) {
root = delete(root, key);
}
private Node delete(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = delete(h.left, key);
else if (cmp > 0) h.right = delete(h.right, key);
else {
if (h.left == null) return h.right; // 情况1
if (h.right == null) return h.left; // 情况2
/* 情况3 */
Node min_of_h_right = min(h.right); // 当前节点h右子树的最小键
Node root_of_h_right = deleteMin(h.right); // 当前节点h右子树删除最小键后的根节点
min_of_h_right.right = root_of_h_right; // 最小键的右孩子 是 h右子树删除最小键后的根节点
min_of_h_right.left = h.left; // 最小键的左孩子 是 h的左孩子
h = min_of_h_right; // 把当前节点设为最小键 然后返回给上一层
}
return h;
}
public static void main(String[] args) {
BST<String, Integer> bst = new BST<String, Integer>();
bst.put("S", 0);
bst.put("E", 1);
bst.put("A", 2);
bst.put("R", 3);
bst.put("C", 4);
bst.put("H", 5);
bst.put("E", 6);
bst.put("X", 7);
bst.put("M", 8);
bst.layerTraverse();
System.out.println(bst.get("X"));
System.out.println(bst.get("L"));
bst.delete("E");
bst.layerTraverse();
bst.deleteMin();
bst.layerTraverse();
}
}
参考:算法(第四版)
网友评论