多叉树的实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
*
* <多叉树>
* <功能详细描述>
*
* @author
soul390
* @version
*/
public class TreeNode
{
/**
* 父节点的ID
*/
private int parentId;
private int selfId;
protected String nodeName;
protected Object object;
protected TreeNode parentNode;
/**
* 孩子节点列表
*/
protected List<TreeNode> childList;
public String getNodeName()
{
return nodeName;
}
public void setNodeName(String nodeName)
{
this.nodeName = nodeName;
}
public List<TreeNode> getChildList()
{
return childList;
}
public void setChildList(List<TreeNode> 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(int parentId, int selfId, String nodeName)
{
this.parentId = parentId;
this.selfId = selfId;
this.nodeName = nodeName;
}
public void initChildList()
{
if(null == childList)
{
childList = new ArrayList<>();
}
}
public void addChildNode(TreeNode treeNode)
{
initChildList();
childList.add(treeNode);
}
/**
* <插入节点>
* <功能详细描述>
* @param treeNode
* @return
* @author soul390
*/
public boolean insertJuniorNode(TreeNode treeNode)
{
int parentId = treeNode.getParentId();
if(this.selfId == parentId)
{
addChildNode(treeNode);
return true;
}
else
{
if(childList == null || childList.isEmpty())
{
return false;
}
for(TreeNode node:childList)
{
boolean f = node.insertJuniorNode(treeNode);
if(f)
{
return true;
}
}
}
return false;
}
/**
* <深度优先遍历>
* <功能详细描述>
* @author soul390
*/
public void depthTraverse()
{
System.out.println(nodeName);
if(null == childList || childList.isEmpty())
{
return;
}
for(TreeNode node:childList)
{
node.depthTraverse();
}
}
/**
* <广度优先遍历>
* <功能详细描述>
* @author soul390
*/
public void breadthTraverse()
{
// 使用队列暂存节点
LinkedList<TreeNode> linkedList = new LinkedList<>();
linkedList.add(this);
while(!linkedList.isEmpty())
{
TreeNode node = linkedList.pop();
System.out.println(node.getNodeName());
if(node.getChildList() == null || node.getChildList().isEmpty())
{
continue;
}
for(TreeNode treeNode:node.getChildList())
{
linkedList.add(treeNode);
}
}
}
}

 

import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
public class TreeHelper
{
private TreeNode root;
public TreeNode getRoot()
{
return root;
}
public void setRoot(TreeNode root)
{
this.root = root;
}
private List<TreeNode> treeNodeList;
public TreeHelper(List<TreeNode> treeNodeList)
{
this.treeNodeList = treeNodeList;
generateTree();
}
/**
*
* <生成树>
* <功能详细描述>
* @author soul390
*/
private void generateTree()
{
HashMap<Integer, TreeNode> nodeMap = putNodesIntoMap();
putChildIntoParent(nodeMap);
}
/**
*
* <根据节点的selfId，生成HashMap>
* <功能详细描述>
* @return
* @author soul390
*/
protected HashMap<Integer, TreeNode> putNodesIntoMap()
{
int maxId = Integer.MAX_VALUE;
HashMap<Integer, TreeNode> hashMap = new HashMap<>();
for(TreeNode node:treeNodeList)
{
int selfId = node.getSelfId();
if(selfId < maxId)
{
// 根节点
root = node;
maxId = selfId;
}
hashMap.put(selfId, node);
}
return hashMap;
}
/**
*
* <建立节点之间的联系>
* <功能详细描述>
* @param nodeMap
* @author soul390
*/
public void putChildIntoParent(HashMap<Integer, TreeNode> nodeMap)
{
Iterator<TreeNode> iterator = nodeMap.values().iterator();
while (iterator.hasNext())
{
TreeNode node = iterator.next();
int parentId = node.getParentId();
if(nodeMap.containsKey(parentId))
{
// 找到父节点，并加入父节点的子节点列表
TreeNode parentNode = nodeMap.get(parentId);
parentNode.addChildNode(node);
}
}
}
}

 

import java.util.ArrayList;
import java.util.List;
public class Main
{
public static void main(String[] args)
{
TreeNode node1 = new TreeNode(0, 2, "A");
TreeNode node2 = new TreeNode(2, 3, "B");
TreeNode node3 = new TreeNode(2, 4, "C");
TreeNode node4 = new TreeNode(3, 5, "D");
TreeNode node5 = new TreeNode(3, 6, "E");
TreeNode node6 = new TreeNode(2, 7, "F");
TreeNode node7 = new TreeNode(6, 8, "G");
List<TreeNode> list = new ArrayList<TreeNode>();
list.add(node1);
list.add(node2);
list.add(node3);
list.add(node4);
list.add(node5);
TreeHelper helper = new TreeHelper(list);
helper.getRoot().insertJuniorNode(node6);
helper.getRoot().insertJuniorNode(node7);
// 深度优先遍历
helper.getRoot().breadthTraverse();
System.out.println("-------------------");
// 广度优先遍历
helper.getRoot().depthTraverse();
}
}

 

 

根据节点信息(父节点的ID，节点ID，节点名称)生成多叉树，并进行遍历。