在Java中将平面结构转换为典型的父子树

Question

出于某种原因，我对此一无所知，也许我的大脑最近超负荷了，但我似乎不能正确地理解它。我正在尝试将唯一值的结构化列表转换为树结构。

我有一个在Apache MultiKey类中设置的唯一值列表，它基本上只是组成一个键的任意数量对象的包装器。他们的列表如下所示：

List<MultiKey> _data = new ArrayList<MultiKey>()

里面的数据看起来像这样：

MultiKey[ABC]
MultiKey[ABC, 111]
MultiKey[ABC, 111, CHF]
MultiKey[ABC, 111, CHF, AT000B049432]
MultiKey[ABC, 111, CHF, CH0012814965]
MultiKey[ABC, 111, CHF, CH0018550399]
MultiKey[ABC, 111, CHF, CH0020626773]
MultiKey[ABC, 111, EUR]
MultiKey[ABC, 111, EUR, AT0000A001X2]
MultiKey[ABC, 111, EUR, AT0000A0U3T4]
MultiKey[ABC, 111, USD]
MultiKey[ABC, 111, USD, CH0002497458]
MultiKey[DEF]
MultiKey[DEF, 222]
MultiKey[DEF, 222, CHF]
MultiKey[DEF, 222, CHF, AT000B049432]
MultiKey[DEF, 222, CHF, CH0012814965]
MultiKey[DEF, 222, EUR]
MultiKey[DEF, 222, EUR, AT0000A001X2]

组成Tree Node的类是一个典型的父子树节点，如下所示(为简单起见，排除了其他方法)。

public class DataTreeNode {

    private Object              _data;
    private DataTreeNode        _parent;
    private List<DataTreeNode>  _children;

    public DataTreeNode() {
        super();
    }

    public DataTreeNode(Object data) {
        super();
        _data = data;
    }

    public DataTreeNode getParent() {
        return _parent;
    }

    public void setParent(DataTreeNode parent) {
        _parent = parent;
    }

    public Object getData() {
        return _data;
    }

    public void addChild(DataTreeNode child) {
        if (!_children.contains(child)) {
            _children.add(child);
            child.setParent(this);
        }
    }

    public List<DataTreeNode> getChildren() {
        return _children;
    }

}

我们的想法是遍历键并(使用示例数据)构建一个树，如下所示：

ABC
  111
    CHF
      AT000B049432
      CH0012814965
      CH0018550399
      CH0020626773
    EUR
      AT0000A001X2
      AT0000A0U3T4
    USD
      CH0002497458
DEF
  222
    CHF
      AT000B049432
      CH0012814965
    EUR
      AT0000A001X2

下面是一个完全可运行的Java示例，它使用MultiKey结构构建示例数据，但缺少转换为树的实现。

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

import org.apache.commons.collections.keyvalue.MultiKey;

public class Sample {

    public static void main(String [] args) { 
        List<MultiKey> data = new ArrayList<MultiKey>();

        data.add(new MultiKey(new Object [] { "ABC" }));
        data.add(new MultiKey(new Object [] { "ABC", "111" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "CHF" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "AT000B049432" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "CH0012814965" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "CH0018550399" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "CH0020626773" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "EUR" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "EUR", "AT0000A001X2" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "EUR", "AT0000A0U3T4" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "USD" }));
        data.add(new MultiKey(new Object [] { "ABC", "111", "USD", "AT0000A0U3T4" }));
        data.add(new MultiKey(new Object [] { "DEF" }));
        data.add(new MultiKey(new Object [] { "DEF", "222" }));
        data.add(new MultiKey(new Object [] { "DEF", "222", "CHF" }));
        data.add(new MultiKey(new Object [] { "DEF", "222", "CHF", "AT000B049432" }));
        data.add(new MultiKey(new Object [] { "DEF", "222", "CHF", "CH0012814965" }));
        data.add(new MultiKey(new Object [] { "DEF", "222", "EUR" }));
        data.add(new MultiKey(new Object [] { "DEF", "222", "EUR", "AT0000A001X2" }));

        DataTreeNode treeFromData = Sample.getTreeFor(data);
        // ...
    }

    public static DataTreeNode getTreeFor(List<MultiKey> data) {
        // TODO: THIS!
        return null;
    }
}

提前感谢你帮我解决这个问题！

Answer 1

如果这不是家庭作业，你可以自由地使用任何可以简化事情的数据结构。

我建议使用Map来进行映射。"ABC“添加到表示它的节点。这将使构建树变得更加简单。

Answer 2

感谢大家的评论，最后我的大脑终于被点开了。我同意MultiKey不是理想的结构，但基本上它可以完成这项工作。

我在DataTreeNode类中添加了以下方法：

public void printTree() {
    printTree(0);
}

private void printTree(int i) {
    for (int x = 0; x < i; x++) {
        System.out.print(" ");
    }
    System.out.println(this);
    for (DataTreeNode child : _children) {
        child.printTree(i+1);
    }
}

public void buildFrom(DataTreeNode root, MultiKey mk) {
    buildFrom(root, 0, mk);
}

private void buildFrom(DataTreeNode root, int start, MultiKey mk) {
    if (start >= mk.getKeys().length) {
        return;
    }
    // get value
    Object val = mk.getKey(start);
    // value exists?
    DataTreeNode tn = root.getChildWithValue(val);
    if (tn == null) {
        tn = new DataTreeNode(val);
        root.addChild(tn);
    }
    else {
        buildFrom(tn, ++start, mk);
    }       
}

private DataTreeNode getChildWithValue(Object o) {
    for (DataTreeNode tn : _children) {
        if (tn.getData() == o) {
            return tn;
        }
    }
    return null;
}

@Override
public String toString() {
    return "[DataTreeNode: " + _data + "]";
}

而getTreeFor方法变成了：

公共静态根(列表数据){ DataTreeNode DataTreeNode =新DataTreeNode()；

for (MultiKey mk : data) {
    DataTreeNode node = new DataTreeNode();
    node.buildFrom(root, mk);           
}

return root;

}

因此最终

treeFromData.printTree();

打印输出

[DataTreeNode: null]
 [DataTreeNode: ABC]
  [DataTreeNode: 111]
   [DataTreeNode: CHF]
    [DataTreeNode: AT000B049432]
    [DataTreeNode: CH0012814965]
    [DataTreeNode: CH0018550399]
    [DataTreeNode: CH0020626773]
   [DataTreeNode: EUR]
    [DataTreeNode: AT0000A001X2]
    [DataTreeNode: AT0000A0U3T4]
   [DataTreeNode: USD]
    [DataTreeNode: AT0000A0U3T4]
 [DataTreeNode: DEF]
  [DataTreeNode: 222]
   [DataTreeNode: CHF]
    [DataTreeNode: AT000B049432]
    [DataTreeNode: CH0012814965]
   [DataTreeNode: EUR]
    [DataTreeNode: AT0000A001X2]

除了清理代码之外，它还可以工作。

再次感谢！