二叉搜索树(Binary Search Tree)(Java实现)
2021/7/7 12:35:23
本文主要是介绍二叉搜索树(Binary Search Tree)(Java实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
@
目录- 1、二叉搜索树
- 1.1、 基本概念
- 1.2、树的节点(BinaryNode)
- 1.3、构造器和成员变量
- 1.3、公共方法(public method)
- 1.4、比较函数
- 1.5、contains 函数
- 1.6、findMin
- 1.7、findMax
- 1.8、insert
- 1.9、remove
- 二、完整代码实现(Java)
1、二叉搜索树
1.1、 基本概念
二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多。分析表明其平均深度为\(\mathcal{O}(\sqrt{N})\),而对于特殊类型的二叉树,即二叉查找树(binary search tree),其深度的平均值为\(\mathcal{O}(log N)\)。
二叉查找树的性质: 对于树中的每个节点X,它的左子树中所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项。
由于树的递归定义,通常是递归地编写那些操作的例程。因为二叉查找树的平均深度为\(\mathcal{O}(log N)\),所以一般不必担心栈空间被用尽。
1.2、树的节点(BinaryNode)
二叉查找树要求所有的项都能够排序,有两种实现方式;
- 对象实现接口 Comparable, 树中的两项使用compareTo方法进行比较;
- 使用一个函数对象,在构造器中传入一个比较器;
本篇文章采用了构造器重载,并定义了myCompare方法,使用了泛型,因此两种方式都支持,在后续的代码实现中可以看到。
节点定义:
/** * 节点 * * @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 }
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; }
关于比较器的知识可以参考下面这篇文章:
Java中Comparator的使用
关于泛型的知识可以参考下面这篇文章:
如何理解 Java 中的 <T extends Comparable<? super T>>
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.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; } } /** * 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); } /** * 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); } /** * 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; } /** * 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; } }
这篇关于二叉搜索树(Binary Search Tree)(Java实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现