java数据结构之二叉搜索树(一)

package com.jimmy.impl;

import com.jimmy.BinaryTreeInterface;

//继承二叉树，泛型T必须是Comparable的
public class BinarySearchTree> extends
Binarytree {

public BinarySearchTree() {
super();
}
//用data构造根节点
public BinarySearchTree(T data) {
super();
setRoot(new BinaryNode(data));
}

//不予许用setTree，因为二叉搜索树是有序的
public void setTree(T data) {
throw new UnsupportedOperationException();
}

public void setTree(T rootData, BinaryTreeInterface left,
BinaryTreeInterface right) {
throw new UnsupportedOperationException();
}

//递归查找
public boolean bstSearch(BinarySearchTree tree, T data) {
if (tree == null)
return false;
else if (tree.getRootData().equals(data))
return true;
else if (data.compareTo(tree.getRootData()) < 0)
return bstSearch(tree.getRoot().getLeft(), data);//调用下面的方法
else
return bstSearch(tree.getRoot().getRight(), data);

}

public boolean bstSearch(BinaryNode node, T data) {
if (node == null)
return false;
else if (node.getData().equals(data))
return true;
else if (data.compareTo(node.getData()) < 0)
return bstSearch(node.getLeft(), data);
else
return bstSearch(node.getRight(), data);

}

public T getEntry(T data) {

return findEntry(this.getRoot(), data);
}

//递归查找节点，

public T findEntry(BinaryNode node, T data) {
if (node == null)
return null;
else if (node.getData().equals(data))
return node.getData();
else if (data.compareTo(node.getData()) < 0)
return findEntry(node.getLeft(), data);
else
return findEntry(node.getRight(), data);

}

public boolean contains(T data) {
return getEntry(data) != null;

}
//添加数据，从根往下迭代搜索
public T addEntry(T data) {
boolean b = false;
T result = null;
BinaryNode root = super.getRoot();
while (!b) {
if (root.getData().equals(data)) {
result = root.getData();
root.setData(data);
b = true;
} else if (data.compareTo(root.getData()) < 0) {
if (root.hasLeft())
root = root.getLeft();
else {
root.setLeft(new BinaryNode(data));
b = true;

}
} else {
if (root.hasRight())
root = root.getRight();
else {
root.setRight(new BinaryNode(data));
b = true;

}
}
}
return result;

}

//包装addEntry方法，考虑tree为null的情况
public T add(BinarySearchTree tree,T data) {
T result = null;
if(tree==null)
{
result=data;
this.setRoot(new BinaryNode(data));

}
else{
result=addEntry(data);
}
return result;
}
public static void main(String[] args) {
BinarySearchTree t=new BinarySearchTree();
//BinarySearchTree t8=new BinarySearchTree("8");
// BinarySearchTree t7=new BinarySearchTree("7");
t.add(null, "8");
t.add(t, "9");
t.add(t, "6");