java实现多叉树

一：树节点的定义（TreeNode.java）

import java.util.List;
import java.util.ArrayList;
import java.io.Serializable;

public class TreeNode implements Serializable
{
private int parentId;
private int selfId;
protected String nodeName;
protected Object obj;
protected TreeNode parentNode;
protected List childList;

public TreeNode()
{
initChildList();
}

public TreeNode(TreeNode parentNode)
{
this.getParentNode();
initChildList();
}

public boolean isLeaf()
{
if(childList==null)
{
return true;
}
else
{
if(childList.isEmpty())
{
return true;
}
else
{
return false;
}
}
}

/*插入一个child节点到当前节点中*/
public void addChildNode(TreeNode treeNode)
{
initChildList();
childList.add(treeNode);
}

public void initChildList()
{
if(childList==null)
childList=new ArrayList ();
}

public boolean isValidTree()
{
return true;
}

/*返回当前节点的父辈节点集合*/
public List getElders()
{
List elderList=new ArrayList ();
TreeNode parentNode=this.getParentNode();
if(parentNode==null)
{
return elderList;
}
else
{
elderList.add(parentNode);
elderList.addAll(parentNode.getElders());
return elderList;
}
}

/*返回当前节点的晚辈集合*/
public List getJuniors()
{
List juniorList=new ArrayList ();
List childList=this.getChildList();
if(childList==null)
{
return juniorList;
}
else
{
int childNumber=childList.size();
for(int i=0;i {
TreeNode junior=childList.get(i);
juniorList.add(junior);
juniorList.addAll(junior.getJuniors());
}
return juniorList;
}
}

/*返回当前节点的孩子集合*/
public List getChildList() {
return childList;
}

/*删除节点和它下面的晚辈*/
public void deleteNode()
{
TreeNode parentNode=this.getParentNode();
int id=this.getSelfId();

if(parentNode!=null)
{
parentNode.deleteChildNode(id);
}
}

/*删除当前节点的某个子节点*/
public void deleteChildNode(int childId)
{
List childList=this.getChildList();
int childNumber=childList.size();
for(int i= 0 ; i < childNumber;i++)
{
TreeNode child=childList.get(i);
if(child.getSelfId()==childId)
{
childList.remove(i);
return;
}
}
}

/*动态的插入一个新的节点到当前树中*/
public boolean insertJuniorNode(TreeNode treeNode)
{
int juniorParentId=treeNode.getParentId();
if(this.parentId==juniorParentId)
{
addChildNode(treeNode);
return true;
}
else
{
List childList=this.getChildList();
int childNumber=childList.size();
boolean insertFlag;

for(int i=0;i {
TreeNode childNode= childList.get(i);
insertFlag=childNode.insertJuniorNode(treeNode);
if(insertFlag==true)
return true;
}
return false;
}
}

/*找到一颗树中某个节点*/
public TreeNode findTreeNodeById(int id)
{
if(this.selfId==id)
return this;
if(childList.isEmpty() || childList==null)
{
return null;
}
else
{
int childNumber=childList.size();
for(int i= 0 ; i < childNumber;i++)
{
TreeNode child=childList.get(i);
TreeNode resultNode=child.findTreeNodeById(id);
if(resultNode!=null)
{
return resultNode;
}
}
return null;
}
}

/*遍历一棵树，层次遍历*/
public void traverse()
{
if(selfId<0)
return;
print(this.selfId);
if(childList==null || childList.isEmpty())
return;
int childNumber=childList.size();
for(int i= 0 ; i < childNumber;i++)
{
TreeNode child=childList.get(i);
child.traverse();
}
}

public void print(String content)
{
System.out.println(content);
}

public void print(int content)
{
System.out.println(String.valueOf(content));
}

public void setChildList(List childList) {
this.childList = childList;
}

public int getParentId() {
return parentId;
}

public void setParentId(int parentId) {
this.parentId = parentId;
}

public int getSelfId() {
return selfId;
}

public void setSelfId(int selfId) {
this.selfId = selfId;
}

public TreeNode getParentNode() {
return parentNode;
}

public void setParentNode(TreeNode parentNode) {
this.parentNode = parentNode;
}

public String getNodeName() {
return nodeName;
}

public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}

public Object getObj() {
return obj;
}

public void setObj(Object obj) {
this.obj = obj;
}
}
二：TreeHelper.java
import java.util.List;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.HashMap;
public class TreeHelper {

private TreeNode root;
private List tempNodeList;
private boolean isValidTree=true;

public TreeHelper()
{
}
public TreeHelper(List treeNodeList)
{
tempNodeList=treeNodeList;
generateTree();
}

public static TreeNode getTreeNodeById(TreeNode tree,int id)
{
if(tree==null)
return null;
TreeNode treeNode;
treeNode=tree.findTreeNodeById(id);
return treeNode;
}

/** generate a tree from the given treeNode or entity list
*/
public void generateTree()
{
HashMap nodeMap = putNodesIntoMap();
putChildIntoParent(nodeMap);
}

/** put all the treeNodes into a hash table by its id as the key
*@return hashmap that contains the treenodes
*/
protected HashMap putNodesIntoMap()
{
int maxId=Integer.MAX_VALUE;
HashMap nodeMap=new HashMap ();
Iterator it=tempNodeList.iterator();
while(it.hasNext())
{
TreeNode treeNode=(TreeNode)it.next();
int id=treeNode.getSelfId();
if(id {
maxId=id;
this.root=treeNode;
}
String keyId=String.valueOf(id);

nodeMap.put(keyId,treeNode);
//System.out.println("keyId: " +keyId);
}
return nodeMap;
}

/** set the parent nodes point to the child nodes
*@param nodeMap a hashmap that contains all the treenodes by its id as the key
*/
protected void putChildIntoParent(HashMap nodeMap)
{
Iterator it=nodeMap.values().iterator();
while(it.hasNext())
{
TreeNode treeNode=(TreeNode)it.next();
int parentId=treeNode.getParentId();
String parentKeyId=String.valueOf(parentId);
if(nodeMap.containsKey(parentKeyId))
{
TreeNode parentNode=(TreeNode)nodeMap.get(parentKeyId);
if(parentNode==null)
{
this.isValidTree=false;
return ;
}
else
{
parentNode.addChildNode(treeNode);
//System.out.println("childId: " +treeNode.getSelfId()+" parentId: "+parentNode.getSelfId());
}
}
}
}

/**initialize the tempNodeList property
*/
protected void initTempNodeList()
{
if(this.tempNodeList==null)
{
this.tempNodeList=new ArrayList ();
}
}

/** add a tree node to the tempNodeList
*/
public void addTreeNode(TreeNode treeNode)
{
initTempNodeList();
this.tempNodeList.add(treeNode);
}

/** insert a tree node to the tree generated already
* @return show the insert operation is ok or not
*/
public boolean insertTreeNode(TreeNode treeNode)
{
boolean insertFlag= root.insertJuniorNode(treeNode);
return insertFlag;
}

/** adapt the entities to the corresponding treeNode
*@param entityList list that contains the entities
*@return the list containg the corresponding treeNodes of the entities
*/
public static List changeEnititiesToTreeNodes(List entityList)
{
OrganizationEntity orgEntity=new OrganizationEntity();
List tempNodeList=new ArrayList ();
TreeNode treeNode;

Iterator it = entityList.iterator();
while(it.hasNext())
{
orgEntity= (OrganizationEntity)it.next();
treeNode=new TreeNode();
treeNode.setObj(orgEntity);
treeNode.setParentId(orgEntity.getParentId());
treeNode.setSelfId(orgEntity.getOrgId());
treeNode.setNodeName(orgEntity.getOrgName());
tempNodeList.add(treeNode);
}
return tempNodeList;
}

public boolean isValidTree()
{
return this.isValidTree;
}

public TreeNode getRoot() {
return root;
}

public void setRoot(TreeNode root) {
this.root = root;
}

public List getTempNodeList() {
return tempNodeList;
}

public void setTempNodeList(List tempNodeList) {
this.tempNodeList = tempNodeList;
}

}