求教一段树形算法

Question

package org.phyeas.demo;import java.util.HashSet;
import java.util.Set;public class StringArrayToTree {
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" }; public static void main(String[] args) {
Node root = new Node();
root.setText("root");
root.addChild(str, true, true);
System.out.println(root.toUlString());
}
}class Node {
private String text; private Node parent; private Set<Node> childs; public Node getParent() {
return parent;
} public void setParent(Node parent) {
this.parent = parent;
} public String getText() {
return text;
} public void setText(String text) {
this.text = text;
} /**
 * 获取该节点下的子节点
 * 
 * @param text
 *            节点文本
 * @param canCreate
 *            如果不存在是否创建
 * @return
 */
public Node getChild(String text, boolean canCreate) {
if (childs == null) {
childs = new HashSet<Node>();
}
for (Node child : childs) {
System.out.println("child.getText()=" + child.getText() + ",text="
+ text + "," + child.getText().equals(text));
if (child.getText().equals(text)) {
return child;
}
}
if (canCreate) {
// Node child = new Node();
// child.setText(text);
// child.setParent(this);
// childs.add(child);
// return child;
return this.addChild(text);
}
return null;
} /**
 * 添加节点
 * 
 * @param text
 *            节点文本
 * @return
 */
public Node addChild(String text) {
if (childs == null) {
childs = new HashSet<Node>();
}
Node node = new Node();
node.setText(text);
node.setParent(this);
childs.add(node);
return node;
} /**
 * 添加节点
 * 
 * @param str
 *            节点字符串
 * @param needParse
 *            是否需要解释
 * @param canCreate
 *            当某个节点不存在时是否可以创建
 * @return
 */
public void addChild(String str, boolean needParse, boolean canCreate) {
if (childs == null) {
childs = new HashSet<Node>();
}
// Node node = new Node();
if (needParse) {
String[] strs = str.split(",");
for (String s : strs) {
String[] nodeStrs = s.split("/");
for (int i = 0; i < nodeStrs.length; i++) {
Node parent = null; for (int j = 0; j < i; j++) {
if (i == 0) {
parent = this;
}
if (parent == null) {
parent = this.getChild(nodeStrs[j], canCreate);
} else {
parent = parent.getChild(nodeStrs[j], canCreate);
if (parent == null && canCreate == false) {
System.out.println("无法获取对象==" + nodeStrs[j]);
break;
}
}
} if (parent != null)
parent.addChild(nodeStrs[i], false, canCreate);
}
}
} else {
this.addChild(str);
}
// return this;
} public void addChild(String[] strs, boolean needParse, boolean canCreate) {
if (childs == null) {
childs = new HashSet<Node>();
}
StringBuffer buffer = new StringBuffer();
for (int i = 0; i < strs.length; i++) {
buffer.append(strs[i]);
if (i != strs.length - 1) {
buffer.append(",");
}
}
this.addChild(buffer.toString(), needParse, canCreate);
} public String toUlString() {
StringBuffer buffer = new StringBuffer();
buffer.append("\n<ul>\n");
buffer.append("  <li>" + text + "</li>\n");
if (childs != null) {
for (Node child : childs) {
buffer.append(child.toUlString());
}
}
buffer.append("</ul>\n");
return buffer.toString();
}
}

Answer 1

