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); } } 

import java.util.ArrayList;import java.util.LinkedList;import java.util.List;/* * Author: Robert Liu */public class BTree<E extends Comparable<E>> {private BTNode root = null;private int t;private final int fullNum;public BTree(int t) {this.t = t;fullNum = 2 * t - 1;}private final BTNode NullBTNode = new BTNode();private class BTNode {private int number = 0;private List<E> values = new ArrayList<E>();private List<BTNode> children = new ArrayList<BTNode>();private boolean isLeaf = false;E getKey(int i) {return values.get(i);}BTNode getChildren(int i) {return children.get(i);}void AddKey(int i, E element) {values.add(i, element);}void removeKey(int i) {values.remove(i);}void AddChildren(int i, BTNode c) {children.add(i, c);}void removeChildren(int i) {children.remove(i);}boolean isFull() {if (number == fullNum)return true;return false;}int getSize() {return values.size();}boolean isNull() {return (this == NullBTNode);}@Overridepublic String toString() {if (number == 0)return "NullNode";StringBuilder sb = new StringBuilder();sb.append("[N: " + number + "] [values: ");for (E e : values) {sb.append(e + ", ");}sb.append(" ] [ children: ");for (BTNode bNode : children) {if (bNode == NullBTNode)sb.append(bNode + ", ");elsesb.append("NotNullNode" + ", ");}sb.append("] [childrenSize: " + children.size());sb.append("] [ isLeaf: " + isLeaf);sb.append("]");return sb.toString();}}// Generate the root nodeprivate void constructRoot(E elem) {root = new BTNode();root.number = 1;root.AddKey(0, elem);root.isLeaf = false;}private void addElemToNode(BTNode node, E element, int i) {node.AddKey(i, element);node.number++;node.AddChildren(i, NullBTNode);}public void insertElem(E elem) {if (root == null) {// The first nodeconstructRoot(elem);root.isLeaf = true;root.AddChildren(0, NullBTNode);root.AddChildren(1, NullBTNode);return;}BTNode curNode = root;if (root.isFull()) {// Extend the rootconstructRoot(curNode.getKey(t - 1));// Get new nodeBTNode newNode = getExtendedNode(curNode);// Process old full nodeprocessFullNode(curNode);// Process rootroot.AddChildren(0, curNode);root.AddChildren(1, newNode);return;}int i = 0;BTNode childNode = null;// Find the node to insertwhile (true) {while ((i < curNode.getSize())&& (elem.compareTo(curNode.getKey(i)) > 0)) {i++;}childNode = curNode.getChildren(i);if (childNode.isFull()) {// Split the node// Add the element to parentcurNode.number++;curNode.AddKey(i, childNode.getKey(t - 1));// New node for extensionBTNode newNode = getExtendedNode(childNode);// Process old full nodeprocessFullNode(childNode);// Add the new node for parent referencecurNode.AddChildren(i + 1, newNode);// Down to low layerif (elem.compareTo(curNode.getKey(i)) < 0) {curNode = childNode;} else {curNode = newNode;}i = 0;continue;}// Down to child nodeif (!childNode.isNull()) {curNode = childNode;i = 0;continue;}// Insert the element in current nodeaddElemToNode(curNode, elem, i);return;}}private BTNode getExtendedNode(BTNode fullNode) {BTNode newNode = new BTNode();newNode.number = t - 1;newNode.isLeaf = fullNode.isLeaf;for (int i = 0; i < t; i++) {if (i != t - 1) {newNode.AddKey(i, fullNode.getKey(t + i));}newNode.AddChildren(i, fullNode.getChildren(t + i));}return newNode;}// Should be called after calling getExtendedNode()private void processFullNode(BTNode fullNode) {fullNode.number = t - 1;for (int i = t - 1; i >= 0; i--) {fullNode.removeKey(t + i - 1);fullNode.removeChildren(t + i);}}@Overridepublic String toString() {if (root == null)return "NULL";StringBuilder sb = new StringBuilder();LinkedList<BTNode> queue = new LinkedList<BTNode>();queue.push(root);BTNode tem = null;while ((tem = queue.poll()) != null) {for (BTNode node : tem.children) {if (!node.isNull())queue.offer(node);}sb.append(tem.toString() + "\n");}return sb.toString();}public static void main(String[] args) {BTree<Character> tree = new BTree<Character>(3);System.out.println(tree);Character[] cL = { 'D', 'E', 'F', 'A', 'C', 'B', 'Z', 'H', 'I', 'J' };for (int i = 0; i < cL.length; i++) {tree.insertElem(cL[i]);System.out.println("After insert the: " + cL[i]);System.out.println(tree);}}output===================NULLAfter insert the: D[N: 1] [values: D,  ] [ children: NullNode, NullNode, ] [childrenSize: 2] [ isLeaf: true]After insert the: E[N: 2] [values: D, E,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]After insert the: F[N: 3] [values: D, E, F,  ] [ children: NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 4] [ isLeaf: true]After insert the: A[N: 4] [values: A, D, E, F,  ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 5] [ isLeaf: true]After insert the: C[N: 5] [values: A, C, D, E, F,  ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 6] [ isLeaf: true]After insert the: B[N: 1] [values: D,  ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false][N: 2] [values: A, C,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true][N: 2] [values: E, F,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true]After insert the: Z[N: 1] [values: D,  ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false][N: 2] [values: A, C,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true][N: 3] [values: E, F, Z,  ] [ children: NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 4] [ isLeaf: true]After insert the: H[N: 1] [values: D,  ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false][N: 2] [values: A, C,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true][N: 4] [values: E, F, H, Z,  ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 5] [ isLeaf: true]After insert the: I[N: 1] [values: D,  ] [ children: NotNullNode, NotNullNode, ] [childrenSize: 2] [ isLeaf: false][N: 2] [values: A, C,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true][N: 5] [values: E, F, H, I, Z,  ] [ children: NullNode, NullNode, NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 6] [ isLeaf: true]After insert the: J[N: 2] [values: D, H,  ] [ children: NotNullNode, NotNullNode, NotNullNode, ] [childrenSize: 3] [ isLeaf: false][N: 2] [values: A, C,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true][N: 2] [values: E, F,  ] [ children: NullNode, NullNode, NullNode, ] [childrenSize: 3] [ isLeaf: true][N: 3] [values: I, J, Z,  ] [ children: NullNode, NullNode, NullNode, NullNode, ] [childrenSize: 4] [ isLeaf: true]