首页 / JAVA / 基于JAVA泛型机制实现二叉查找树
基于JAVA泛型机制实现二叉查找树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了基于JAVA泛型机制实现二叉查找树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5053字，纯文字阅读大概需要8分钟。
内容图文
基于JAVA泛型机制实现二叉查找树
参考《数据结构与算法分析——Java语言描述》
-
二叉查找树：对于树中的每个节点T，它的左子树中所有项的值都小于节点T中的值，而它的右子树中所有项的值都大于节点T中的值。
-
我们通过提供
Comparable接口来表示二叉树所有项可以排序的性质，因为使用这个接口的话，二叉树所有的项都可以使用comparableTo方法进行比较。 -
值得注意的是，树的定义以及其各种方法的定义，都会用到递归。
import java.util.Random;
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
/**
* 静态嵌套类
* @param <AnyType>
*/
private static class BinaryNode<AnyType>{
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
BinaryNode(AnyType theElement){
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode<AnyType> theLeft, BinaryNode<AnyType> theRight) {
element = theElement;
left = theLeft;
right = theRight;
}
}
/**
* 树根
*/
private BinaryNode<AnyType> root;
public BinarySearchTree(){
root = null;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root==null;
}
public boolean contains(AnyType x){
return contains(x,root);
}
public AnyType findMin(){
return findMin(root).element;
}
public AnyType findMax(){
return findMax(root).element;
}
public void insert(AnyType x){
root = insert(x, root);
}
public void remove(AnyType x){
root = remove(x, root);
}
public void printTree(){
if(isEmpty()){
System.out.println("Empty Tree");
}
else {
printTree(root);
}
}
/**
* 递归判断树里是否存在x元素
* @param x 待寻找元素
* @param t 节点
* @return boolean
*/
private boolean contains(AnyType x, BinaryNode<AnyType> t) {
if(t == null){
return false;
}
int comparableResult = x.compareTo(t.element);
// 如果寻找元素更小就进入左子树
if(comparableResult < 0){
return contains(t.left.element);
}
// 如果寻找元素更大就进入右子树
else if(comparableResult > 0){
return contains(t.right.element);
}
// 匹配到了
else {
return true;
}
}
/**
* 递归寻找树最小元素
* @param t 节点
* @return 最小元素的节点
*/
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
if(t == null){
return null;
}
if(t.left == null){
return t;
}
return findMin(t.left);
}
/**
* 非递归寻找树最大元素
* @param t 节点
* @return 是最大元素的节点
*/
private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
if(t != null){
while (t.right != null){
t = t.right;
}
}
return t;
}
/**
* 把元素x插入根节点为t的树
* 值得注意的是，如果树中已经存在相同的元素，我们这里并不继续插入
* 可以考虑用另外的存储结构表示每个元素及其出现频数，并在该情况下使频数加一
* @param x 元素
* @param t 节点
* @return 插入后的新根节点
*/
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
if(t == null){
return new BinaryNode<AnyType>(x, null, null);
}
int comparableResult = x.compareTo(t.element);
if(comparableResult < 0){
t.left = insert(x, t.left);
}
else if(comparableResult > 0){
t.right = insert(x, t.right);
}
// 重复，什么也不做，不插入了
else {
;
}
return t;
}
/**
* 在根节点为t的树中删除元素x
* 值得注意的是，可以考虑在另外的结构（在插入方法的注释中提到过）把频数减1，这种被称作懒惰删除
* @param x 待插入元素
* @param t 节点
* @return 删除后的树的新根节点，如果没有删除成功，则返回null
*/
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
// 元素并未找到，do nothing
if(t == null){
return null;
}
int comparableResult = x.compareTo(t.element);
if(comparableResult < 0){
t.left = remove(x, t.left);
}
else if(comparableResult > 0){
t.right = remove(x, t.right);
}
// 如果找到了该元素并且该节点同时有左右孩子
// 用这个节点的右子树的最小数据代替这个节点的数据，并且右子树删除那个最小数据节点
else if(t.right != null && t.left != null){
t.element = findMin(t.right).element;
t.right = remove(t.element,t.right);
}
// 如果只有一个孩子，返回那个非空的孩子
// 如果没有孩子，就返回空
else {
t = (t.left!=null) ? t.left : t.right;
}
return t;
}
/**
* 中序遍历
* @param t 某节点
*/
private void printTree(BinaryNode<AnyType> t) {
if(t != null){
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
public static void main(String[] args) {
BinarySearchTree<Integer> integerBinarySearchTree = new BinarySearchTree<>();
for (int i = 0; i < 10; i++) {
integerBinarySearchTree.insert( new Random().nextInt(20) + i);
// integerBinarySearchTree.printTree();
// System.out.println("--------------");
}
System.out.println("integerBinarySearchTree的打印结果为:");
integerBinarySearchTree.printTree();
char[] chars = new char[]{'b','c','a','a','d','z','f','-','+','*'};
BinarySearchTree<Character> characterBinarySearchTree = new BinarySearchTree<>();
for (int i = 0; i < 10; i++) {
characterBinarySearchTree.insert(chars[i]);
// characterBinarySearchTree.printTree();
// System.out.println("--------------");
}
System.out.println("characterBinarySearchTree的打印结果为:");
characterBinarySearchTree.printTree();
String[] strings = new String[]{"fhn","Strolling","str707","你好，世界","\nnn","4536251"};
BinarySearchTree<String> stringBinarySearchTree = new BinarySearchTree<>();
for (int i = 0; i < 6; i++) {
stringBinarySearchTree.insert(strings[i]);
// stringBinarySearchTree.printTree();
// System.out.println("--------------");
}
System.out.println("stringBinarySearchTree的打印结果为:");
stringBinarySearchTree.printTree();
}
}
内容总结
以上是互联网集市为您收集整理的基于JAVA泛型机制实现二叉查找树全部内容，希望文章能够帮你解决基于JAVA泛型机制实现二叉查找树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】