树的构造与遍历，请各位大侠看看有几种解法？

Question

在一个文件中有以下内容
root|a,b,c,d
a|aa1,aa2
b|bb1,bb2
c|cc1其中“|”号是父亲、孩子节点的分隔符，“，”号是兄弟节点的分隔符题目：请从文件中读取数据，构造树形结构，并按照深度、广度优先输出。

Answer 1

是不是作业啊？？？？
数据封装成一对象，再对象里放一List<自身>就行了

Answer 2

Stack + List再加个广度搜索，搞定

Answer 3

这是我的实现方法供大家参考，若有更优的算法望共享：）public class FilterRelate
{
/**
 * 测试接口
 * @param inputPath 输入文件路径
 * @param outPath 输出文件路径
 * @param itType 输出类型，限制BFS/DFS两种类型
 */
public void outputTreeInfo(String inputPath, String outputPath, String itType)
{
if(inputPath == null || inputPath.length() == 0)
{
return;
}
Map<String, String[]> p2cMap = new HashMap<String, String[]>();
Node rootNode = null;
File file = new File(inputPath);
try
{
FileReader fileReader = new FileReader(file);
BufferedReader bufReader = new BufferedReader(fileReader);
String line = null;
while((line = bufReader.readLine()) != null)
{
if(isTitleRow(line))
{
continue;
}
String[] cells = line.split(",");
if(cells.length != 2)
{
continue;
}
String[] children = cells[1].split(";");
if(children == null || children.length == 0)
{
continue;
}
if(cells[0].equals(OPContants.ROOT))
{
rootNode = new Node(cells[0]);
for (String c : children)
{
Node childNode = new Node(c);
rootNode.addChild(childNode);
}
}
//放在Map中
p2cMap.put(cells[0], children);
}
bufReader.close();
fileReader.close();
}
catch (Exception e)
{
e.printStackTrace();
}
if(rootNode != null && !p2cMap.isEmpty())
{
bulidTree(rootNode, p2cMap);
if(OPContants.BFS.equals(itType))
{
outputByBFS(rootNode, "");
}
if(OPContants.DFS.equals(itType))
{
outputByDFS(rootNode, "");
}
}
}

/**
 * 递归构建树形结构
 * @param rootNode
 * @param p2cMap
 */
private void bulidTree(Node rootNode, Map<String, String[]> p2cMap)
{
List<Node> childrenNodes = rootNode.getChildrenNode();
for (Node childNode : childrenNodes)
{
String[] cNames = p2cMap.get(childNode.toString());
if(cNames != null)
{
for (String cName : cNames)
{
Node cNode = new Node(cName);
childNode.addChild(cNode);
}
}
bulidTree(childNode, p2cMap);
}
}

/**
 * 判断是否标题行
 * @param str
 * @return
 */
private boolean isTitleRow(String str)
{
if(str.startsWith(OPContants.RELATE_TITLE[0]))
{
return true;
}
return false;
}

/**
 * 广度遍历输出
 * @param filePath
 */
private void outputByBFS(Node rootNode, String filePath)
{
List<Node> tempList = new ArrayList<Node>();
tempList.add(rootNode);
while(!tempList.isEmpty())
{
Node node = tempList.remove(0);
System.out.println(node + " ");
List<Node> children = node.getChildrenNode();
tempList.addAll(children);
}
}

/**
 * 深度遍历输出
 * @param filePath
 */
private void outputByDFS(Node rootNode, String filePath)
{
List<Node> children = rootNode.getChildrenNode();
for (Node node : children)
{
outputByDFS(node, "");
}
System.out.print(rootNode + " ");
}

/**
 * 主函数入口
 * @param args
 */
public static void main(String[] args)
{
FilterRelate fr = new FilterRelate();
fr.outputTreeInfo("conf/relate.csv", "", OPContants.DFS);
}

//节点结构定义
class Node
{
    public String name = null;
    public Node parentNode = null;
    public List<Node> childrenNode = new ArrayList<Node>();

public Node(String name)
{
this.name = name;
}

public void setParent(Node parentNode)
{
this.parentNode = parentNode;
}

public void addChild(Node childNode)
{
childrenNode.add(childNode);
}

public List<Node> getChildrenNode()
{
return this.childrenNode;
} @Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + getOuterType().hashCode();
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
} @Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (name == null)
{
if (other.name != null)
return false;
}
else if (!name.equals(other.name))
return false;
return true;
} public String toString()
{
return this.name;
} private FilterRelate getOuterType()
{
return FilterRelate.this;
}
}
}