每个节点最多可以存三个数据项
不存在空节点
叶子结点可以有数据项而没有子节点
数据总是插入叶节点中
有一个数据项的节点总是有两个子节点
有两个数据项的节点总是有三个子节点
有三个数据项的节点总是有四个子节点
//数据项 public class DataItem { public long dData; public DataItem(long dd) { dData=dd; } public void displayNode() { System.out.print("/"+dData); } }
//节点 public class Node { public static final int order=4;//最多有四个子节点,三个数据项，所以即数据项数组最大值order-1，子节点是order private int numItems;//当前数据项个数 private Node parent;//父节点 private Node[] childArray=new Node[order];//子节点数组 private DataItem[] itemArray=new DataItem[order-1];//数据项数组 //根据下标取子节点数组中某个子节点 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); } //加入子节点(将对应的子节点放到数组中，childNum为数组中的索引)双向的 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; } //查找当前节点key数据项 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; } //插入数据项 public int insertItem(DataItem newItem) { numItems++;//插入加1 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;//直接跳出循环，返回插入的位置 } } } //如果没找到比它小的，都比它大，最后在0这个位置插入数据项 //插入的位置是0 itemArray[0]=newItem; return 0; } //删除数据项 public DataItem remove() {//直接删最后一个 DataItem temp=itemArray[numItems-1]; itemArray[numItems-1]=null; numItems--; return temp; } //显示 public void display() { for(int j=0;j<numItems;j++) itemArray[j].displayNode(); System.out.println("/");//全部输出之后，换行，每个节点作为一行输出 } }
public class Tree234 { Node root=new Node(); //查找数据 public int find(long key) { Node curNode=root; int childNumber; while(true) { if((childNumber=curNode.findItem(key))!=-1) return childNumber;//找到了，返回位置 else if(curNode.isLeaf())//如果上面没有找到，且是叶子节点，就没法继续往下找了。找不到 return -1;//没有找到 else curNode=getNextChild(curNode,key);//如果不是叶子结点，就在它的某个子节点中找 } } //获取theNode的子节点中要寻找的子节点 public Node getNextChild(Node theNode,long theValue) { int j; int numItems=theNode.getNumItems();//根据theNode的数据项个数判断节点个数 for(j=0;j<numItems;j++) {//循环节点的数据项 if(theValue<theNode.getItem(j).dData)//根据数据项的比对，来判断下一个比较的子节点 return theNode.getChild(j); } return theNode.getChild(j); } //新增数据项 public void insert (long dValue) { Node curNode=root; DataItem tempItem=new DataItem(dValue); while(true) {//找到需要插入的节点 if(curNode.isFull()) {//如果需要插入的当前节点满了，就需要拆分 split(curNode);//拆分为一个新的(中间的数做新的根，左数值为左边子节点作为，右数值右边子节点) //重新定义curNode curNode=curNode.getParent(); curNode=getNextChild(curNode,dValue); }else if(curNode.isLeaf()) {//如果是叶子结点，而且没满，等循环结束，插入 break;//找到节点 }else//如果不是叶子结点，找到需要插入的叶子结点 curNode=getNextChild(curNode,dValue); } curNode.insertItem(tempItem);//插入到当前节点中 } //拆分 public void split(Node thisNode) { DataItem itemB,itemC; Node parent,child2,child3;//父节点是中间值得来的，childe2和child3是保存该节点的子节点 int itemIndex; //将当前节点的数据项数组删除两个，子节点数组就得删除两个 itemC=thisNode.remove();//删除当前节点最大数据项 itemB=thisNode.remove();//删除第二大的,中间值 child2=thisNode.disconnectChild(2);//删除当前节点的子节点2 child3=thisNode.disconnectChild(3);//删除当前节点的子节点3 //删除后thisNode就是值为索引为0的，还有索引为0，1的子节点 Node newRight=new Node();//最大值的节点 //插入parent（中间值） if(thisNode==root) {//如果当前节点是根节点 //创建新的根 root=new Node(); parent=root; root.connectChild(0, thisNode);//加入子节点thisNode于0位置 }else //如果不是根 parent=thisNode.getParent(); //插入itemB(插入根的值) itemIndex=parent.insertItem(itemB);//插入数据项，返回插入的位置 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); newRight.connectChild(0, child2); newRight.connectChild(1, child3); } //显示树 public void display() { recDisplayTree(root,0,0);//第0层，当前节点存在的位置是父节点的节点数组的0位置 } //显示树（递归函数） //childNumber为当前节点在父节点子节点数组中的索引数 private void recDisplayTree(Node thisNode,int level,int childNumber) { System.out.print("leve="+level+"child="+childNumber+" "); thisNode.display(); 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; } } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Test { public static void main(String[] agrs) 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 show,isnert,find:"); int choice=getchar(); switch(choice){ case's': theTree.display(); break; case 'i': System.out.print("Enter value to insert:"); value=getInt(); theTree.insert(value); break; case 'f': System.out.println("Enter value to find:"); value=getInt(); int found=theTree.find(value); if(found!=-1) { System.out.print("Found "+value); }else System.out.print("not"+value); break; default: System.out.println("无效的输入"); } } } public static String getString()throws IOException{ InputStreamReader isr=new InputStreamReader(System.in); BufferedReader br=new BufferedReader(isr); return br.readLine(); } public static char getchar() throws IOException{ return getString().charAt(0); } public static int getInt() throws IOException{ String s=getString(); return Integer.parseInt(s); } }