平衡树，子节点数目可以达到4个
特点
若父节点中存有1个数据项，则必有2个子节点。
若父节点中存有2个数据项，则必有3个子节点。
若父节点中存有3个数据项，则必有4个子节点。
构造
插入数据：
未满节点直接插入
满节点 ABC 分裂 A不变 B到父节点 C到右侧
代码实现
class Node
{
private static final int ORDER = 4;
private int numItems;//节点中实际存储的数据项数目，其值一定不大于3
private Node parent;
private Node childArray[] = new Node[ORDER];//子节点数组
private DataItem itemArray[] = new DataItem[ORDER-1];//存储数据项数组
//-------------------------------------------------------------
// 把参数中的节点作为子节点，与当前节点进行连接
public void connectChild(int childNum, Node child)
{
childArray[childNum] = child;
if(child != null)
child.parent = this;//当前节点作为父节点
}
//-------------------------------------------------------------
// 断开参数确定的节点与当前节点的连接，这个节点一定是当前节点的子节点。
public Node disconnectChild(int childNum)
{
Node tempNode = childArray[childNum];
childArray[childNum] = null; //断开连接
return tempNode;//返回要这个子节点
}
//-------------------------------------------------------------
public Node getChild(int childNum)//获取相应的子节点
{ return childArray[childNum]; }
//-------------------------------------------------------------
public Node getParent()//获取父节点
{ return parent; }
//-------------------------------------------------------------
public boolean isLeaf()//是否是叶结点
{ return (childArray[0]==null) ? true : false; }//叶结点没有子节点
//-------------------------------------------------------------
public int getNumItems()//获取实际存储的数据项数目
{ return numItems; }
//-------------------------------------------------------------
public DataItem getItem(int index) // 获取具体的数据项
{ return itemArray[index]; }
//-------------------------------------------------------------
public boolean isFull()//该节点是否已满
{ return (numItems==ORDER-1) ? true : false; }
//-------------------------------------------------------------
public int findItem(long key) // 查找
{
for(int j=0; j<ORDER-1; j++) // 遍历数组
{
if(itemArray[j] == null) // 数组未满，未找到
break;
else if(itemArray[j].dData == key)
return j;
}
return -1;
} // end findItem
//-------------------------------------------------------------
public int insertItem(DataItem newItem)//节点未满的插入
{
numItems++;
long newKey = newItem.dData; // 获得关键字
for(int j=ORDER-2; j>=0; j--) // 因为节点未满，所以从倒数第二项向前查找
{
if(itemArray[j] == null) // 没存数据
continue;
else
{
long itsKey = itemArray[j].dData;//获得关键字
if(newKey < itsKey) //插入位置在其前面，但未必相邻
itemArray[j+1] = itemArray[j]; //当前数据项后移
else
{
itemArray[j+1] = newItem; // 在其后位置插入
return j+1; // 返回插入的位置下标
} // new item
} // end else (not null)
} // end for // shifted all items,
//若上述代码没有执行返回操作，那么这是空节点（只有初始时根是这个情况）
itemArray[0] = newItem; // insert new item
return 0;
} // end insertItem()
//-------------------------------------------------------------
public DataItem removeItem() // 移除数据项，从后向前移除
{
// 假设节点非空
DataItem temp = itemArray[numItems-1]; // 要移除的数据项
itemArray[numItems-1] = null; // 移除
numItems--; // 数据项数目减一
return temp; // 返回要移除的数据项
}
//-------------------------------------------------------------
public void displayNode() // format "/24/56/74/"
{
for(int j=0; j<numItems; j++)
itemArray[j].displayItem(); // "/56"
System.out.println("/"); // final "/"
}
//-------------------------------------------------------------
} // end class Node
////////////////////////////////////////////////////////////////
class Tree234
{
private Node root = new Node(); // 创建树的根
//-------------------------------------------------------------
//获取查找的下一个节点
public Node getNextChild(Node theNode, long theValue)
{
int j;
// 假设这个节点不是叶结点
int numItems = theNode.getNumItems();//获得当前节点的数据项数目
for(j=0; j<numItems; j++)
{
if( theValue < theNode.getItem(j).dData )
return theNode.getChild(j); // 返回相应的节点
} // end for
return theNode.getChild(j); // 此时j=numItems
}
//-------------------------------------------------------------
public int find(long key)
{
Node curNode = root;
int childNumber;
while(true)
{
if(( childNumber=curNode.findItem(key) ) != -1)//每次循环这句一定执行
return childNumber; // found it
else if( curNode.isLeaf() )//叶结点上也没找到
return -1; // can't find it
else // 不是叶结点，则继续向下查找
curNode = getNextChild(curNode, key);
} // end while
}
//-------------------------------------------------------------
// 插入数据项
public void insert(long dValue)
{
Node curNode = root;//当前节点标志
DataItem tempItem = new DataItem(dValue);//插入数据项封装
while(true)
{
if( curNode.isFull() ) // 是满节点
{
split(curNode); // 分裂
curNode = curNode.getParent(); // 回到分裂出的父节点上
// 继续向下查找
curNode = getNextChild(curNode, dValue);
} // end if(node is full)
//后面的操作中节点都未满，否则先执行上面的代码
else if( curNode.isLeaf() ) // 是叶结点，非满
break; // 跳出，直接插入
else
curNode = getNextChild(curNode, dValue);//向下查找
} // end while
curNode.insertItem(tempItem); // 此时节点一定不满，直接插入数据项，
} // end insert()
//-------------------------------------------------------------
public void split(Node thisNode) // 分裂
{
// 操作中节点一定是满节点，否则不会执行该操作
DataItem itemB, itemC;
Node parent, child2, child3;
int itemIndex;
itemC = thisNode.removeItem(); // 移除最右边的两个数据项，并保存为B和C
itemB = thisNode.removeItem(); //
child2 = thisNode.disconnectChild(2); // //断开最右边两个子节点的链接
child3 = thisNode.disconnectChild(3); //
Node newRight = new Node(); //新建一个节点，作为当前节点的兄弟节点
if(thisNode==root) // 是根
{
root = new Node(); // 新建一个根
parent = root; // 把新根设为父节点
root.connectChild(0, thisNode); // 连接父节点和子节点
}
else // 不是根
parent = thisNode.getParent(); // 获取父节点
itemIndex = parent.insertItem(itemB); // 把B插入父节点中，返回插入位置
int n = parent.getNumItems(); // 获得总数据项数目
for(int j=n-1; j>itemIndex; j--) //从后向前移除
{
Node temp = parent.disconnectChild(j); // 断开连接
parent.connectChild(j+1, temp); // 连接到新的位置
}
parent.connectChild(itemIndex+1, newRight);//连接到新位置
// 处理兄弟节点
newRight.insertItem(itemC); // 将C放入兄弟节点中
newRight.connectChild(0, child2); // 把子节点中最右边的两个连接到兄弟节点上
newRight.connectChild(1, child3); //
} // end split()
//-------------------------------------------------------------
// gets appropriate child of node during search for value
public void displayTree()
{
recDisplayTree(root, 0, 0);
}
//-------------------------------------------------------------
private void recDisplayTree(Node thisNode, int level,
int childNumber)
{
System.out.print("level="+level+" child="+childNumber+" ");
thisNode.displayNode(); // display this node
// call ourselves for each child of this node
int numItems = thisNode.getNumItems();
for(int j=0; j<numItems+1; j++)
{
Node nextNode = thisNode.getChild(j);
if(nextNode != null)
recDisplayTree(nextNode, level+1, j);
else
return;
}
} // end recDisplayTree()
//-------------------------------------------------------------\
} // end class Tree234
////////////////////////////////////////////////////////////////
import java.io.*;
class Tree234App
{
public static void main(String[] args) throws IOException
{
long value;
Tree234 theTree = new Tree234();
theTree.insert(50);
theTree.insert(40);
theTree.insert(60);
theTree.insert(30);
theTree.insert(70);
while(true)
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, or find: ");
char choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
int found = theTree.find(value);
if(found != -1)
System.out.println("Found "+value);
else
System.out.println("Could not find "+value);
break;
default:
System.out.print("Invalid entry\n");
} // end switch
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//-------------------------------------------------------------
} // end class Tree234App
////////////////////////////////////////////////////////////////