Java数据结构和算法（十二）——2-3-4树详解编程语言

package com.ys.tree.twothreefour; 
 
public class Tree234 { 
	private Node root = new Node() ; 
	/*public Tree234(){ 
		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); 
			} 
		} 
	} 
	 
	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); 
			} 
		} 
		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.getParent(); 
				curNode = getNextChild(curNode, dValue); 
			}else if(curNode.isLeaf()){//当前节点是叶节点 
				break; 
			}else{ 
				curNode = getNextChild(curNode, dValue); 
			} 
		}//end while 
		curNode.insertItem(tempItem); 
	} 
	 
	public void split(Node thisNode){ 
		DataItem itemB,itemC; 
		Node parent,child2,child3; 
		int itemIndex; 
		itemC = thisNode.removeItem(); 
		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); 
		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 displayTree(){ 
		recDisplayTree(root,0,0); 
	} 
	private void recDisplayTree(Node thisNode,int level,int childNumber){ 
		System.out.println("levle="+level+" child="+childNumber+" "); 
		thisNode.displayNode(); 
		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; 
			} 
		} 
	} 
 
	//数据项 
	class DataItem{ 
		public long dData; 
		public DataItem(long dData){ 
			this.dData = dData; 
		} 
		public void displayItem(){ 
			System.out.println("/"+dData); 
		} 
	} 
	 
	//节点 
	class Node{ 
		private static final int ORDER = 4; 
		private int numItems;//表示该节点有多少个数据项 
		private Node parent;//父节点 
		private Node childArray[] = new Node[ORDER];//存储子节点的数组，最多有4个子节点 
		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]; 
		} 
		//判断节点的数据项是否满了（最多3个） 
		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; 
		} 
		 
		//将数据项插入到节点 
		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; 
					} 
				} 
			} 
			//如果都为空，或者都比待插入的数据项大，则将待插入的数据项放在节点第一个位置 
			itemArray[0] = newItem; 
			return 0; 
		} 
		//移除节点的数据项 
		public DataItem removeItem(){ 
			DataItem temp = itemArray[numItems-1]; 
			itemArray[numItems-1] = null; 
			numItems--; 
			return temp; 
		} 
		//打印节点的所有数据项 
		public void displayNode(){ 
			for(int j = 0 ; j < numItems ; j++){ 
				itemArray[j].displayItem(); 
			} 
			System.out.println("/"); 
		} 
	} 
 
	 
}