我想问一个递归的问题，应该是树的递归吧

Question

id paredntid
1 0
2 1
3 1
4 2
5 3

这样一组数据，假设已经放在list里了，如何封装成{1，{2{4}}，{3{5}}}.
哪位兄弟指点迷津下，谢谢

Answer 1

遍历树的过程通常可以用递归来实现，但是遍历一个list来构造一棵树纯粹是线性的遍历而已……

简单实现了一个版本：
[code="java"]import java.util.*;

class TreeNode {
// don't need a reference to parent for an ordinary tree
//private TreeNode parent;

// a list of children TreeNodes, implementing an N-ary tree
private List<TreeNode> children;

// use this field to carry values on all nodes
private E value;

public TreeNode() {
    this(null);
}

public TreeNode(E value) {
    this.value = value;
    this.children = new ArrayList<TreeNode>();
}

public TreeNode(E value, Iterable<TreeNode> children) {
    this(value);
    // add all children
    // can't use List<E>.addAll() because Iterable<E> is
    // a base interface of Collection<E>
    for (TreeNode child : children) {
        addChild(child);
    }
}

public E getValue() {
    return this.value;
}

public void setValue(E value) {
    this.value = value;
}

public Iterable<TreeNode> getChildren() {
    return this.children;
}

public void addChild(TreeNode child) {
    // skip duplicate children
    if (!this.children.contains(child)) {
        this.children.add(child);
    }
}

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    toStringCore(sb);
    return sb.toString();
}

// builds the string recursively
protected void toStringCore(StringBuilder sb) {
    sb.append("(");
    sb.append(value);
    for (TreeNode child : this.children) {
        sb.append(" ");
        child.toStringCore(sb);
    }
    sb.append(")");
}

}

public class TestTree {
private static Map getSampleNodeMapping() {
return new HashMap() {{
put(1, 0);
put(2, 1);
put(3, 1);
put(4, 2);
put(5, 3);
}};
}

private static TreeNode<Integer> buildTreeFromMapping(
    Map<Integer, Integer> mapping) {

    // make a map from id to TreeNode instance
    Map<Integer, TreeNode<Integer>> nodes
        = new HashMap<Integer, TreeNode<Integer>>();
    TreeNode<Integer> root = null;
    for (Map.Entry<Integer, Integer> entry : mapping.entrySet()) {
        Integer key = entry.getKey();
        Integer value = entry.getValue();
        TreeNode<Integer> child = null;
        if (!nodes.containsKey(key)) {
            child = new TreeNode<Integer>(key);
            nodes.put(key, child);
        } else {
            child = nodes.get(key);
        }
        if (0 == value) {
            root = child;
        } else {
            TreeNode<Integer> parent = null;
            if (!nodes.containsKey(value)) {
                parent = new TreeNode<Integer>(value);
                nodes.put(key, parent);
            } else {
                parent = nodes.get(value);
            }
            parent.addChild(child);
        }
    }

    return root;
}

public static void main(String[] args) {
    Map<Integer, Integer> mapping = getSampleNodeMapping();
    TreeNode<Integer> root = buildTreeFromMapping(mapping);
    System.out.println(root); // (1 (2 (4)) (3 (5)))
}

}[/code]
这段代码遍历一个id到parent_id的映射表并创建出对应的树，这个遍历过程是线性的；在得到树的字符串表示（toString）时遍历了树，过程是递归的。