首页 > 程序开发 > 软件开发 > Java >

java数据结构之二叉搜索树

2011-12-15

package com.jimmy.impl;import com.jimmy.BinaryTreeInterface;//继承二叉树,泛型T必须是Comparable的public class BinarySearchTree<T extends Comparable<? super T>> extends Binarytree<T> { ...

package com.jimmy.impl;

import com.jimmy.BinaryTreeInterface;


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

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


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

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

//递归查找
public boolean bstSearch(BinarySearchTree<T> 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<T> 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<T> 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<T> 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<T>(data));
b = true;

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

}
}
}
return result;

}

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

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

t.inOrderTraverse();
//System.out.println(t.getHeight());
}
}

摘自 嵇康的专栏

相关文章
最新文章
热点推荐