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,
;
newTree.insert(9, 9);
newTree.insert(7, 7);
newTree.delete(1);
newTree.inOrder(newTree.root);
}
}
分享到:
相关推荐
数据结构 二叉排序树 二叉搜索树 java swing图形界面实现
红黑树、二叉平衡树、二叉排序树的java实现,做了泛型封装,可以装任何对象,其中还附带工具类,可以友好一点地打印树,还有各种遍历树方法的递归实现和非递归实现。
基于JAVA实现的常用数据结构代码,JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等
二叉数,二叉搜索树,红黑树,AVL树,B树,B+树,B*树,树之间的关系,各类树的主要应用,哈夫曼树的构造过程
二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章 红...
二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树(BalancedBinarySearchTree、BBST) AVL树(AVLTree)、红黑树(RebBlackTree) B树(B-Tree) 集合(TreeSet)、映射(TreeMap) ...
本文实例讲述了javascript二叉搜索树实现方法。分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉;而且左分叉节点的值 < 右分叉节点的值 。 特点:插入节点、找最大/最小...
二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章...
Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切? 小...
第十八章二叉搜索树 第十九章集与映射 第二十章有序集与映射的实现 第二十一章实现映射的散列法 第二十二章堆 第二十三章位数与文件压缩 第二十四章图与路径 第二十五章图算法 第二十六章图的实现 第二十七章平衡的...
二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度。因此二叉树应该尽量的矮,即左右节点尽量平衡。 二叉搜索树的构造 要构造二叉搜索树,首先要构造二叉树的节点...
Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切? 小结 问题 实验...
界面操作二叉树的查找,并可观察结果。是桌面程序
字典ABB 工作表7.算法和数据结构。 使用二叉搜索树的单词词典
红黑树是一种自平衡二叉搜索树,排序时间介于数组和链表之间。链表的排序时间较长,因为它需要通过指针遍历节点来进行排序。 接下来,我们测试性能。我们使用相同的随机整数数组,并分别将其转换为数组、链表和红黑...
Java 数据结构目录 整理一下。。。 【动态扩容数组】动态扩容数组 ArrayList实现源码(Java、C++) 【链表List】单向链表 ...【二叉搜索树BST】二叉搜索树 BST 实现源码 【AVL树】AVLTree 实现源码 【红黑树RBTree】
Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切? ...
B树 B树是一种自平衡树数据... B树是二叉搜索树的概括,一个节点可以有两个以上的子节点。 与自平衡二进制搜索树不同,B树非常适合于读写相对较大的数据块(例如磁盘)的存储系统。 它通常在数据库和文件系统中使用。
数据结构与算法笔记+LeetCode经典例题分析。...其中包括八大排序算法、动态规划背包问题、深度优先搜索、广度优先搜索、队列、优先队列、栈、并查集、树、二叉树、二叉搜索树、AVL平衡二叉树等等。
一个网络应用程序,可帮助可视化各种二叉搜索树及其操作。 由于过时 Java 小程序的激增令人沮丧,因此专门设计为 UPenn 的 CIS121 数据结构课程的工具。 此实现仅使用 Javascript 和 CSS(AngularJS、D3、CSS)运行...