示例
BST示例.png
BST.java源代码
package com.reign.gcld.chapter12;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 算法导论第12章的二叉搜索树实现
*/
public class BST {
//入口：根节点
protected Node root;
//辅助节点:记录父节点引用
protected Node hot;
public static void main(String[] args) {
BST tree = new BST();
//插入测试
Entry entry15 = new Entry(15,15);
tree.insert(entry15);
Entry entry6 = new Entry(6,6);
tree.insert(entry6);
Entry entry18 = new Entry(18,18);
tree.insert(entry18);
Entry entry3 = new Entry(3,3);
tree.insert(entry3);
Entry entry7 = new Entry(7,7);
tree.insert(entry7);
Entry entry17 = new Entry(17,17);
tree.insert(entry17);
Entry entry20 = new Entry(20, 20);
tree.insert(entry20);
Entry entry2 = new Entry(2,2);
tree.insert(entry2);
Entry entry4 = new Entry(4,4);
tree.insert(entry4);
Entry entry13 = new Entry(13,13);
tree.insert(entry13);
Entry entry9 = new Entry(9,9);
tree.insert(entry9);
//中序遍历
tree.inOrder(entry15);
// //最大值
// tree.getMax(tree.root);
// //最小值
// tree.getMin(tree.root);
// //继任者
// System.out.println(tree.getSuccessor(tree.root));
// Node node9 = tree.search(entry9);
// System.out.println(node9);
//删除测试
// 见297页情形a
//tree.delete(entry9);
//见297页情形b
tree.delete(entry13);
//见297页情形c
//tree.delete(entry18);
//见297页情形d
//tree.delete(entry15);
tree.inOrder(tree.root);
}
protected Iterable<Node> inOrder(Entry e) {
Node x = search(e);
return inOrder(x);
}
protected Node getSuccessor(Node x) {
if (x.getRight() != null) {
return getMin(x.getRight());
}
Node y = x.getParent();
Node z = x;
while (y != null && z.getEntry().getKey().compareTo(y.getRight().getEntry().getKey()) == 0) {
z = y;
y = y.getParent();
}
return y;
}
protected Node getMax(Entry e) {
Node x = search(e);
if (x != null) {
return getMax(x);
}
return x;
}
private Node getMax(Node x) {
Node y = x;
while (y.getRight() != null) {
y = y.getRight();
}
return y;
}
protected void delete(Entry e) {
Node x = search(e);
delete(x);
}
protected void delete(Node z) {
Node x = z;
if (x.getLeft() == null) {
//情形a
transplant(x,x.getRight());
}else if (x.getRight() == null) {
//情形b
transplant(x, x.getLeft());
}else {
Node y = getMin(x.getRight());
Node p = y.getParent();
if ((p.getEntry().getKey().compareTo(x.getEntry().getKey())) != 0) {
//节点y不是待删除节点的右孩子
transplant(y, y.getRight());
y.setRight(x.getRight());
y.getRight().setParent(y);
}
transplant(x, y);
y.setLeft(x.getLeft());
y.getLeft().setParent(y);
}
}
/**
* 使用节点v替换节点u
* 主要功能：修改节点u的父节点及其左右孩子节点的指向
* @param u
* @param v
*/
private void transplant(Node u, Node v) {
Node y = u.getParent();
if (y == null) {
//节点u是根节点
this.root = v;
}else if (y.getLeft() != null && y.getLeft().getEntry().getKey().compareTo(u.getEntry().getKey())==0) {
//节点u是左孩子
y.setLeft(v);
}else if (y.getRight() != null && y.getRight().getEntry().getKey().compareTo(u.getEntry().getKey())==0){
//节点u是右孩子
y.setRight(v);
}
//修改节点v的父节点
if (v != null) {
v.setParent(y);
this.hot = y;
updateHeightAbove(y);
}
}
private Node getMin(Node x) {
Node y = x;
while (y.getLeft() != null) {
y = y.getLeft();
}
return y;
}
protected Iterable<Node> inOrder(Node x) {
List<Node> nodes = new ArrayList<>();
Stack<Node> helper = new Stack<>();
Node y = x;
while (true) {
if (y != null) {
helper.push(y);
y = y.getLeft();
}else if (!helper.isEmpty()) {
y = helper.pop();
nodes.add(y);
y = y.getRight();
}else {
break;
}
}
StringBuilder sb = new StringBuilder();
for (Node node : nodes) {
sb.append(node.getEntry().getKey()).append(" ");
}
System.out.println(sb);
return nodes;
}
protected Node search(Entry e) {
this.hot = null;
return search(this.root, e);
}
private Node search(Node x, Entry e) {
if (x == null || x.getEntry().getKey().compareTo(e.getKey()) == 0) {
return x;
}
this.hot = x;
if (e.getKey().compareTo(x.getEntry().getKey()) < 0) {
return search(x.getLeft(), e);
}else {
return search(x.getRight(), e);
}
}
public Node insert(Entry e) {
Node w = search(e);
if (w != null) {
return w;
}
Node y = null;
Node x = this.root;
while (x != null) {
y = x;
if (e.getKey().compareTo(x.getEntry().getKey()) < 0) {
x = x.getLeft();
}else {
x= x.getRight();
}
}
this.hot = y;
Node z = new Node();
z.setParent(y);
z.setEntry(e);
if (y == null) {
this.root = z;
}else if (z.getEntry().getKey().compareTo(y.getEntry().getKey()) < 0) {
y.setLeft(z);
}else {
y.setRight(z);
}
updateHeightAbove(z);
return z;
}
protected void updateHeightAbove(Node x) {
Node y = x;
while (y != null) {
updateHeight(y);
y = y.getParent();
}
}
protected void updateHeight(Node x) {
int height = 1 + Math.max(getStature(x.getLeft()), getStature(x.getRight()));
x.setHeight(height);
}
protected int getStature(Node x) {
int height = -1;
if (x != null) {
height = x.getHeight();
}
return height;
}
protected boolean isLChild(Node x) {
boolean result = false;
if (!isRoot(x) && x.getEntry().getKey().compareTo(x.getParent().getEntry().getKey()) < 0) {
result = true;
}
return result;
}
private boolean isRoot(Node x) {
boolean result = false;
if (x!=null && x.getParent() == null) {
result = true;
}
return result;
}
protected boolean isRChild(Node x) {
boolean result = false;
if (!isRoot(x) && x.getEntry().getKey().compareTo(x.getParent().getEntry().getKey()) > 0) {
result = true;
}
return result;
}
}
BST删除示例.png
