写点什么

Java 实现:二叉搜索树 (Binary Search Tree)

  • 2021 年 11 月 11 日
  • 本文字数:2603 字

    阅读完需:约 9 分钟

1.3、构造器和成员变量

private BinaryNode<AnyType> root;


private Comparator<? super AnyType> cmp;


/**


  • 无参构造器


*/


public BinarySearchTree() {


this(null);


}


/**


  • 带参构造器,比较器

  • @param c 比较器


*/


public BinarySearchTree(Comparator<? super AnyType> c) {


root = null;


cmp = c;


}

1.3、公共方法(public method)

主要包括插入,删除,找到最大值、最小值,清空树,查看元素是否包含;


/**


  • 清空树


*/


public void makeEmpty() {


root = null;


}


public boolean isEmpty() {


return root == null;


}


public boolean contains(AnyType x){


return contains(x,root);


}


public AnyType findMin(){


if (isEmpty()) throw new BufferUnderflowException();


return findMin(root).element;


}


public AnyType findMax(){


if (isEmpty()) throw new BufferUnderflowException();


return findMax(root).element;


}


public void insert(AnyType x){


root = insert(x, root);


}


public void remove(AnyType x){


root = remove(x,root);


}

1.4、比较函数

如果有比较器,就使用比较器,否则要求对象实现了 Comparable 接口;


private int myCompare(AnyType lhs, AnyType rhs) {


if (cmp != null) {


return cmp.compare(lhs, rhs);


} else {


return lhs.compareTo(rhs);


}


}

1.5、contains 函数

本质就是一个树的遍历;


private boolean contains(AnyType x, BinaryNode<AnyType> t) {


if (t == null) {


return false;


}


int compareResult = myCompare(x, t.element);


if (compareResult < 0) {


return contains(x, t.left);


} else if (compareResult > 0) {


return contains(x, t.right);


} else {


return true;


}


}

1.6、findMin

因为二叉搜索树的性质,最小值一定是树的最左节点,要注意树为空的情况。


/**


  • Internal method to find the smallest item in a subtree

  • @param t the node that roots the subtree

  • @return node containing the smallest item


*/


private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {


if (t == null) {


return null;


}


if (t.left == null) {


return t;


}


return findMin(t.left);


}

1.7、findMax

最右节点;


/**


  • Internal method to find the largest item in a subtree

  • @param t the node that roots the subtree

  • @return the node containing the largest item


*/


private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){


if (t == null){


return null;


}


if (t.right == null){


return t;


}


return findMax(t.right);


}

1.8、insert

这个主要是根据二叉搜索树的性质,注意当树为空的情况,就可以加入新的节点了,还有当该值已经存在时,默认不进行操作;


/**


  • Internal method to insert into a subtree

  • @param x the item to insert

  • @param t the node that roots the subtree

  • @return the new root of the subtree


*/


private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){


if (t == null){


return new BinaryNode<>(x,null,null);


}


int compareResult = myCompare(x,t.element);


if (compareResult < 0){


t.left = insert(x,t.left);


}


else if (compareResult > 0){


t.right = insert(x,t.right);


}


else{


//Duplicate; do nothing


}


return t;


}

1.9、remove




注意当空树时,返回 null;


最后一个三元表达式,是在之前已经排除掉节点有两个儿子的情况下使用的。


/**


  • Internal method to remove from a subtree

  • @param x the item to remove

  • @param t the node that roots the subtree

  • @return the new root of the subtree


*/


private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){


if (t == null){


return t; // Item not found ,do nothing


}


int compareResult = myCompare(x,t.element);


if (compareResult < 0){


t.left = remove(x,t.left);


}


else if (compareResult > 0){


t.right = remove(x,t.right);


}


else if (t.left !=null && t.right!=null){


//Two children


t.element = findMin(t.right).element;


t.right = remove(t.element,t.right);


}


else


t = (t.left !=null) ? t.left:t.right;


return t;


}


二、完整代码实现(Java)




/**


  • @author LongRookie

  • @description: 二叉搜索树

  • @date 2021/6/26 19:41


*/


import com.sun.source.tree.BinaryTree;


import java.nio.BufferUnderflowException;


import java.util.Comparator;


/**


  • 二叉搜索树


*/


public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {


/**


  • 节点

  • @param <AnyType>


*/


private static class BinaryNode<AnyType> {


BinaryNode(AnyType theElement) {


this(theElement, null, null);


}


BinaryNode(AnyType theElement, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {


element = theElement;


left = left;


right = right;


}


AnyType element; // the data in the node


BinaryNode<AnyType> left; // Left child


BinaryNode<AnyType> right; // Right child


}


private BinaryNode<AnyType> root;


private Comparator<? super AnyType> cmp;


/**


  • 无参构造器


*/


public BinarySearchTree() {


this(null);


}


/**


  • 带参构造器,比较器

  • @param c 比较器


*/


public BinarySearchTree(Comparator<? super AnyType> c) {


root = null;


cmp = c;


}


/**


  • 清空树


*/


public void makeEmpty() {


root = null;


}


public boolean isEmpty() {


return root == null;


}


public boolean contains(AnyType x){


return contains(x,root);


}


public AnyType findMin(){


if (isEmpty()) throw new BufferUnderflowException();


return findMin(root).element;


}


public AnyType findMax(){


if (isEmpty()) throw new BufferUnderflowException();


return findMax(root).element;


}


public void insert(AnyType x){


root = insert(x, root);


}


public void remove(AnyType x){


root = remove(x,root);


}


private int myCompare(AnyType lhs, AnyType rhs) {


if (cmp != null) {


return cmp.compare(lhs, rhs);


} else {


return lhs.


【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


compareTo(rhs);


}


}


private boolean contains(AnyType x, BinaryNode<AnyType> t) {


if (t == null) {


return false;


}


int compareResult = myCompare(x, t.element);


if (compareResult < 0) {


return contains(x, t.left);


} else if (compareResult > 0) {


return contains(x, t.right);


} else {


return true;


}

评论

发布
暂无评论
Java实现:二叉搜索树(Binary Search Tree)