二叉树的概念
1.所有非叶子结点至多拥有两个儿子（Left和Right）；
2.所有结点存储一个关键字；
3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；
如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；
如：
但B树在经过多次插入与删除后，有可能导致不同的结构：
右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；
实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略；
下面是代码实现
节点类
package com.wzg.tree.btree;
/**
* @author 作者 王志刚
* @version 创建时间：2016年12月16日 下午1:44:28
* @Description: Btree node
*/
public class TreeNode<K,V> {
private K key;
private V value;
private TreeNode<K,V> parent;
private TreeNode<K,V> left;
private TreeNode<K,V> right;
public TreeNode(K key, V value){
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public TreeNode<K, V> getParent() {
return parent;
}
public void setParent(TreeNode<K, V> parent) {
this.parent = parent;
}
public TreeNode<K, V> getLeft() {
return left;
}
public void setLeft(TreeNode<K, V> left) {
this.left = left;
}
public TreeNode<K, V> getRight() {
return right;
}
public void setRight(TreeNode<K, V> right) {
this.right = right;
}
}
二叉树实现类
package com.wzg.tree.btree;
import java.util.Comparator;
import java.util.Iterator;
/**
* @author 作者 王志刚
* @version 创建时间：2016年12月16日 下午2:58:23
* @Description:二叉树实现
*/
public class BtreeMap<K, V> {
private TreeNode<K, V> root = null;
private Comparator<? super K> comparator = null;
public BtreeMap(){}
public BtreeMap(Comparator<? super K> comp) throws Exception{
this.comparator = comp;
}
/**
* @author 作者 王志刚
* @Description:put
*/
public void put(K key, V value){
TreeNode<K, V> pnode = null;
if(root == null){ //第一个节点作为根节点
pnode = new TreeNode<K, V>(key, value);
pnode.setKey(key);
pnode.setValue(value);
root = pnode;
return ;
}else{
put(key, value, root);
}
}
/**
* @author 作者 王志刚
* @Description:迭代查找，并put入正确的位置
*/
public void put(K key, V value, TreeNode<K, V> pnode){
if(compare(pnode.getKey(), key) < 0){ //父节点的键小于放入节点的键，将放入的元素置于父节点的右节点
if(pnode.getRight() == null){
TreeNode<K, V> child = new TreeNode<K, V>(key, value);
child.setParent(pnode);
pnode.setRight(child);
}else{
put(key, value, pnode.getRight());
}
}else if(compare(pnode.getKey(), key) > 0){ //父节点的键大于放入节点的键，将放入的元素置于父节点的左节点
if(pnode.getLeft() == null){
TreeNode<K, V> child = new TreeNode<K, V>(key, value);
child.setParent(pnode);
pnode.setLeft(child);
}else{
put(key, value, pnode.getLeft());
}
}else{
pnode.setValue(value); //父节点的键等于放入节点的键，重置父节点的值
}
}
/**
* @author 作者 王志刚
* @Description:get
*/
public V get(K key){
TreeNode<K, V> pnode = root;
while(pnode != null){ //“二分查找”对应的值----二分查找用词可能不确切，但只要左右节点数差不多，性能接近二分查找
if(compare(pnode.getKey(), key) < 0){
pnode = pnode.getRight();
}else if(compare(pnode.getKey(), key) > 0){
pnode = pnode.getLeft();
}else{
return pnode.getValue();
}
}
return null;
}
/**
* @author 作者 王志刚
* @Description:B树节点比较方法
*/
private final int compare(K k1, K k2) {
return comparator == null ? ((Comparable<? super K>) k1).compareTo((K) k2) : comparator.compare((K) k1, (K) k2);
}
/**
* @author 作者 王志刚
* @Description:获取最左边的节点
*/
private final TreeNode<K,V> getLastLeftNode() {
TreeNode<K,V> lastLeft = root;
if (lastLeft != null)
while (lastLeft.getLeft() != null)
lastLeft = lastLeft.getLeft();
return lastLeft;
}
/**
* @author 作者 王志刚
* @Description:B树迭代器
*/
private class EntryIterator implements Iterator<TreeNode<K,V>> {
TreeNode<K,V> next = null;
public EntryIterator(TreeNode<K,V> lastLeft){
next = lastLeft;
}
@Override
public boolean hasNext() {
return next != null;
}
@Override
public TreeNode<K,V> next() {
TreeNode<K,V> e = next;
next = getNext(e);
return e;
}
/**
* @author 作者 王志刚
* @Description:返回下个节点
*/
private TreeNode<K,V> getNext(TreeNode<K,V> tn){
if (tn == null){
return null;
} else if(tn.getRight() == null){
TreeNode<K,V> nextNode = tn.getParent();
TreeNode<K,V> ch = tn;
//最右侧树节点往上翻
//最右节点的下个节点需往上查寻到交叉节点处（最后会到根节点，根节点的下个节点就是null）
while(nextNode != null && nextNode.getRight() == ch){
ch = nextNode;
nextNode = nextNode.getParent();
}
return nextNode;
}else{
TreeNode<K,V> nextNode = tn.getRight();
while(nextNode.getLeft() != null){
nextNode = nextNode.getLeft();
}
return nextNode;
}
}
}
/**
* @author 作者 王志刚
* @Description:返回B树的迭代器
*/
public Iterator<TreeNode<K,V>> iterator(){
return new EntryIterator(getLastLeftNode());
}
public void testprint(){
System.out.println(root.getKey());
System.out.println(root.getLeft().getKey() + "------" + root.getRight().getKey());
System.out.print(root.getLeft().getLeft().getKey() + "------" + root.getLeft().getRight().getKey());
System.out.print(" ");
System.out.print(root.getRight().getLeft().getKey() + "------" + root.getRight().getRight().getKey());
System.out.println("----");
System.out.println(root.getLeft().getLeft().getLeft().getKey());
}
public static void main(String[] args) {
BtreeMap<Integer, Integer> bm = new BtreeMap<Integer, Integer>();
bm.put(6, 6);
bm.put(4, 4);
bm.put(9, 9);
bm.put(2, 2);
bm.put(7, 7);
bm.put(10, 10);
bm.put(5, 5);
bm.put(2, 2);
bm.testprint();
System.out.println("\n 测试get");
System.out.println(bm.get(6));
System.out.println(bm.get(9));
System.out.println(bm.get(4));
System.out.println("\n 测试迭代器");
Iterator<TreeNode<Integer, Integer>> i = bm.iterator();
while(i.hasNext()){
System.out.println(i.next().getKey());
}
}
}