查询二叉树是平衡树->红黑树的基础,红黑树是TreeMap和TreeSet实现的基础。
深度:根到任意节点的唯一路径长,根节点的深度是零
高度:从节点到一片树叶的最长路径长,树叶的高度是零
二叉树:每个节点都不能有多余两个的儿子
public class BinarySearchTree<T extends Comparable<? super T>> { // 树的每个节点都是一个Node private static class Node<T> { /** * 构造方法 */ Node(T element) { this(element, null, null); } /** * 构造方法 */ Node(T element, Node<T> lt, Node<T> rt) { this.element = element; this.left = lt; this.right = rt; } // 每个节点的3个属性 T element; // 要存储的值 Node<T> left; // 左节点 Node<T> right; // 右节点 } /** * 根节点 */ private Node<T> root; /** * 构造方法 */ public BinarySearchTree() { root = null; } /** * 设置树为空树 */ public void makeEmpty() { root = null; } /** * 判断树是否是空树 */ public boolean isEmpty() { return root == null; } /** * 判断当前树中是否包含元素为t的节点 */ public boolean contains(T t) { return contains(root, t); } private boolean contains(Node<T> root, T t) { if (root == null) return false;// 空树返回false int i = t.compareTo(root.element); if (i > 0) // 比较节点右儿子 return contains(root.right, t); else if (i < 0)// 比较节点左儿子 return contains(root.left, t); else return true; } /** * 查找最小值 */ public T findMin() { if (isEmpty()) { throw new NullPointerException(); } return findMin(root).element; } /** * 递归 :比较耗资源 */ private Node<T> findMin(Node<T> root) { if (root.left == null) return root; return findMin(root.left); } /** * 查找最大值 */ public T findMax() { if (isEmpty()) { throw new NullPointerException(); } return findMax(root).element; } /** * 建议方式 */ private Node<T> findMax(Node<T> root) { while (root.right != null) { root = root.right; } return root; } /** * 添加元素 */ public void add(T t) { root = add(root, t); } /** * 过程 * 这里不考虑重复元素 * 重复元素,可以在Node<T>中加一个计数的域来处理,节省空间 * 还可以保存在一个辅助数据结构中,树||表? */ private Node<T> add(Node<T> node, T t) { if (node == null) { return new Node<T>(t); } int i = t.compareTo(node.element); if (i > 0) node.right = add(node.right, t); else if (i < 0) node.left = add(node.left, t); else ; // 相等的不考虑 return node; } /** * 删除元素 */ public void remove(T t) { remove(root, t); } /** * 过程 删除节点只有一个儿子,直接删除节点, 用其儿子替换 * 删除节点有两个儿子,取右儿子节点下的最小值 替换删除节点 */ private Node<T> remove(Node<T> node, T t) { if (node == null) { return node; } int i = t.compareTo(node.element); if (i > 0) { node.right = remove(node.right, t); } else if (i < 0) { node.left = remove(node.left, t); } else if (node.right != null && node.left != null) {// 删除节点有两个儿子 node.element = findMin(node.right).element; node.right = remove(node.right, node.element); } else {// 删除节点有一个儿子,或者没有儿子 node = node.left == null ? node.right : node.left; } return node; } /** * 打印 */ public void printTree() { printTree(root); } /** * 中序遍历:从小到大 */ private void printTree(Node<T> node) { if (node != null) { printTree(node.left);// 先打印小的 System.out.println(node.element); // 打印自己 printTree(node.right);// 打印大的 } } public static void main(String[] args) { BinarySearchTree<Integer> inter = new BinarySearchTree<Integer>(); System.err.println(inter.isEmpty()); inter.add(7); inter.add(4); inter.add(11); inter.add(2); inter.add(1); inter.add(3); inter.add(6); inter.add(5); inter.add(9); inter.add(10); inter.add(8); System.err.println(inter.isEmpty()); System.err.println(inter.contains(4)); System.err.println(inter.findMax()); System.err.println(inter.findMin()); inter.remove(7); inter.printTree(); } }
输出:true
false
true
11
1
1
2
3
4
5
6
8
9
10
11
后续遍历:1、3、2、5、6、4 、8、10、9、11、7
先序便利:7、4、2、1、3、6、5、11、9、8、10
如果删除次数不多,通常使用懒删除,即删除元素时它仍然留在树中,只是被标记删除。这特别在重复的时候特别有用,可以对计数域 -1
如果树中实际节点和删除节点一样多,那么树的深度预计只上升一个小的常数。
如果被删除的项是重新插入的,那么分配一个新单元的开销就避免了。
相关推荐
Java二分查找递归算法
java二分查找开发技术实现代码,注意二分查找必须是有序数组
java 二分查找法的实现方法 java 二分查找法的实现方法
用java二分查找法实现日期搜索 用java二分查找法实现日期搜索 用java二分查找法实现日期搜索
用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
java实现二分查找,包含时间复杂度的计算
JAVA用递归和非递归的方法实现二分查找
java二分查找算法,用于普通的代码算法。。,。。
二分查找树的全部操作代码:包括各种遍历操作,以及打印树形二叉树操作等;博客附带资源!
在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的搜索工具,有助于在大型有序数据集中快速...
二分查找的三种实现方式 分别是: while for 递归
while(low){ if(x==arr[mid]){ return mid; } else if(mid>0&&x[mid]){... else if(mid){//若前面没有判断,则当要查找数超过arr数组中最大值时出现死循环。 low=mid+1; mid=(low+high)/2; }
用java实现了二分查找,效率较高,思路清晰易懂。
文件读出数组进行选择排序和二分查找文件读出数组进行选择排序和二分查找java实现
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素...
Java二分查找.doc
基于java语言的二分查找,递归以及非递归算法,仅供学习娱乐
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...