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);
}
}
分享到:
相关推荐
在计算机科学中,B树(B-tree)是一种自平衡的多路查找树,它的设计目的是为了优化磁盘或网络存储环境下的数据检索效率。...在Java中实现B树需要理解其数据结构特点,并适当地处理插入、查找和删除操作,确保树的平衡。
在Java中实现B树,我们需要理解其基本概念、结构和操作,包括插入、删除和查找等。** B树的主要特征包括: 1. **每个节点可以有多个子节点**,与二叉树不同,B树的节点可以有多个分支,通常为2的幂次方,如2、4、8...
不平衡的二叉树可能会导致性能下降,因此有自平衡二叉树如AVL树和红黑树等,它们在插入或删除后会通过旋转操作保持树的高度平衡,从而确保搜索效率。 此外,二叉树还可以扩展为更复杂的数据结构,如B树和B+树,常...
在Java中,我们可以使用类和对象来实现树结构。例如,定义一个Node类,包含数据和指向子节点的引用。为了支持树的各种操作,我们可以编写对应的函数,如insertNode()、deleteNode()、searchNode()等。对于特定类型...
在这个项目“B树实现的文件索引 java版”中,我们探讨的是如何利用Java语言来实现B树在文件索引中的应用。 B树是一种多路搜索树,它的每个节点可以有多个子节点,通常比二叉树更适合处理大量的数据。这种数据结构的...
- **红黑树的优点**:相比于AVL树等其他自平衡二叉树,红黑树在插入和删除操作上的性能更加稳定,因为任何不平衡状态都可以在最多三次旋转内解决。 - **B+树的优势**:在磁盘存储中,由于所有的数据都存储在叶子节点...
平衡二叉树是一种特殊的二叉搜索树,它的左右子树的高度差不超过1,从而保证了树的平衡性,进一步提高了查找、插入和删除操作的效率。 平衡二叉树的主要类型有AVL树和红黑树等。AVL树是最早被提出的自平衡二叉搜索...
示例代码通常会涵盖这些基本操作的实现,例如在Python中,你可以使用类来表示二叉树节点,然后实现插入、删除和查找的方法。在插入操作中,你需要比较新节点的值与当前节点的值,决定将其插入左子树还是右子树。删除...
本资源提供了C、C++和JAVA三种语言实现的二叉树非递归操作源码,涵盖了基本的遍历、插入和删除等操作。下面我们将详细讨论这些知识点。 1. **非递归遍历**: - **前序遍历**:访问根节点 -> 左子树 -> 右子树。非...
在Java中,实现树形结构通常有两种主要方式:通过继承自Java集合框架的`TreeSet`或`TreeMap`类,或者自定义节点类来构建树。`TreeSet`和`TreeMap`利用红黑树(Red-Black Tree)实现,提供了自动排序的功能。而自定义...
- **`KDTree<S>`**:KD树的主要实现类,提供了构建树、插入、删除、查询等功能。 - **`KDDistance<S>`**:接口类,定义了计算两点间距离的方法。 ##### 3. `KDTreeNode<S>`类分析 - **属性**: - `left` 和 `right...
本文将深入探讨Java中树的数据结构,特别是红黑树的实现,以及如何构建一个有效的学习路线。 首先,让我们从"树的基本概念"开始。树是一种非线性的数据结构,它由节点(或称为顶点)和边构成,每个节点可以有零个或...
压缩包内的"树与二叉树代码模板.doc"可能包含了这些基本操作的示例代码,例如用C++、Java或Python实现。通过这些模板,你可以快速理解并实践如何在实际项目中使用树和二叉树。 在学习和应用树与二叉树时,还需要...
6. `BTree.java`:这是B树的源代码文件,应包含B树的定义和主要方法,比如插入、删除、搜索等功能的实现。 7. `www.pudn.com.txt`:这可能是一个文本文件,可能包含了有关B树的额外说明、教程链接或其他资源,供...
B树(B-tree)是一种自平衡的树数据结构,广泛应用于数据库和文件系统中,因为它能够保持数据排序,使得对数据的搜索、插入和删除操作的平均时间复杂度为O(log n)。B树的主要特点是每个节点可以有多个子节点,且每个...
通过阅读和分析源代码,开发者可以学习到如何在JAVA中创建、插入、删除二叉树节点,以及如何实现各种遍历算法。 7. **文件名**:“BinTree”可能是源代码文件的名字,可能包含了二叉树类的定义,以及实现输入输出...
此外,树和二叉树在实际应用中有很多变体,如B树、B+树、Trie树等,它们在数据库索引、文件系统和网络路由等领域发挥着重要作用。 "高一凡代码-第6章 树和二叉树.rar"这个压缩包可能包含了这些概念的实例代码,帮助...
在计算机科学领域,数据结构是组织和管理大量...通过实践这些基本操作,你可以进一步探索更高级的主题,如平衡二叉树(AVL树、红黑树)、二叉堆、B树和B+树等,这些都广泛应用于数据库索引、优先队列和文件系统等领域。
- 自定义实现树结构,需要创建表示节点的类,并提供插入、删除、查找等方法。 以上内容涵盖了Java中制作树的基本概念、类型、遍历方式、操作和实际应用。在实践中,理解这些知识点并能够灵活运用是构建和操作树的...
Java提供了多种方式来实现和操作树结构,其中最常见的是使用Java集合框架中的`java.util.TreeSet`和`java.util.TreeMap`,以及`java.awt.tree.TreeModel`和`javax.swing.JTree`用于图形用户界面的树视图。...