树形结构算法

Question

题目是这样的，有一段数组
static final String[] str={"aaa/bbb/ccc",
"aaa/ddd/eee",
"aaa/ddd/ooo",
"bbb/sss/xxx",
"eee/sss/aaa",
"aaa/eee/www",
"aaa/bbb/ccc/ddd",
"ccc/eee/www",
"ccc/eee/www/nnn"};

要求显示成

• aaa
• bbb
• ccc
• ddd
• eee
• ooo
• bbb
• sss
...........

帮我写写这个算法，我卡在这里1天了。其实也就是一个递归。

:cry: :cry: :cry:

Answer 1

[code="java"]
package app;

public class TreeDaoImpl {
public String[] queryData() {
return new String[] { "aaa/ddd/eee",
"aaa/ddd/ooo",
"bbb/sss/xxx",
"eee/sss/aaa",
"aaa/eee/www",
"aaa/bbb/ccc/ddd",
"ccc/eee/www",
"ccc/eee/www/nnn"
};
}
}

[/code]

[code="java"]
package app;

import java.util.List;
import java.util.ArrayList;

public class Node {

private Object data;

private Node parent;

private List children;

public Node() {  
    children = new ArrayList<Node>();  
}  

public Node(Object data, Node parent) {  
    this.data = data;  
    this.parent = parent;  
    children = new ArrayList<Node>();  
}  

public boolean hasChildren() {  
    return children.size() != 0;  
}  

public boolean containChildData(Object data) {  
    return queryChildByData(data) != null;  
}  

public Node queryChildByData(Object data) {  
    Node r = null;  
    for(Node node : children) {  
        if(node.getData().equals(data)) {  
            r = node;  
            break;  
        }  
    }  

    return r;  
}  

public void addChild(Node node) {  
    children.add(node);  
}  

public Object getData() {  
    return data;  
}  

public void setData(Object data) {  
    this.data = data;  
}  

public Node getParent() {  
    return parent;  
}  

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

public List<Node> getChildren() {  
    return children;  
}  

public void setChildren(List<Node> children) {  
    this.children = children;  
}  

}

[/code]

[code="java"]
package app;

public class TreeBuilder {

private TreeDaoImpl dao = new TreeDaoImpl();
private StringBuffer buffer = new StringBuffer();

public Node generateTree() {
    String[] data = dao.queryData();
    Node root = new Node();
    Node parent = null;

    for(String e :data) {
        String[] s = parseData(e);

        parent = root;
        if(s != null || s.length > 0) {
            for(String f : s) {

                Node node = null;
                if(parent.containChildData(f)) {
                    node = parent.queryChildByData(f);
                } else {
                    node = new Node(f, parent);
                    parent.addChild(node);
                }

                parent = node;
            }
        }
    }

    return root;
}

public String generateHtml(Node root) {
    if(root == null) {
        return "";
    }

    privateGenerateHtml(root, root);
    return buffer.toString();
}

public void privateGenerateHtml(Node parent, Node root) {
    if(parent == root) {
        buffer.append("<ul id=\"root\">");
    } else {
        buffer.append("<ul>");
    }

    for(int i = 0; i < parent.getChildren().size(); i++) {
        Node node = parent.getChildren().get(i);
        buffer.append("<li>" + node.getData() + "</li>");
        privateGenerateHtml(node, root);
    }
    buffer.append("</ul>");
}

public String[] parseData(String s) {
    String[] result = new String[0];

    if(s != null && s.indexOf("/") >= 0) {
        result = s.split("/");
    }

    return result;
}

public static void main(String[] args) {
    TreeBuilder tb = new TreeBuilder();
    Node root = tb.generateTree();
    String s = tb.generateHtml(root);
    System.out.println(s);
}

}

[/code]

[code="html"]

• aaa
• ddd
• eee
• ooo
• eee
• www
• bbb
• ccc
• ddd
• bbb
• sss
• xxx
• eee
• sss
• aaa
• ccc
• eee
• www
• nnn

[/code]