`

java实现B树(二叉树)插入,删除

阅读更多

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树算法Java实现代码

    在计算机科学中,B树(B-tree)是一种自平衡的多路查找树,它的设计目的是为了优化磁盘或网络存储环境下的数据检索效率。...在Java中实现B树需要理解其数据结构特点,并适当地处理插入、查找和删除操作,确保树的平衡。

    B树的Java实现

    在Java中实现B树,我们需要理解其基本概念、结构和操作,包括插入、删除和查找等。** B树的主要特征包括: 1. **每个节点可以有多个子节点**,与二叉树不同,B树的节点可以有多个分支,通常为2的幂次方,如2、4、8...

    二叉树实现源码(C、C++、JAVA)

    不平衡的二叉树可能会导致性能下降,因此有自平衡二叉树如AVL树和红黑树等,它们在插入或删除后会通过旋转操作保持树的高度平衡,从而确保搜索效率。 此外,二叉树还可以扩展为更复杂的数据结构,如B树和B+树,常...

    Javatree java树结构

    在Java中,我们可以使用类和对象来实现树结构。例如,定义一个Node类,包含数据和指向子节点的引用。为了支持树的各种操作,我们可以编写对应的函数,如insertNode()、deleteNode()、searchNode()等。对于特定类型...

    B树实现的文件索引 java版

    在这个项目“B树实现的文件索引 java版”中,我们探讨的是如何利用Java语言来实现B树在文件索引中的应用。 B树是一种多路搜索树,它的每个节点可以有多个子节点,通常比二叉树更适合处理大量的数据。这种数据结构的...

    二叉树、B树、B+树、红黑树

    - **红黑树的优点**:相比于AVL树等其他自平衡二叉树,红黑树在插入和删除操作上的性能更加稳定,因为任何不平衡状态都可以在最多三次旋转内解决。 - **B+树的优势**:在磁盘存储中,由于所有的数据都存储在叶子节点...

    广工数据结构课程设计大作业-平衡二叉树-Java实现(数据结构期末)

    平衡二叉树是一种特殊的二叉搜索树,它的左右子树的高度差不超过1,从而保证了树的平衡性,进一步提高了查找、插入和删除操作的效率。 平衡二叉树的主要类型有AVL树和红黑树等。AVL树是最早被提出的自平衡二叉搜索...

    二叉树基础知识 包含ppt 和示例代码

    示例代码通常会涵盖这些基本操作的实现,例如在Python中,你可以使用类来表示二叉树节点,然后实现插入、删除和查找的方法。在插入操作中,你需要比较新节点的值与当前节点的值,决定将其插入左子树还是右子树。删除...

    二叉树非递归实现源码(C、C++、JAVA)

    本资源提供了C、C++和JAVA三种语言实现的二叉树非递归操作源码,涵盖了基本的遍历、插入和删除等操作。下面我们将详细讨论这些知识点。 1. **非递归遍历**: - **前序遍历**:访问根节点 -&gt; 左子树 -&gt; 右子树。非...

    java树形结构

    在Java中,实现树形结构通常有两种主要方式:通过继承自Java集合框架的`TreeSet`或`TreeMap`类,或者自定义节点类来构建树。`TreeSet`和`TreeMap`利用红黑树(Red-Black Tree)实现,提供了自动排序的功能。而自定义...

    KD树java实现

    - **`KDTree&lt;S&gt;`**:KD树的主要实现类,提供了构建树、插入、删除、查询等功能。 - **`KDDistance&lt;S&gt;`**:接口类,定义了计算两点间距离的方法。 ##### 3. `KDTreeNode&lt;S&gt;`类分析 - **属性**: - `left` 和 `right...

    java 树的数据结构 红黑树的实现 学习路线

    本文将深入探讨Java中树的数据结构,特别是红黑树的实现,以及如何构建一个有效的学习路线。 首先,让我们从"树的基本概念"开始。树是一种非线性的数据结构,它由节点(或称为顶点)和边构成,每个节点可以有零个或...

    树与二叉树代码模板.zip

    压缩包内的"树与二叉树代码模板.doc"可能包含了这些基本操作的示例代码,例如用C++、Java或Python实现。通过这些模板,你可以快速理解并实践如何在实际项目中使用树和二叉树。 在学习和应用树与二叉树时,还需要...

    BT.rar_b tree in java_b tree java_b-tree_tree

    6. `BTree.java`:这是B树的源代码文件,应包含B树的定义和主要方法,比如插入、删除、搜索等功能的实现。 7. `www.pudn.com.txt`:这可能是一个文本文件,可能包含了有关B树的额外说明、教程链接或其他资源,供...

    最简单的B树

    B树(B-tree)是一种自平衡的树数据结构,广泛应用于数据库和文件系统中,因为它能够保持数据排序,使得对数据的搜索、插入和删除操作的平均时间复杂度为O(log n)。B树的主要特点是每个节点可以有多个子节点,且每个...

    JAVA编写的二叉树源代码(输入输出都有)

    通过阅读和分析源代码,开发者可以学习到如何在JAVA中创建、插入、删除二叉树节点,以及如何实现各种遍历算法。 7. **文件名**:“BinTree”可能是源代码文件的名字,可能包含了二叉树类的定义,以及实现输入输出...

    高一凡代码-第6章 树和二叉树.rar

    此外,树和二叉树在实际应用中有很多变体,如B树、B+树、Trie树等,它们在数据库索引、文件系统和网络路由等领域发挥着重要作用。 "高一凡代码-第6章 树和二叉树.rar"这个压缩包可能包含了这些概念的实例代码,帮助...

    二叉树建立和查找 数据结构

    在计算机科学领域,数据结构是组织和管理大量...通过实践这些基本操作,你可以进一步探索更高级的主题,如平衡二叉树(AVL树、红黑树)、二叉堆、B树和B+树等,这些都广泛应用于数据库索引、优先队列和文件系统等领域。

    JAVA制作树TREE

    - 自定义实现树结构,需要创建表示节点的类,并提供插入、删除、查找等方法。 以上内容涵盖了Java中制作树的基本概念、类型、遍历方式、操作和实际应用。在实践中,理解这些知识点并能够灵活运用是构建和操作树的...

    java 树 tree

    Java提供了多种方式来实现和操作树结构,其中最常见的是使用Java集合框架中的`java.util.TreeSet`和`java.util.TreeMap`,以及`java.awt.tree.TreeModel`和`javax.swing.JTree`用于图形用户界面的树视图。...

Global site tag (gtag.js) - Google Analytics