`
若是人间
  • 浏览: 76538 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

java 2-3的实现

阅读更多

最近在看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);

	}

}
0
1
分享到:
评论

相关推荐

    mysql-connector-java-3.0.16-ga-bin.jar

    MySQL Connector/J是MySQL数据库与Java应用程序之间的重要桥梁,它是一个实现了Java Database Connectivity (JDBC) API的驱动程序,使得Java开发者能够轻松地在Java应用中访问MySQL数据库。"mysql-connector-java-...

    mysql-connector-java-5.1.40.zip和mysql-connector-java-5.1.10.jar

    总结,`mysql-connector-java-5.1.40.zip`和`mysql-connector-java-5.1.10.jar`是MySQL与Java应用交互的关键组件,它们通过JDBC实现了数据存取功能。了解和正确使用这些文件,可以帮助Java开发者更高效地与MySQL...

    mysql-connector-java-5.1.45-bin.jar

    它实现了JDBC(Java Database Connectivity)接口,使得Java程序可以通过标准的JDBC API来操作MySQL数据库。JDBC是Java平台中用于与各种数据库交互的一组API,它为开发人员提供了一种统一的方式来访问数据库,无论...

    mysql-connector-java-5.1.40-bin.jar连接器

    MySQL Connector/J是MySQL数据库系统与Java应用程序之间的重要桥梁,它是一个实现了JDBC(Java Database Connectivity)规范的驱动程序,使得Java开发者能够通过编写Java代码来访问、操作MySQL数据库。在这个特定的...

    mysql-connector-java-gpl-5.1.36

    MySQL Connector/J是MySQL数据库系统与Java应用程序之间的桥梁,它是一个实现了Java Database Connectivity (JDBC) API的驱动程序,使得Java开发者能够方便地在Java应用程序中访问MySQL数据库。"mysql-connector-...

    ckeditor-java-core-3.5.3

    在Java环境下,可以创建Java插件与CKEditor的JavaScript部分进行通信,实现更复杂的业务逻辑。 6. **版本兼容性** 版本号"3.5.3"表明这是CKEditor的一个较旧版本,发布于2011年。虽然它可能缺少一些较新版本中的...

    mysql-connector-java-8.0.11

    MySQL Connector/J是MySQL数据库与Java应用程序之间的重要桥梁,它是一个实现了Java Database Connectivity (JDBC) API的驱动程序,使得Java开发者能够方便地在MySQL数据库上执行SQL查询和操作。在这个"mysql-...

    mysql-connector-java-5.1.15-bin.jar

    JDBC驱动程序主要分为四种类型:Type 1、Type 2、Type 3和Type 4,其中MySQL Connector/J属于Type 4,即纯Java实现,无需依赖于操作系统或数据库供应商的特定库,因此具有良好的平台兼容性。 MySQL Connector/J的...

    WSDL2Java--根据wsdl生成Java客户端工具

    **WSDL2Java工具详解** 在Web服务的世界中,`WSDL`(Web Service Description Language)是一种XML格式的规范,用于定义服务接口、操作、消息结构等,使得服务消费者能够理解如何与服务进行交互。而`WSDL2Java`工具...

    mysql连接包mysql-connector-java-5.1.27.jar

    总的来说,`mysql-connector-java-5.1.27.jar`是Java开发者连接到MySQL数据库的关键组件,它提供了与MySQL通信的桥梁,使得开发者能够利用Java的强大功能来实现数据库操作。了解和熟练掌握这些知识点对于任何使用...

    mysql-connector-java-5.1.7 jar包

    这可以通过多种方式实现,如在IDE(如Eclipse或IntelliJ IDEA)中设置,或者在命令行运行Java程序时使用`-cp`或`-classpath`参数指定。一旦驱动被正确引入,就可以通过以下步骤建立数据库连接: 1. 导入必要的JDBC...

    反欺诈-反欺诈平台-反欺诈平台源码-反欺诈平台java代码-基于Web的反欺诈平台设计与实现-反欺诈平台设计与实现-java代码

    反欺诈-反欺诈平台-反欺诈平台源码-反欺诈平台java代码-反欺诈平台设计与实现-基于springboot的反欺诈平台-基于Web的反欺诈平台设计与实现-反欺诈网站-反欺诈网站源码-反欺诈网站java代码-反欺诈项目-反欺诈项目代码...

    mysql-connector-java-5.1.30

    MySQL Connector/J属于Type 4 JDBC驱动,意味着它是纯Java实现,无需安装任何本地库,可以在任何支持Java的平台上运行。 3. **功能**: - 数据库连接:通过`java.sql.DriverManager.getConnection()`方法创建到...

    mysql-connector-java-5.1.37jar包和源码

    1. 添加依赖:在Java项目中,你需要将`mysql-connector-java-5.1.37.jar`添加到项目的类路径中,这可以通过IDE的配置或在构建脚本(如Maven的pom.xml或Gradle的build.gradle)中指定依赖来实现。 2. 建立连接:使用...

    智慧养老-智慧养老平台-智慧养老平台源码-智慧养老平台java代码-基于Web的智慧养老平台设计与实现-智慧养老平台设计与实现

    智慧养老-智慧养老平台-智慧养老平台源码-智慧养老平台java代码-智慧养老平台设计与实现-基于springboot的智慧养老平台-基于Web的智慧养老平台设计与实现-智慧养老网站-智慧养老网站源码-智慧养老网站java代码-智慧...

    protoc+protoc-gen-grpc-java

    3. 编译生成的Java代码,并在你的应用中引入它们。在服务端,实现服务接口并启动gRPC服务器;在客户端,使用服务存根来调用远程方法。 总的来说,`protoc`和`protoc-gen-grpc-java`是gRPC Java开发中的关键工具,...

    学习-学习平台-学习平台源码-学习平台java代码-基于Web的学习平台设计与实现-学习平台设计与实现-学习项目代码-java

    学习-学习平台-学习平台源码-学习平台java代码-学习平台设计与实现-基于springboot的学习平台-基于Web的学习平台设计与实现-学习网站-学习网站源码-学习网站java代码-学习项目-学习项目代码-学习系统-学习系统源码-...

    mysql-connector-java-5.1.37

    MySQL Connector/J 5.1.37 是MySQL数据库与Java应用程序之间的重要桥梁,它是一个实现了JDBC(Java Database Connectivity)接口的驱动程序,允许Java开发者在应用中与MySQL数据库进行交互。这个版本的驱动是MySQL...

    电商-电商平台-电商平台源码-电商平台java代码-基于Web的电商平台设计与实现-电商平台设计与实现-电商项目代码-java

    电商-电商平台-电商平台源码-电商平台java代码-电商平台设计与实现-基于springboot的电商平台-基于Web的电商平台设计与实现-电商网站-电商网站源码-电商网站java代码-电商项目-电商项目代码-电商系统-电商系统源码-...

Global site tag (gtag.js) - Google Analytics