上面的不对。现已修正：
package org.phyeas.demo;import java.util.HashSet;
import java.util.Set;public class StringArrayToTree {
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" }; public static void main(String[] args) {
Node root = new Node();
root.setText("root");
root.addChild(str, true, true);
System.out.println(root.toUlString());
}
}class Node {
private String text; private Node parent; private Set<Node> childs; public Node getParent() {
return parent;
} public void setParent(Node parent) {
this.parent = parent;
} public String getText() {
return text;
} public void setText(String text) {
this.text = text;
} /**
 * 获取该节点下的子节点
 * 
 * @param text
 *            节点文本
 * @param canCreate
 *            如果不存在是否创建
 * @return
 */
public Node getChild(String text, boolean canCreate) {
if (childs == null) {
childs = new HashSet<Node>();
}
for (Node child : childs) {
if (child.getText().equals(text)) {
return child;
}
}
if (canCreate) {
return this.addChild(text);
}
return null;
} /**
 * 添加节点，如果已存在该节点就直接返回
 * 
 * @param text
 *            节点文本
 * @return
 */
public Node addChild(String text) {
if (childs == null) {
childs = new HashSet<Node>();
}
Node n = getChild(text, false);
if (n == null) { Node node = new Node();
node.setText(text);
node.setParent(this);
childs.add(node);
return node;
}
return n;
} /**
 * 添加节点
 * 
 * @param str
 *            节点字符串
 * @param needParse
 *            是否需要解释
 * @param canCreate
 *            当某个节点不存在时是否可以创建
 * @return
 */
public void addChild(String str, boolean needParse, boolean canCreate) {
if (childs == null) {
childs = new HashSet<Node>();
}
if (needParse) {
String[] strs = str.split(",");
this.addChild(strs, needParse, canCreate);
} else {
this.addChild(str);
}
} /**
 * 添加节点
 * 
 * @param str
 *            节点字符串
 * @param needParse
 *            是否需要解释
 * @param canCreate
 *            当某个节点不存在时是否可以创建
 * @return
 */
public void addChild(String[] strs, boolean needParse, boolean canCreate) {
if (childs == null) {
childs = new HashSet<Node>();
}
if (needParse) {
for (String s : strs) {
String[] nodeStrs = s.split("/");
for (int i = 0; i < nodeStrs.length; i++) {
Node parent = null; for (int j = 0; j < i; j++) {
if (j == 0) {
parent = this.getChild(nodeStrs[j], canCreate);
} else {
parent = parent.getChild(nodeStrs[j], canCreate);
if (parent == null && canCreate == false) {
System.err.println("无法获取对象==" + nodeStrs[j]);
break;
}
} } if (parent != null) {
parent.addChild(nodeStrs[i], false, canCreate);
}
}
}
} else {
for (String str : strs) {
this.addChild(str);
}
}
} public String toUlString() {
StringBuffer buffer = new StringBuffer();
buffer.append("\n<ul>\n");
buffer.append("  <li>" + text + "</li>\n");
if (childs != null) {
for (Node child : childs) {
buffer.append(child.toUlString());
}
}
buffer.append("</ul>\n");
return buffer.toString();
}
}

Answer 2

    public static void main(String[] args) {
        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"};
        g(str);
    }    public static void g(String[] arr) {
        Deque<Node> root = new ArrayDeque<Node>();
        for (int i = 0; i < arr.length; i++) {
            String[] temp = arr[i].split("/");
            h(temp, 0, root);
        }
        p(root, 0);
    }    private static void h(String[] arr, int a, Deque<Node> nodes) {
        if (a >= arr.length) {
            return;
        }
        Node node = nodes.peekLast();
        if (node == null || !node.name.equals(arr[a])) {
            node = new Node(arr[a]);
            nodes.add(node);
        }
        h(arr, a + 1, node.childNodes);
    }    private static void p(Deque<Node> nodes, int a) {
        if (nodes.size() == 0) {
            return;
        }
        StringBuffer s = new StringBuffer();
        for (int i = 0; i < a; i++) {
            s.append("      ");
        }
        System.out.println(s + "<ul" + (a == 0 ? " id=\"root\"" : "") + "> ");
        for (Node node : nodes) {
            System.out.println(s + "  <li>" + node.name + "</li>");
            p(node.childNodes, a + 1);
        }
        System.out.println(s + "</ul>");
    }    private static class Node {        public Node(String name) {
            this.name = name;
            childNodes = new ArrayDeque<Node>();
        }
        private String name;
        private Deque<Node> childNodes;
    }