转载 http://my.oschina.net/BreathL/blog/54734
二叉查找树
二叉查找树是一种支持动态查询的数据结构,所谓动态查寻结构:即在当数据集合内容发生改变时,集合内数据的排列组合不用重新构建。这样的数据结构在查询时需要不断变动的场景中是非常高效的,二叉查找树就是其中一个,并且它是SBT,AVL,红黑树的基础,一直有兴趣想要研究下。原理就不介绍了,可参考这个 。今天花了半天时间,自己完成了一个基于数组的Java实现。
实现的方法:INSERT、SEACH、DELETE
先简单说明下这几个方法的实现原理:
SEARCH:
查询方法的思路很简单,和二分查找相似,即从根节点开始查找,若待查找元素a小于根节点,则在该节点的左子树中继续查找,大于则去右子树中,等于便是找到了。
INSERT:
插入方法,也是一个查询的过程,若根节点为空,则直接设置成跟节点,否则依如下方式与节点比较: 若小于节点值,将元素插入其左子树,若大于该节点值插入其右子树。若发现相等的则退出,算是排重。
DELETE:
删除操作相对比较复杂,若要删除某一个节点 Z ,可能遇见三种情况:
一. 节点 Z 不包含任何子树;此时可直接删除,不影响数据的结构。
二. 节点 Z 只有一个子子树,左子树或右子树;此时只需将 Z 的唯一的那个子树的根节点指向 Z 的父节点即可,此操作也不影响数据的。(但由于我是基于数组的,指针式通过数组的位置表示,所以某个节点指向变了,其所有子节点在数组中的位置都要变,不过好在这种变化是有规律的,我已在程序中注明。)
三. 节点 Z 的左子树和右子树同时存在。这种情况最为复杂,首先找到 Z 左子树中值最大的节点,记为 H ,将代替 Z 在树种的位置,然后再以递归的方式删除节点 H.
package com.mycode.structures; import java.util.Collection; /** * 基于数组二叉查找树实现 * @author Breath_L * @param <T> */ public class BSTree<T extends Comparable<T>> { private static final int DEFAULT_SIZE = 10; private T[] data; private Integer count; public Integer getCount(){ return count; } public BSTree(int size){ data = (T[]) new Object[size]; count = 0; } public BSTree(){ data = (T[]) new Object[DEFAULT_SIZE]; count = 0; } /** * 扩充容量 */ private void expandSize(){ T[] newDate = (T[]) new Object[data.length * 2]; System.arraycopy(data, 0, newDate, 0, data.length); data = newDate; } /** * 判断二叉树中是否包含元素 one * @param one * @return 若找到了,返回该元素在数组中的位置,否则返回-1 */ public int search(T one){ if(data[0] == null){ System.out.println("==> This BSTree is Empty!"); return -1; }else{ int index = 0; while(index < data.length && data[index] != null){ int f = one.compareTo(data[index]); if(f == 0){ //找到了返回其位置 return index; }else if(f < 0){ index = 2 * index + 1; }else{ index = 2 * index + 2; } } return -1; } } /** * 添加元素 * @param t */ public void add(T t){ if(data[0] == null){ data[0] = t; count++; return; }else{ int index = 0; while(index < data.length){ if(t.compareTo(data[index])<0){ int left = 2 * index + 1; if(left >= data.length) expandSize(); if(data[left] == null){ data[left] = t; break; }else{ index = left; } }else if(t.compareTo(data[index]) > 0){ int right = 2 * index + 2; if(right >= data.length) expandSize(); if(data[right] == null){ data[right] = t; break; }else{ index = right; } }else{ // 相同元素不处理,算是排重了 break; } } } count++; } public void addAll(Collection<T> all){ for (T t:all){ add(t); } } public void addAll(T[] all){ for (T t:all){ add(t); } } public void delete(T del){ int del_index = this.search(del); if(del_index != -1){ //等于-1 表示没有,便不做处理 real_delete(del_index); } } /** * 删除某个节点 * @param index:该节点在数组中的位置 * @return */ private void real_delete(int index){ int lc = 2*index + 1; int rc = 2*index + 2; if(data[lc] != null && data[rc] != null){ // 左子树、右子树同时存在的情况 int left_max_child = findLeftMaxChild(index); data[index] = data[left_max_child]; //删除节点 real_delete(left_max_child); //递归删除左子树中值最大的节点 }else if(data[lc] == null && data[rc] == null){ // 都没有则直接删除 data[index] = null; }else{ if(data[lc] != null){ replaceNodeWithChild(lc, lc-index); }else{ replaceNodeWithChild(rc, rc-index); } } } /** * 寻找某个节点的左子树中最大节点 * @param index 某个节点的位置 * @return 最大节点位置 */ private int findLeftMaxChild(int index){ int left = 2*index +1; int bigger = 2*left + 2; while( bigger < data.length && data[bigger] != null){ left = bigger; bigger = 2 * bigger + 2; } return left; } /** * 若子节点C替换了其父节点P,则C的所有子节点都需要被移动(由于数组的原因),distance为C和P在数组中位置之差。 * 其所有子节点在数组中移动的距离为 distance*(2^x),x为这些子节点与节点C的距离(相邻节点距离为1); * @param node * @param distance */ private void replaceNodeWithChild(int node, int distance){ int left = 2*node+1; int right = 2*node+2; int current_distance = distance*2; //每次递归距离*2 if(data[left] != null){ data[left - current_distance] = data[left]; replaceNodeWithChild(left,current_distance); //递归遍历下个节点 } if(data[right] != null){ data[right - current_distance] = data[right]; replaceNodeWithChild(right,current_distance); } } }
相关推荐
binary-tree.js , binary-search-tree.js , self-balancing-binary-tree.js 二叉搜索树实现包括: 插入节点 计算高度 深度优先遍历:在每个节点上依次执行一个函数(升序或降序) 返回排序的节点数组(升序或降序...
lru cache leetcode 7天入门数据结构与算法 学习目标 形成高效学习方法/习惯 LeetCode 300+的积累 学习方法 切碎知识点(脑图) ...反馈(总结/运用) ...基础:数组array,链表linked ...二分查找Binary S
二叉查找树(Binary Search Tree (BST)) 平衡二叉树/AVL 树(Balanced Binary Tree/AVL Tree) 红黑树(Red-Black Tree) 伸展树(Splay Tree) B-树(B-Tree) 线索二叉树(Threaded Binary Tree) 前缀树/字典树...
java bitset 源码 最后更新于20180424 (Toc generated by ) 数据结构 队列 非阻塞队列:...二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree)。
高级java笔试题 架构师之路 (Toc generated by ) ...二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree)。 红黑树 添加阶段后,左旋或
二叉查找树(Binary Search Tree (BST)) 平衡二叉树/AVL 树(Balanced Binary Tree/AVL Tree) 红黑树(Red-Black Tree) 伸展树(Splay Tree) B-树(B-Tree) 线索二叉树(Threaded Binary Tree) 前缀树/字典树...
亚信java笔试题 《后端架构师技术图谱》 更新于20180624 (Toc generated by ) 数据结构 ...二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tr
高级java笔试题 《后端架构师技术图谱》 最后更新于20180502 (Toc generated by ) 数据结构 ...二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary
二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree Convert Sorted List to Binary Search Tree LCA of BST Kth ...
《后端架构师技术图谱》 更新于20180513 (Toc generated by ) 数据结构 队列 非阻塞队列:...二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted bina
leetcode中国 《后端架构师技术图谱》 后端架构师技术图谱go版本 --- Fork by (Toc generated by ) ...非阻塞队列:...二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二
阿里云java短信验证码源码 《后端架构师技术图谱》 :thumbs_up: :thumbs_up: :thumbs_up: 推荐一个在线搜课程的神器,“”: 推荐: 从初级开发者到资深架构师...二叉查找树(Binary Search Tree),也称有序二叉树(or
普通的二叉搜索树 Binary-Search-Tree 广度优先搜索 Breadth-First-Search 冒泡排序 Bubble-Sort 桶排序 Bucket-Sort 组合数的递推求解 Combination(Recursion) 枚举组合 Combination 基本的复数类 Complex-...
binarysearch(二分搜索) 二分查找 寻找旋转排序数组中的最小值 design(设计) LRU doublepointer(双指针) 三数之和 两数之和II输入有序数组 无重复字符的最长子串 盛最多水的容器 dp(动态规划) 三角形最小路劲和 ...
leetcode 分类 leetcode java语言实现leetcode中的一些题,数据结构的一些基本知识也在往这上面总结。:turtle: src algorithm 算法总结 ...二叉搜索树性质应用 depth 二叉树深度问题 doubleRecursio
C / C ++中的数据结构和算法 该代码由Amit Bansal在学习...插入删除中预定遍历顺序遍历后遍历级别顺序遍历查找二叉搜索树的高度检查树是否为二叉搜索树(2种方法) 在二分搜索树中查找最大和最小元素 AVL树 插入b。删除
二叉搜索树 ( BST ) 字典树(前缀树) ( Trie ) 哈希表 ( Hash Table ) 堆 ( Heap ) 图 ( Graph ) 二分查找 ( Binary Search ) 位运算 ( Bit Manipulation ) 分治算法 ( Divide And Conquer ) 排序 ( Sort ) 回溯...
leetcode中国 leetcode 记录个人刷leetcode的题解 复杂度 时间复杂度:算法的执行时间与[数据规模]之间的增长关系 ...在有序的数组中查找,一分为二,每次只查找一边。 2、Binary tree traversal,二叉搜索树。O(n