每个节点最多两个子节点，其中左边节点的值小于该节点的值，右边节点的值大于该节点的值。为了简便起见，该二叉树装入的数据为整数，且不允许有重复的关键字值。
编程中为了简便，采用了递归算法，运算时会带来额外的开销，如果能将相应的算法替换为迭代，则更为有效。删除的算法相应复杂一些，但也可以承受。
API
add：将数加入树
remove：从树中删除指定的节点
contains：树中是否包含指定的数
ordinal：从小到大遍历打印数（测试只用）
max：查找最大值
min：查找最小值
其中Node类是辅助类，为了简单没有写标准的 get，set方法。
因为该树没有自我保持平衡的能力，因此对于随机插入的数据，效果较好，对于有局部生降序特征的插入序列，则会失去平衡，极端状况下，树退化成链表。关于平衡树请参见（Tree2-3-4 ，红黑树 ,Tree-2-3 )
Tree的main函数仅为测试之用。
class Node {
private int value;
private Node left;
private Node right;
Node(int value) {
this.value = value;
}
int value() {
return value;
}
void left(Node left) {
this.left = left;
}
void right(Node right) {
this.right = right;
}
Node left() {
return left;
}
Node right() {
return right;
}
}
class Tree {
private Node root;
void add(int value) {
Node node = new Node(value);
if(root == null) root = node;
else add(root,node);
}
private void add(Node current, Node node) {
if(node.value() < current.value()) {
if(current.left() == null) current.left(node);
else add(current.left(), node);
} else if(node.value() > current.value()) {
if(current.right() == null) current.right(node);
else add(current.right(), node);
}
}
boolean contains(int value) {
if(root == null) return false;
else return contains(root,value);
}
private boolean contains(Node current, int value) {
if(current == null) return false;
if(current.value() == value) return true;
if(value < current.value()) return contains(current.left(),value);
else return contains(current.right(),value);
}
void remove(int value) {
remove(null,root,value);
}
private void remove(Node parent, Node current, int value) {
if(current == null) return;
if(current.value() == value) {
Node node;
if(current.left() == null && current.right() == null) node = null;
else if (current.left() != null && current.right() == null) node = current.left();
else if (current.right() != null && current.left() == null) node = current.right();
else {
node = removeMin(current,current.right());
node.left(current.left());
node.right(current.right());
}
if(parent == null) root = node;
else if(parent.left() == current) parent.left(node);
else parent.right(node);
} else if(value < current.value()) remove(current,current.left(),value);
else remove(current,current.right(),value);
}
private Node removeMin(Node parent, Node current) {
if(current.left() != null) return removeMin(current,current.left());
else {
if(parent.left() == current) parent.left(current.right());
else parent.right(current.right());
return current;
}
}
int max() {
if(root == null) return -1;
else return max(root);
}
private int max(Node current) {
if(current.right() == null) return current.value();
else return max(current.right());
}
int min() {
if(root == null) return -1;
else return min(root);
}
private int min(Node current) {
if(current.left() == null) return current.value();
else return min(current.left());
}
void ordinal() {
if (root == null) return;
else ordinal(root);
}
void ordinal(Node current) {
if(current.left() != null) ordinal(current.left());
System.out.println(current.value() + ” “);
if(current.right() != null) ordinal(current.right());
}
public static void main(String[] args) {
Tree t = new Tree();
t.add(50);
t.add(6);
t.add(29);
t.add(100);
t.add(34);
t.add(45);
t.add(4);
t.add(68);
t.ordinal();
System.out.println(t.contains(34));
assert t.contains(34);
assert t.contains(6);
assert !t.contains(110);
assert t.max() == 100;
assert t.min() == 4;
t.remove(50);
t.remove(45);
t.remove(6);
t.ordinal();
}
}
Tags: Algorithm
Posted in Algorithm
