- 浏览: 778240 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
萨琳娜啊:
Java读源码之Netty深入剖析网盘地址:https://p ...
Netty源码学习-FileRegion -
飞天奔月:
写得有趣 ^_^
那一年你定义了一个接口 -
GoldRoger:
第二个方法很好
java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 -
bylijinnan:
<script>alert("close ...
自己动手实现Java Validation -
paul920531:
39行有个bug:"int j=new Random ...
java-蓄水池抽样-要求从N个元素中随机的抽取k个元素,其中N无法确定
see also:http://blog.csdn.net/jiqiren007/article/details/6534810
import java.util.LinkedList; import ljn.help.*; public class OperationsOnBinarySearchTree { /** * It shows the operations on Binary Search Tree. * see also: http://blog.csdn.net/jiqiren007/article/details/6534810 */ private Node root; public static void main(String[] args) { int[] data={12,5,18,2,9,15,19,0,0,8,0,0,17,}; /* 12 / \ 5 18 / \ / \ 2 9 15 19 / \ 8 17 */ OperationsOnBinarySearchTree bst=new OperationsOnBinarySearchTree(data); bst.levelTraverse(); bst.insert(13); bst.levelTraverse(); bst.delete(13); bst.levelTraverse(); bst.delete(12); bst.levelTraverse(); bst.inOrder(bst.root); } public OperationsOnBinarySearchTree(int[] data){ root=Helper.createTree(data); } public void delete(int dataDelete){ if(root==null){ return; } Node curNode=root; NodePair pair=findNodeAndParent(curNode,dataDelete); Node nodeDelete=pair.son; Node parent=pair.parent; if(nodeDelete==null){ return; } if(isLeaf(nodeDelete)){ if(parent.getLeft()==nodeDelete){ parent.setLeft(null); } if(parent.getRight()==nodeDelete){ parent.setRight(null); } }else{ if( hasLeftOnly(nodeDelete) ){ if(parent.getLeft()==nodeDelete){ parent.setLeft(nodeDelete.getLeft()); } if(parent.getRight()==nodeDelete){ parent.setRight(nodeDelete.getLeft()); } }else if( hasRightOnly(nodeDelete) ){ if(parent.getLeft()==nodeDelete){ parent.setLeft(nodeDelete.getRight()); } if(parent.getRight()==nodeDelete){ parent.setRight(nodeDelete.getRight()); } }else{//has both left child and right child.Successor is in the min(curNode.getRight()) NodePair tmpPair=min(nodeDelete.getRight()); Node successor=tmpPair.son; Node sParent=tmpPair.parent; nodeDelete.setData(successor.getData()); if(null==sParent){ nodeDelete.setRight(null); }else{ sParent.setLeft(successor.getRight()); } } } } public NodePair findNodeAndParent(Node curNode,int data){ if(curNode==null){ return null; } Node parent=null; Node son=null; NodePair pair=null; while(curNode!=null){ int curData=curNode.getData(); if(curData==data){ son=curNode;//when curNode.getData()==data,'parent' is null.Is it OK? break; } if(data<curData){ parent=curNode; curNode=curNode.getLeft(); } if(data>curData){ parent=curNode; curNode=curNode.getRight(); } } pair=new NodePair(son,parent); return pair; } public boolean hasLeftOnly(Node node){ return node!=null&&node.getLeft()!=null&&node.getRight()==null; } public boolean hasRightOnly(Node node){ return node!=null&&node.getRight()!=null&&node.getLeft()==null; } public boolean isLeaf(Node node){ return node!=null&&node.getLeft()==null&&node.getRight()==null; } public NodePair min(Node curNode){ if(curNode==null){ return null; } Node parent=null; while(curNode.getLeft()!=null){//when 'curNode' has no left child,'curNode' is min,and its parent is null(ok?) parent=curNode; curNode=curNode.getLeft(); } return new NodePair(curNode,parent); } //we don't get 'max''s parent node like 'min' public Node max(Node curNode){ if(curNode==null){ return null; } while(curNode.getRight()!=null){ curNode=curNode.getRight(); } return curNode; } public Node find(int target){ if(root==null){//empty tree return null; }else{ return findHelp(root,target); } } public Node findHelp(Node curNode,int target){ Node result=null; int curData=curNode.getData(); if(target==curData){ result=curNode; } if(target<curData){ findHelp(curNode.getLeft(),target); } if(target>curData){ findHelp(curNode.getRight(),target); } return result; } public void insert(int dataInsert){ if(root==null){//the tree is empty root=new Node(dataInsert); }else{ insertHelp(root,dataInsert); } } public void insertHelp(Node curNode,int dataInsert){ Node nodeToInsert=new Node(dataInsert); int curData=curNode.getData(); if(dataInsert<=curData){//insert into left tree Node left=curNode.getLeft(); if(left==null){ curNode.setLeft(nodeToInsert); }else{ insertHelp(left,dataInsert); } } if(dataInsert>curData){//insert into right tree Node right=curNode.getRight(); if(right==null){ curNode.setRight(nodeToInsert); }else{ insertHelp(right,dataInsert); } } } public void levelTraverse(){ if(root==null){ return; } Node node=root; LinkedList<Node> queue=new LinkedList<Node>(); queue.addLast(node); while(!queue.isEmpty()){ node=queue.removeFirst(); System.out.print(node.getData()+" "); if(node.getLeft()!=null){ queue.addLast(node.getLeft()); } if(node.getRight()!=null){ queue.addLast(node.getRight()); } } System.out.println(); } public void inOrder(Node curNode){ if(curNode==null){ return; } inOrder(curNode.getLeft()); System.out.print(curNode.getData()+" "); inOrder(curNode.getRight()); } //when deleting a node,we need the node and its parent. private static class NodePair{ Node son; Node parent; NodePair(Node son,Node parent){ this.son=son; this.parent=parent; } } }
发表评论
-
二维数组(矩阵)对角线输出
2014-04-28 17:55 4599/** 二维数组 对角线输出 两个方向 例如对于数 ... -
线段树-poj1177-N个矩形求边长(离散化+扫描线)
2013-01-05 20:34 2908package com.ljn.base; import ... -
线段树-入门
2013-01-05 20:32 2109/** * 线段树入门 * 问题:已知线段 ... -
bitmap求哈密顿距离-给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(
2012-12-27 21:12 2889import java.util.Random; / ... -
百度笔试题:一个已经排序好的很大的数组,现在给它划分成m段,每段长度不定,段长最长为k,然后段内打乱顺序,请设计一个算法对其进行重新排序
2012-12-21 18:17 4050import java.util.Arrays; ... -
有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。写一个函数实现。复杂度是什么。
2012-12-07 14:32 3544import java.util.Random; i ... -
三色旗算法
2012-11-29 12:19 3753import java.util.Arrays; ... -
单调队列-用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值
2012-11-11 22:32 2299import java.util.LinkedList; ... -
据说是2012年10月人人网校招的一道笔试题-给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 将重物放到天平左侧,问在两边如何添加砝码
2012-10-28 23:41 1918public class ScalesBalance { ... -
编程之美-分层遍历二叉树
2012-08-12 10:02 5861import java.util.ArrayList; ... -
编程之美-最短摘要的生成
2012-08-10 18:37 2431import java.util.HashMap; ... -
编程之美-计算字符串的相似度
2012-08-09 19:25 2850public class StringDistance ... -
编程之美-电话号码对应英语单词
2012-08-09 19:24 4167import java.util.Arrays; ... -
编程之美-数组中最长递增子序列
2012-08-09 19:22 1957import java.util.Arrays; imp ... -
编程之美-数组中最长递增子序列
2012-08-09 19:22 6import java.util.Arrays; imp ... -
xxx
2012-08-09 00:35 0package beautyOfCoding; public ... -
编程之美-子数组的最大和(二维)
2012-08-05 23:51 2206package beautyOfCoding; impo ... -
编程之美-子数组的最大乘积
2012-08-06 00:00 2234public class MaxProduct { ... -
编程之美-找符合条件的整数 用字符串来表示大整数避免溢出
2012-07-26 19:26 1789import java.util.LinkedList ... -
sudoku
2012-07-25 20:36 0package a; public class Sudoku ...
相关推荐
主要为大家详细介绍了java二叉查找树的实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
java bitset 源码 最后更新于20180424 (Toc generated by ) ...二叉查找树(BST) 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree)。
高级java笔试题 《后端架构师技术图谱》 最后更新于20180502 (Toc generated ...二叉查找树(BST) 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary
高级java笔试题 架构师之路 (Toc ...二叉查找树(BST) 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree)。 红黑树 添加阶段后,左旋或
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、...
亚信java笔试题 《后端架构师技术图谱》 更新于20180624 (Toc generated ...二叉查找树(BST) 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tr
java简易投票系统源码下载 《后端架构师技术图谱》 更新于20180513 (Toc ...二叉查找树(BST) 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted bina
阿里云java短信验证码源码 《后端架构师技术图谱》 :thumbs_up: :thumbs_up: :thumbs_up: 推荐一个在线搜课程的神器,“”: ...二叉查找树(BST) 二叉查找树(Binary Search Tree),也称有序二叉树(or
二叉查找树(BST) 红黑树 B,B+,B*树 LSM 树 BitSet 常用算法 计数排序 桶排序 基数排序 二分查找 Java 中的排序工具 布隆过滤器 字符串比较 KMP 算法 深度优先、广度优先 贪心算法 回溯算法 剪枝算法 动态规划 ...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归...斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)等...
二叉搜索树(BST) 问题 解决方案 位操作 问题 解决方案 | 动态规划 问题 解决方案 | | 芬威克树/二叉索引树(BIT) 问题 解决方案 图形 问题 解决方案 贪婪的 问题 解决方案 | 迭代器 问题 解决方案 链表 问题 解决...
(BST)](二叉搜索树bst) 【红黑树】(黑树) [B, B+, B* 树](树) [LSM 树] () 【常用算法】(算法) [排序,查找算法](排序搜索算法) [选择排序](排序) 【气泡排序】(排序) [插入排序](排序) 【快速排序...
《后端架构师技术图谱》更新于20180624二叉查找树(BST)红黑树B-,B+,B*树LSM 树BitSet常用算法排序、查找算法选择排序冒泡排序插入排序快速排序归并排序希尔排序堆排序计数排序桶排序基数排序二分查找Java 中的...
列特码Java中的Leet代码解决方案转储,链接到下面列出的问题加两个数字: : 检测资金: : 分发糖果: : 查找左下树值: : 汉明距离: : 二叉搜索树的最低共同祖先: : 最大二叉树: : BST中的最小绝对差值: : //...
二进制搜索树(BST) 堆 哈希表 脱节集联合(联合查找) 特里 后缀数组 段树 二进制索引树(BIT) 重光分解 线性搜寻 二元搜寻 三元搜索 合并排序 快速排序 桶分类 计数排序 堆排序 基数排序 图算法 图表示 广度优先...
将排序列表转换为二叉搜索树 递归有序 前 K 个频繁元素 最小堆 区间列表交点 合并区间 从前序遍历构造二叉搜索树 递归的 查找每个树行中的最大值 队列 编辑距离 动态规划 最长递增子序列 二分搜索动态规划 会议室二 ...
java语言实现leetcode中的一些题,数据结构的一些基本知识也在往这上面总结。:turtle: src algorithm 算法总结 basic 写一些基础的算法,如快排 famous 著名的一些算法 LCS 最长公共子序列 graph 图 sort 排序 test ...
第 338 章五月 Leetcoding 挑战 ...从前序遍历构建二叉搜索树 - 问题 :right_arrow: 未交叉线 - 问题 :right_arrow: 连续数组 - 问题 :right_arrow: 可能的二分法 - 问题 :right_arrow: 计数位 - 问题
二叉搜索树(平衡和不平衡) BST 红黑树 AVL树 跳过列表 堆 哈希值 冲突解决方法 链接 开放寻址 线性探测 多项式探测 散列探测的散列 联合查找 后缀树 算法 图表 分布式文件系统 BFS 拓扑排序 克鲁斯卡尔 MST 总理 ...
二叉查找树 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 ...