最近在看B+树,看了两天没看出来所以然来,所以打算从最基础的写起,昨天将二叉树写出来的,今天在二叉树的基础上实现了2-3,下篇要实现B-,然后再是B+,下面是B+树的代码,只在二叉树的基础上做了一些改动,可以参考上一篇二叉树的构建。
BinaryTree类:
package com.javaeye.rsrt;
/**
*
* @author nishiting
*
*/
public class BinaryTree {
private Node root;
private int keyAmount;
/**
* 内部类实现结点类,可提高安全性
*
* @author nishiting
*
*/
private static class Node {
Node left;//左孩子
Node right;//右孩子
Node middle;//中间结点
int keyAmount;//键值数
int data[];//键值
int size=0;//计算当前的健值数
/**
* 初始化结点
* @param newData 键值
* @param keyAmount 结点数
*/
Node(int newData, int keyAmount) {
++size;
data = new int[2];
left = null;
right = null;
middle = null;
data[0] = newData;
keyAmount = keyAmount;
}
/**
* 添加键值,根据position的位置移位
* @param newData 键值
* @param position 位置
*/
void addKey(int newData, int position) {
++size;
for(int z =position;z<size-1;z++){
data[z+1] = data[z];
}
data[position] = newData;
}
}
/**
* 创建一个空的二叉树
*/
public BinaryTree(int keyAmount) {
root = null;
this.keyAmount = keyAmount;
}
/**
* 递归的插入数值
*
* @param data
* 要插入的数值
*/
public void insert(int data) {
root = insert(root, data);
System.out.println("-------"+data+"结束"+"------------------");
}
/**
* 将数值插入到二叉树中,比当前结点小或等于当前结点的插在当前结点的左侧,比当前结点大的数插在当前结点的右侧,每次从根结点开始递归比较
*
* @param node
* 当前的结点,就是根结点,只是每次根结点的左右子孙更新
* @param data
* 要插入的数值
* @return 新排好的二叉树
*/
private Node insert(Node node, int data) {
if (node == null) {
node = new Node(data, keyAmount);
} else {
if (isFull(node)) {
for (int i = 0; i < node.size; i++) {
if (data <= node.data[i]) {
System.out.println("进入左子数");
node.left = insert(node.left, data);
return node;
} else {
if (data <= node.data[i + 1]) {
System.out.println("进入中间数");
node.middle = insert(node.middle, data);
return node;
} else {
System.out.println("进入右子数");
node.right = insert(node.right, data);
return node;
}
}
}
}else{
for(int k =0;k < node.size;k++){
if(data <= node.data[k]){
node.addKey(data, k);
return node;
}
}
node.addKey(data, node.size);
}
}
return (node);
}
/**
* 判断结点是否还有空闲空间
*
* @param node
* @return
*/
private boolean isFull(Node node) {
if (node.size >= keyAmount) {
return true;
} else {
return false;
}
}
/**
* 将数值输入构建二叉树
*
* @param data
* 要输入的数值
*/
public void buildTree(int[] data) {
for (int i = 0; i < data.length; i++) {
insert(data[i]);
}
}
/**
* 递归打印出二叉树
*/
public void printTree() {
printTree(root);
System.out.println();
}
/**
* 从根结点开始遍历,从树的最高层叶子结点开始输出,从左至右,如果没有中间指针的话先将结点的左部输出,
*
* @param node
* 当前的结点
*/
private void printTree(Node node) {
if (node == null)
return;
printTree(node.left);
if(node.middle == null){
for(int z = 0;z<node.size;z++){
System.out.print(node.data[z] + " ");
}
}else{
System.out.println(node.data[0]);
}
printTree(node.middle);
if(node.middle != null){
System.out.println(node.data[1]);
}
printTree(node.right);
}
}
分享到:
相关推荐
java敬老院-java敬老院系统-java敬老院系统源码-java敬老院管理系统-java敬老院管理系统java代码-java敬老院系统设计与实现-基于springboot的java敬老院系统-基于Web的java敬老院系统设计与实现-java敬老院网站-java...
java敬老院-java敬老院系统-java敬老院系统源码-java敬老院管理系统-java敬老院管理系统java代码-java敬老院系统设计与实现-基于springboot的java敬老院系统-基于Web的java敬老院系统设计与实现-java敬老院网站-java...
学习-学习平台-学习平台源码-学习平台java代码-学习平台设计与实现-基于springboot的学习平台-基于Web的学习平台设计与实现-学习网站-学习网站源码-学习网站java代码-学习项目-学习项目代码-学习系统-学习系统源码-...
电商-电商平台-电商平台源码-电商平台java代码-电商平台设计与实现-基于springboot的电商平台-基于Web的电商平台设计与实现-电商网站-电商网站源码-电商网站java代码-电商项目-电商项目代码-电商系统-电商系统源码-...
网购-网购平台-网购平台源码-网购平台java代码-网购平台设计与实现-基于springboot的网购平台-基于Web的网购平台设计与实现-网购网站-网购网站源码-网购网站java代码-网购项目-网购项目代码-网购系统-网购系统源码-...
正则表达式就业-就业平台-就业平台源码-就业平台java代码-就业平台设计与实现-基于springboot的就业平台-基于Web的就业平台设计与实现-就业网站-就业网站源码-就业网站java代码-就业项目-就业项目代码-就业系统-就业...
卤菜销售-卤菜销售平台-卤菜销售平台源码-卤菜销售平台java代码-卤菜销售平台设计与实现-基于ssm的卤菜销售平台-基于Web的卤菜销售平台设计与实现-卤菜销售网站-卤菜销售网站源码-卤菜销售网站java代码-卤菜销售项目...