B树(二叉搜索树)定义:
1)、每个非叶子节点至多有两个子节点。
2)、每个节点都存储关键字值。
3)、其左子节点的关键字值小于该节点,且右子节点的关键字值大于或等于该节点。
/**
* 节点类
*/
class Node{
public int key;
public int data;
public Node leftChild;
public Node rightChild;
public Node(int key, int data){
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public void display(){
System.out.println("key: " + key + ", data: " + data);
}
}
/**
* B树类
*/
class Tree{
public Node root;
public void insert(int key, int data){
Node newNode = new Node(key, data);
if (root == null){
root = newNode;
}else{
Node current = root;
Node parent = null;
while (true){
parent = current;
if (key < current.key){
current = current.leftChild;
if (current == null){
parent.leftChild = newNode;
return;
}
}else{
current = current.rightChild;
if (current == null){
parent.rightChild = newNode;
return;
}
}
}
}
}
/** 只实现有一个节点的删除 */
public boolean delete(int key){
Node current = root;
Node parent = null;
boolean isLeftChild = false;
while (current.key != key){
parent = current;
if (key < current.key){
current = current.leftChild;
isLeftChild = true;
}else{
current = current.rightChild;
isLeftChild = false;
}
}
if (current == null){
return false;
}
/** 无子节点 */
if (current.leftChild == null && current.rightChild == null){
if (current == root){
root = null;
}else if (isLeftChild){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
}
/** 仅有右节点 */
else if ((current.leftChild == null && current.rightChild != null)){
if (current == root){
root = current.rightChild;
}else if (isLeftChild){
parent.leftChild = current.rightChild;
}else{
parent.rightChild = current.rightChild;
}
}else if ((current.leftChild != null && current.rightChild == null)){
if (current == root){
root = null;
}else if (isLeftChild){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
}
return true;
}
public Node find(int key){
Node current = root;
while (current != null){
if (current.key == key){
break;
}else if (key < current.key){
current = current.leftChild;
}else{
current = current.rightChild;
}
}
return current;
}
/** 中序 */
public void inOrder(Node localNode){
if (localNode != null){
inOrder(localNode.leftChild);
System.out.println("key: " + localNode.key + ", data: " + localNode.data);
inOrder(localNode.rightChild);
}
}
}
public class BTree {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Tree newTree = new Tree();
newTree.insert(5, 5);
newTree.insert(1, 1);
newTree.insert(2, 2);
newTree.insert(8, 8);
newTree.insert(9, 9);
newTree.insert(7, 7);
newTree.delete(1);
newTree.inOrder(newTree.root);
}
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/*
* Author: Robert Liu
*/
public class BTree<E extends Comparable<E>> {
private BTNode root = null;
private int t;
private final int fullNum;
public BTree(int t) {
this.t = t;
fullNum = 2 * t - 1;
}
private final BTNode NullBTNode = new BTNode();
private class BTNode {
private int number = 0;
private List<E> values = new ArrayList<E>();
private List<BTNode> children = new ArrayList<BTNode>();
private boolean isLeaf = false;
E getKey(int i) {
return values.get(i);
}
BTNode getChildren(int i) {
return children.get(i);
}
void AddKey(int i, E element) {
values.add(i, element);
}
void removeKey(int i) {
values.remove(i);
}
void AddChildren(int i, BTNode c) {
children.add(i, c);
}
void removeChildren(int i) {
children.remove(i);
}
boolean isFull() {
if (number == fullNum)
return true;
return false;
}
int getSize() {
return values.size();
}
boolean isNull() {
return (this == NullBTNode);
}
@Override
public String toString() {
if (number == 0)
return "NullNode";
StringBuilder sb = new StringBuilder();
sb.append("[N: " + number + "] [values: ");
for (E e : values) {
sb.append(e + ", ");
}
sb.append(" ] [ children: ");
for (BTNode bNode : children) {
if (bNode == NullBTNode)
sb.append(bNode + ", ");
else
sb.append("NotNullNode" + ", ");
}
sb.append("] [childrenSize: " + children.size());
sb.append("] [ isLeaf: " + isLeaf);
sb.append("]");
return sb.toString();
}
}
// Generate the root node
private void constructRoot(E elem) {
root = new BTNode();
root.number = 1;
root.AddKey(0, elem);
root.isLeaf = false;
}
private void addElemToNode(BTNode node, E element, int i) {
node.AddKey(i, element);
node.number++;
node.AddChildren(i, NullBTNode);
}
public void insertElem(E elem) {
if (root == null) {
// The first node
constructRoot(elem);
root.isLeaf = true;
root.AddChildren(0, NullBTNode);
root.AddChildren(1, NullBTNode);
return;
}
BTNode curNode = root;
if (root.isFull()) {
// Extend the root
constructRoot(curNode.getKey(t - 1));
// Get new node
BTNode newNode = getExtendedNode(curNode);
// Process old full node
processFullNode(curNode);
// Process root
root.AddChildren(0, curNode);
root.AddChildren(1, newNode);
return;
}
int i = 0;
BTNode childNode = null;
// Find the node to insert
while (true) {
while ((i < curNode.getSize())
&& (elem.compareTo(curNode.getKey(i)) > 0)) {
i++;
}
childNode = curNode.getChildren(i);
if (childNode.isFull()) {
// Split the node
// Add the element to parent
curNode.number++;
curNode.AddKey(i, childNode.getKey(t - 1));
// New node for extension
BTNode newNode = getExtendedNode(childNode);
// Process old full node
processFullNode(childNode);
// Add the new node for parent reference
curNode.AddChildren(i + 1, newNode);
// Down to low layer
if (elem.compareTo(curNode.getKey(i)) < 0) {
curNode = childNode;
} else {
curNode = newNode;
}
i = 0;
continue;
}
// Down to child node
if (!childNode.isNull()) {
curNode = childNode;
i = 0;
continue;
}
// Insert the element in current node
addElemToNode(curNode, elem, i);
return;
}
}
private BTNode getExtendedNode(BTNode fullNode) {
BTNode newNode = new BTNode();
newNode.number = t - 1;
newNode.isLeaf = fullNode.isLeaf;
for (int i = 0; i < t; i++) {
if (i != t - 1) {
newNode.AddKey(i, fullNode.getKey(t + i));
}
newNode.AddChildren(i, fullNode.getChildren(t + i));
}
return newNode;
}
// Should be called after calling getExtendedNode()
private void processFullNode(BTNode fullNode) {
fullNode.number = t - 1;
for (int i = t - 1; i >= 0; i--) {
fullNode.removeKey(t + i - 1);
fullNode.removeChildren(t + i);
}
}
@Override
public String toString() {
if (root == null)
return "NULL";
StringBuilder sb = new StringBuilder();
LinkedList<BTNode> queue = new LinkedList<BTNode>();
queue.push(root);
BTNode tem = null;
while ((tem = queue.poll()) != null) {
for (BTNode node : tem.children) {
if (!node.isNull())
queue.offer(node);
}
sb.append(tem.toString() + "\n");
}
return sb.toString();
}
public static void main(String[] args) {
BTree<Character> tree = new BTree<Character>(3);
System.out.println(tree);
Character[] cL = { 'D', 'E', 'F', 'A', 'C', 'B', 'Z', 'H', 'I', 'J' };
for (int i = 0; i < cL.length; i++) {
tree.insertElem(cL[i]);
System.out.println("After insert the: " + cL[i]);
System.out.println(tree);
}
}
output
===================
NULL
After insert the: D
[N: 1] [values: D, ] [ children: NullNode, NullNode, ] [childrenSize: 2] [ isLeaf: true]
After insert the: E
[N: 2] [values: D, E, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
After insert the: F
[N: 3] [values: D, E, F, ] [ children: NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 4] [ isLeaf: true]
After insert the: A
[N: 4] [values: A, D, E, F, ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 5] [ isLeaf: true]
After insert the: C
[N: 5] [values: A, C, D, E, F, ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 6] [ isLeaf: true]
After insert the: B
[N: 1] [values: D, ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false]
[N: 2] [values: A, C, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
[N: 2] [values: E, F, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
After insert the: Z
[N: 1] [values: D, ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false]
[N: 2] [values: A, C, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
[N: 3] [values: E, F, Z, ] [ children: NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 4] [ isLeaf: true]
After insert the: H
[N: 1] [values: D, ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false]
[N: 2] [values: A, C, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
[N: 4] [values: E, F, H, Z, ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 5] [ isLeaf: true]
After insert the: I
[N: 1] [values: D, ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false]
[N: 2] [values: A, C, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
[N: 5] [values: E, F, H, I, Z, ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 6] [ isLeaf: true]
After insert the: J
[N: 2] [values: D, H, ] [ children: NotNullNode, NotNullNode, NotNullNode, ] [childrenSize: 3] [ isLeaf: false]
[N: 2] [values: A, C, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
[N: 2] [values: E, F, ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]
[N: 3] [values: I, J, Z, ] [ children: NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 4] [ isLeaf: true]
分享到:
相关推荐
在C++中实现B树,我们需要定义一个B树节点类,这个节点类通常会包含键值、指向子节点的指针以及一个指示当前节点键值数量的变量。在`btree.h`头文件中,我们可能会看到如下声明: ```cpp class BTreeNode { public:...
- **节点结构**:理解如何定义和实现B+树的节点类,包括节点类型(叶子或非叶)、键值、指针等属性。 - **插入操作**:学习如何在保持B+树平衡的情况下插入新的键值对,可能涉及节点的分裂。 - **查找操作**:...
与B树相比,B+树的所有叶子节点都位于同一层,且叶子节点之间通过指针相互连接,这使得B+树非常适合范围查询和顺序访问。 #### 三、代码结构分析 1. **文件头注释**: - 作者:bysvking - 时间:2012年5月 - ...
总结来说,"B树索引算法 VC实现"是一个将B树数据结构应用于VC++环境的项目,通过创建B树节点和相应的操作方法,实现了数据的高效查找、插入和删除。项目附带的文档提供了对算法和实现的详细解释,以及测试验证,对于...
"BMT"可能是"B-Tree Main Test"的缩写,这可能是一个主测试程序,用来验证B-树实现的正确性和性能。 在具体实现时,需要注意的是,C++标准库并不直接支持B-树这样的数据结构,因此我们需要自己编写代码来实现。同时...
在提供的代码中,`BTree`类定义了B树的基本结构和操作,包括插入、查找、删除等方法。`height`属性记录树的高度,`n`记录键值对的数量。`Node`类维护了子节点的数组和子节点数量,`Entry`类用于存储键、值和指向下一...
B树,全称为平衡多路查找树...总的来说,理解和实现B树对于深入学习数据库和数据结构至关重要,而C#的实现则提供了一个直观的学习途径。通过这个项目,我们可以实际操作B树,进一步理解其工作原理,并提升编程技能。
在Java中实现B树,我们首先需要定义一个节点类`BTreeNode`,它包含以下属性: - `keys`:存储键的数组。 - `children`:存储子节点的数组,可以是`BTreeNode`对象。 - `leaf`:布尔值,表示当前节点是否为叶节点。 -...
B-树的实现涉及复杂的节点管理和平衡机制,但其强大的数据处理能力和优秀的磁盘访问效率使其成为大型数据集和持久化存储解决方案中的理想选择。通过深入理解B-树的结构和工作原理,可以更好地设计和优化基于B-树的...
在Java中实现B+树,我们需要定义几个关键的数据结构: 1. 节点类:每个节点包含键值数组、子节点指针数组以及一个指向兄弟节点的指针。对于B+树,节点的键值数量通常为2的幂,例如4、8、16等,以确保树的高度相对较...
这些函数和数据结构共同构成了B树的基础实现框架,通过对这些函数的具体实现,可以完成对B树的各种操作。 综上所述,B树作为一种高效的数据结构,在数据库管理和文件系统等方面具有广泛的应用。了解其原理和实现...
### B树定义 B树是一种多路搜索树,每个节点可以有多个子节点,通常用m表示最大分支数。每个非叶节点最多含有m个子节点,并且至少有⌈m/2⌉个子节点。叶子节点是满的,即至少包含⌈m/2⌉个键,而根节点至少有两个子...
B+树(B+ Tree)是一种自平衡的树数据结构,广泛应用于数据库系统和文件系统中,用于高效地存储和检索大量数据。...通过理解和实现这些算法,可以深入理解B+树的工作原理,并在实际项目中应用这种强大的数据结构。
- 源代码文件(.cpp和.h):包含了B树节点类和B树类的实现。 - 资源文件(.rc):定义了MFC应用程序的资源,如菜单、对话框和图标。 - 工程文件(.vcxproj):Visual Studio项目文件,用于编译和运行程序。 - 可执行...
同时,需要实现B树的插入、删除和查找操作。 2. **构建GUI界面**:使用QT Creator创建一个新的QT项目,选择GUI应用模板。在界面上添加必要的元素,如画布(QGraphicsView)用于绘制B树,以及可能的控制按钮...
最后,"btree.h"是B-树的头文件,它定义了B-树的相关数据结构和接口,供其他源文件引用。头文件是C++程序中模块化的重要工具,它定义了类、函数和常量,使得代码组织更加清晰,易于维护。 总的来说,这个图书管理...
在IT领域,数据结构是计算机科学的基础之一,而B树作为一种自平衡的树形数据结构,广泛应用于数据库和文件系统中。...通过实际操作和观察,你不仅可以掌握B树的基本概念,还能了解如何在C++环境中实现和优化数据结构。
在计算机科学中,B+树(B Plus Tree)是一种自平衡的...通过以上步骤,我们可以在VC++环境中实现一个功能完备的B+树数据结构,为数据的高效存储和检索提供基础。这不仅有助于理解B+树的原理,也能够提升VC++编程技巧。
本项目以C语言为基础,结合2019年广东工业大学的课程设计,实现了一个基于B树的图书管理系统,旨在让学生深入理解B树的数据结构特性和实际应用。 一、B树介绍 B树(Balanced Tree)是一种自平衡的多路搜索树,其...
综上所述,用C语言实现B树和B+树涉及到数据结构设计、算法实现以及接口工程化等多个方面,这要求我们具备扎实的理论基础和实践经验。通过理解和实现这类数据结构,我们可以更好地理解和优化数据存储系统,提高程序的...