package 查找.B加减树;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
/**
* Created by MSI on 2016/1/5.
* 该程序参考文章:http://blog.csdn.net/v_JULY_v/article/details/6530142/
*/
public class BsubTree<T extends Comparable<T>> {
private static BsubTree<Integer> tree = new BsubTree<Integer>();
private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int m = 4; //此B-树的阶数。关键字数等于阶数-1。m至少为2,m必须大于等于2。
int n; //n是关键字最小个数
public BTNode root;
public BsubTree(){
root = new BTNode(null,null);
if(m>=2){
if(m%2==0){
n = m/2-1;
}else {
n = m/2;
}
}else {
System.out.println("error");
System.exit(0);
}
}
public BsubTree(BTNode root){
this.root = root;
if(m%2==0){
n = m/2;
}else {
n = m/2+1;
}
}
public BTNode findNode(T information){
return findNode(information, root);
} //isMember应该返回插入点
private BTNode findNode(T info, BTNode node){ //不论是否找到都返回一个node。
BTNode member = null;
if(node.informations.size()==0){//这种情况存在,只有root可能
member = node;
//System.out.println("error");
}else {
if(info.compareTo(node.informations.get(node.informations.size()-1))>0) { //info比节点最大的还大,则直接进入最右分支
if(node.ptr.size()>0){//有孩子的情况,进入范围中的子节点
member = findNode(info, node.ptr.get(node.informations.size()));
}else {//没有子节点,直接返回node
member = node;
}
}else {//没有判断没有子节点的情况,上一个if中判断了,这一个else中就忘了,怒
if(node.ptr.size()>0){//有子节点
if(info.compareTo(node.informations.get(0))<0){
member = findNode(info, node.ptr.get(0));
}else {
for(int i = 0;i<node.informations.size();++i){
if(info.compareTo(node.informations.get(i))==0){
member = node;
break;
}else if(info.compareTo(node.informations.get(i))>0&&info.compareTo(node.informations.get(i+1))<0){ //只要不是最右,info比之大的,进入它的孩子节点
member = findNode(info, node.ptr.get(i+1));
break;
}
}
}
}else {//没有子节点
member = node;
}
}
}
return member;
}
public void insert(T info){
BTNode temp = findNode(info);
if(temp.informations.size()!=0){
for(T i:temp.informations){
if(i.compareTo(info)==0){
System.out.println("已存在所插入的值。");
return;
}
}
}
insert(info,temp,temp.parent);
return;
}
private void insert(T info,BTNode node,BTNode parent){//插入一定是在叶子节点
if(node == null){//insert中的node为空应该只有一种情况,node=root
if(parent == null){
root = new BTNode(info,parent);
}else {
System.out.println("不应该出现的情况,请检查。");
//node = new BTNode(info,parent);
}
}else{
if(node.informations.size()==0){
//System.out.println("这种情况应该不存在,请检查代码");//现在存在这种情况啦
node.informations.add(info);
}else if(node.informations.size()>0 && node.informations.size()<m-1){
if(info.compareTo(node.informations.get(node.informations.size() - 1))>0){//info比node最右边最大的值还大,则直接插入
node.informations.add(info);
}else {
for (int i = 0; i < node.informations.size(); ++i) {
if (info.compareTo(node.informations.get(i)) < 0) {
node.informations.add(i, info);
break;
}
}
}
}else if(node.informations.size()==m-1){//需要分裂
if(info.compareTo(node.informations.get(node.informations.size()-1))>0){//info比node最右边最大的值还大,则直接插入
node.informations.add(info);
}else {
for(int i = 0;i<node.informations.size();++i){
if(info.compareTo(node.informations.get(i))<0){
node.informations.add(i,info);
break;
}
}
}
split(node);
}else {
System.out.println("node 的size大于等于m-1,不应该出现,请检查代码");
}
}
}
public void delete(T info){
BTNode temp = findNode(info,root);
if(temp.informations.size()==0){
System.out.println("根节点为空!");
return;
}
for(T i:temp.informations){
if(info.compareTo(i)==0){
delete(info,temp);
break;
}else if(temp.informations.indexOf(i)==temp.informations.size()-1){//循环到最后一个值了,仍到这里,说明不存在要删除的值!
System.out.println("不存在要删除的值!");
}
}
}
private void delete(T info,BTNode node)throws NoSuchElementException {
if (node == null) { //其实到这里,就一定存在要删除的值了。
throw new NoSuchElementException();
}else {
int i;
for(i=0;i<node.informations.size();i++){
if(info.compareTo(node.informations.get(i))==0){
node.informations.remove(i); //删除关键字,其实要是索引向文件,也应该删除文件。
break;
}
}
if(node.ptr.size()>0){//删除一个非叶子节点的关键字后,如果有孩子,则判断孩子的孩子,如果孩子有孩子,则将右孩子的孩子最深左孩子的第一个值赋给删除关键字的节点
//每一个关键字,一定有两个孩子
if(node.ptr.get(i+1).ptr.size()==0){//孩子没有孩子的时候,只将孩子的最左关键字上升。
node.informations.add(i,node.ptr.get(i+1).informations.get(0));
node.ptr.get(i+1).informations.remove(0);
if(node.ptr.get(i+1).informations.size()<n){
dManageNode(node.ptr.get(i+1));
}
}else {//孩子有孩子的时候,则将右孩子的孩子最深左孩子的第一个值赋给删除关键字的节点
pullRLeftNode(node,i,node.ptr.get(i+1),i);
}
}else {//如果没有孩子,要判断该节点关键字数量是否大于最小值
if(node.informations.size()>=n){//大于等于就没事,不用动
return;
}else {//叶子�
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
java-数据结构代码实现 (286个子文件)
BsubTree.class 12KB
IBinaryTree.class 10KB
BinaryTree.class 10KB
GraphArr.class 8KB
ALGraph.class 8KB
DuLinkList.class 6KB
NGList.class 6KB
SearchBST.class 6KB
例7_6_2.class 6KB
例7_6_1.class 5KB
MatrixInt.class 5KB
CrossList.class 5KB
Matrix.class 5KB
SimpleString.class 5KB
例4_4_2.class 5KB
SearchBBST.class 5KB
KeyTree.class 4KB
例7_5_2.class 4KB
例3_2_5.class 4KB
SimpleArray.class 4KB
SSTable.class 4KB
LinkList.class 4KB
StaticLinkList.class 4KB
Polyn.class 4KB
HashTable.class 4KB
例6_6_2.class 4KB
GraphHelper.class 3KB
SimpleList.class 3KB
Bank.class 3KB
BinaryTreeTest.class 3KB
例7_5_1.class 3KB
例7_4_3.class 3KB
例3_2_4.class 3KB
SortTest.class 3KB
ListHelper.class 3KB
RadixSort.class 3KB
算法2_1.class 2KB
算法9_9.class 2KB
LinkQueue.class 2KB
SqQueue.class 2KB
NGListTest.class 2KB
INode.class 2KB
StaticStack.class 2KB
算法2_1Test.class 2KB
StaticLinkListTest.class 2KB
DuLinkListTest.class 2KB
LinkListTest.class 2KB
ShellSort.class 2KB
MergeSort.class 2KB
BinaryTree$10.class 2KB
IBinaryTree$10.class 2KB
例3_2_3.class 2KB
TreeNode.class 2KB
算法9_8.class 2KB
例2_3.class 2KB
IBinaryTreeTest.class 2KB
九宫格问题.class 2KB
例3_3_2.class 2KB
GLNode.class 2KB
SimpleListTest.class 2KB
HeapSort.class 2KB
QuikSort.class 2KB
BsubTree$BTNode.class 2KB
SelectSort.class 2KB
BinaryTree$9.class 1KB
Vistor.class 1KB
DefaultIndex.class 1KB
SSTableTest.class 1KB
Main2.class 1KB
GraphArrTest.class 1KB
A.class 1KB
ALGraphTest.class 1KB
例6_14.class 1KB
Main.class 1KB
ListHelper$1$1.class 1KB
BinaryTree$6.class 1KB
LinkQueueTest.class 1KB
SqQueueTest.class 1KB
BinaryTree$8.class 1KB
BinaryTree$7.class 1KB
BInsertSort.class 1KB
MatrixIntTest.class 1KB
IBinaryTree$4.class 1KB
IBinaryTree$2.class 1KB
IBinaryTree$3.class 1KB
InsertSort.class 1KB
IBinaryTree$5.class 1KB
ITVistor.class 1KB
Ele.class 1KB
StaticStackTest.class 1KB
PrintVisit.class 1KB
IBinaryTree$6.class 1KB
HashTableTest.class 1KB
BubbleSort.class 1KB
ListHelperTest.class 1KB
SimpleArrayTest.class 1KB
MatrixTest.class 1KB
MyIndex2.class 1KB
CrossListTest.class 1KB
例3_1.class 1KB
共 286 条
- 1
- 2
- 3
资源评论
- xll_computer2018-03-08挺不错的代码
- chengpengsdwf2018-04-08很不错的代码啊
soursecoder
- 粉丝: 1
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功