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);
}
}
分享到:
相关推荐
二叉树的搜索、插入和删除时间取决于树的高度。在最坏的情况下,高度是O(n)如果一棵树是完全平衡的,也就是说。,一个完整的二叉树——它的高度是log n。是的。但是这样做将是昂贵的。折衷的办法是保持树的平衡,也...
红黑树创建,插入,删除操作代码。包括创建,插入操作,删除操作,代码有详细的注释,java代码实现。
本演示程序用JAVA编写,完成树的生成,任意位置的插入、删除,以及遍历二叉树中的结点,查找和修改树中元素的值。 ① 输入的形式和输入值的范围:插入元素时需要输入插入的位置和元素的值;删除元素时输入删除元素的...
C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07...35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
.算法与数据结构基本概念 (1)数据、数据对象和...(3)散列表的插入和删除 6.算法分析与设计基础 (1)分治与递归的关系 (2)贪心算法的思想 (3)回溯与分支限界算法的比较 (4)算法时间和空间复杂度的简单分析
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程...
简介 第1章 综述 数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 ...Java中数组的基础知识 ...附录B 进一步学习 附录C 问题答案