BTree
特征:
1.一个节点最多只有两个子节点,其中左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。
2.执行查找,插入,删除的时间复杂度都是:O(logN)。
3.遍历有中序,前序,后序。前,中和后只是在递归的时候先输出左子,自己或右子的顺序。可以通过中排序,按左子,自己,右子的顺序就是升序,反之则是降序。
4.最大值是树的右边底层叶子;最小值是左边底层叶子。
JAVA代码实现:
package org.acooly.datastructure.btree;
import java.util.Random;
/**
* 特征:一个节点的左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。
*
* @author zhangpu
*
*/
public class BinaryTree {
/** 根节点 */
private Node root;
/**
* 查找
*
* @param key
* @return
*/
public Node find(int key) {
if (root == null) {
return null;
}
Node current = root;
while (current.getKey() != key) {
if (key < current.getKey()) {
// 小于本节点在左边
current = current.getLeftNode();
} else {
// 大于等于本节点在右边
current = current.getRightNode();
}
if (current == null) {
// 搜索到最后叶子为空,表示没有找到
return null;
}
}
return current;
}
public Node getParent(int key) {
if (root == null) {
return null;
}
Node current = root;
Node parent = root;
while (current.getKey() != key) {
if (key < current.getKey()) {
// 小于本节点在左边
parent = current;
current = current.getLeftNode();
} else {
// 大于等于本节点在右边
parent = current;
current = current.getRightNode();
}
if (current == null) {
// 搜索到最后叶子为空,表示没有找到
return null;
}
}
return parent;
}
/**
* 插入
*
* @param key
* @param value
*/
public void insert(int key, Object value) {
Node node = new Node(key, value);
if (root == null) {
root = node;
return;
}
Node current = root;
while (true) {
if (key < current.getKey()) {
if (current.getLeftNode() == null) {
current.setLeftNode(node);
return;
} else {
current = current.getLeftNode();
}
} else {
if (current.getRightNode() == null) {
current.setRightNode(node);
return;
} else {
current = current.getRightNode();
}
}
}
}
/**
* 中遍历(升序)
*
* @param startNode
*/
public void inOrderAsc(Node startNode) {
if (startNode != null) {
inOrderAsc(startNode.getLeftNode());
System.out.println(startNode);
inOrderAsc(startNode.getRightNode());
}
}
/**
* 中遍历(降序)
*
* @param startNode
*/
public void inOrderDesc(Node startNode) {
if (startNode != null) {
inOrderDesc(startNode.getRightNode());
System.out.println(startNode);
inOrderDesc(startNode.getLeftNode());
}
}
/**
* 最大值 算法:树中最底层的右子叶
*
* @return
*/
public Node getMax() {
Node current = root;
while (current.getRightNode() != null) {
current = current.getRightNode();
}
return current;
}
/**
* 算法:树中最底层的左子叶
*
* @return
*/
public Node getMin() {
return getMin(root);
}
/**
* 指定节点的最小节点,如果指定节点为root,则是树的最小节点
*
* @param localRoot
* @return
*/
private Node getMin(Node localRoot) {
Node current = localRoot;
while (current.getLeftNode() != null) {
current = current.getLeftNode();
}
return current;
}
/**
* 删除节点存在3中情况 <li>目标节点是叶子:直接删除,置为null <li>
* 目标节点只有一个子节点:如果目标节点是在父节点的左边,直接使用子节点作为父节点的左子,反正则为右子。 <li>
* 目标节点有两个子节点:找到后继节点,作为目标节点父节点的对应子节点。(后继:目标节点子节点中大于目标节点最小的个。路径:目标节点右子的最小节点。)
*
* @param key
*/
public void delete(int key) {
Node target = find(key);
if (target == null) {
return;
}
boolean leftExsit = (target.getLeftNode() != null ? true : false);
boolean rightExsit = (target.getRightNode() != null ? true : false);
// 第一种情况,目标是叶子,直接设置为null
if (!leftExsit && !rightExsit) {
target = null;
return;
}
// 获得目标的父节点
Node parent = getParent(key);
Node child = null;
if (leftExsit != rightExsit) {
// 第二种情况:只有一个子
child = (leftExsit ? target.getLeftNode() : target.getRightNode());
} else {
// 第三种情况:有两个子
Node rightChild = target.getRightNode();
child = getMin(rightChild);
getParent(child.getKey()).setLeftNode(null);
child.setRightNode(rightChild);
}
if (parent == null) {
root = child;
target = null;
return;
}
if (parent.getLeftNode() != null && target.getKey() < parent.getLeftNode().getKey()) {
// 目标是父的左子
parent.setLeftNode(child);
} else {
// 目标是父的右子
parent.setRightNode(child);
}
target = null;
}
public Node getRoot() {
return root;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
Random random = new Random();
// INSERT
for (int i = 1; i <= 10; i++) {
int key = random.nextInt(100);
tree.insert(key, "value" + key);
}
int key = 0;
tree.insert(key, "value" + key);
System.out.println("TARGET key: " + key);
// FIND
System.out.println("FIND: " + tree.find(key));
// GETPARENT
System.out.println("PARENT: " + tree.getParent(key));
// MIX
System.out.println("MAX: " + tree.getMax());
// MIN
System.out.println("MIN: " + tree.getMin());
tree.delete(key);
System.out.println();
System.out.println("中遍历(升序):");
tree.inOrderAsc(tree.getRoot());
System.out.println("中遍历(降序):");
tree.inOrderDesc(tree.getRoot());
}
}
节点类:
package org.acooly.datastructure.btree;
/**
* BTree 节点
*
* @author zhangpu
*
*/
public class Node {
/** 节点KEY */
private int key;
private Object value;
/** 左子节点 */
private Node leftNode;
/** 右子节点 */
private Node rightNode;
public Node() {
super();
}
public Node(int key, Object value) {
super();
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(key) + "=" + value;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Node){
Node n = (Node)obj;
if(n.getKey() != getKey()){
return false;
}
}else{
return false;
}
return true;
}
}
分享到:
相关推荐
许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之...
数据结构关于二叉树的建立遍历以及应用二叉树进行编解码 实验要求 必做部分 1. 小明会按照前序的方式输入一棵二叉树。例如,输入$ACG##H##D##BE#I##F##的话,代表了下面这棵树: 2. 请分别按照前序、中序、后序...
C语言中文网 Go语言二叉树数据结构的应用 源码。一开始以为“btree”是golang的包呢。后来发现不是。又找以为是“https://github.com/google/btree.git”。发现还不是。这才想起来可能是自己写的包。绕了一圈子。 ...
实验四 二叉树基本操作的实现 二叉树概念及其存储结构 二叉链储存结构的二叉树基本操作 举例说明什么样的二叉树采用顺序存储,什么样的二叉树采用二叉链存储
从键盘输入二叉树先序序列,以二叉链表作为存储结构。 建立二叉树,求出二叉树的深度、结点总数和叶子结点数,并将遍历结果打印输出。 方法实现。查找给定结点的双亲、祖先和所有孩子节点。
先建立二叉树节点,有一个data数据域,left,right 两个指针域复制代码 代码如下:# -*- coding: utf – 8 – *- class TreeNode(object): def __init__(self, left=0, right=0, data=0): self.left = left self....
数据结构 二叉树 两种存储结构的优缺点 顺序存储可能会浪费空间(在非完全二叉树的时候),但是读取某个指定的节点的时候效 率比较高O(0) 链式存储相对二叉树比较大的时候浪费空间较少,但是读取某个指定节点的时候...
数据结构算法演示(Windows版) 使 用 手 册 一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法...
数据结构算法演示(Windows版) 使 用 手 册 一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行...
printf("二叉树创建数据结果:\n"); TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1); //TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1); if (TreeHeader==0) { printf("二叉树创建失败!\n"); return...
│ ├─平衡二叉树(二叉排序树的平衡旋转生成) │ │ 1.txt │ │ BBSTree.cpp │ │ BBSTree.h │ │ BiTree.cpp │ │ BiTree.h │ │ DElemType.cpp │ │ DElemType.h │ │ DSTable.cpp │ │ DSTable.h │ ...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
①初始化二叉树。 ②调用插入函数建立二叉排序树。 ③调用查找函数在二叉树中查找指定的结点。 ④调用删除函数删除指定的结点为,并动态地显删除结果。 */ #include #include #include //#include ...
/* 数据域 */ PBinTreeNode llink; /* 指向左子女 */ PBinTreeNode rlink; /* 指向右子女 */ }; typedef struct BinTreeNode *BinTree; typedef BinTree *PBinTree; typedef PBinTreeNode BNode; PBinTreeNode ...
数据结构实验报告 题目:二叉树 学 院 计算机学院 专 业 软件工程 年级班别 2010级 4 班 学 号 学生姓名 指导教师 成 绩 ____________________ 2012年6月 1、设计任务【Design Tasks】 完成二叉树的17中基本操作。...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
数据结构算法演示 1. 顺序表 (1)在顺序表中插入一个数据元素(ins_sqlist) (2)删除顺序表中一个数据元素(del_sqlist) (3)合并两个有序顺序表(merge_sqlist) 2. 链表 (1)创建一个单链表(Crt_LinkList) ...