c# - 如何从平面数据中找到树叶

Question

我有一个与此类似的树数据：

[0] => 
      id = 5,
      name = "TV",
      parent_id = 1,
      children => 
                  [0] => 
                        id = 6,
                        name = "PLASMA",
                        parent_id = 5,
                        children = null
                  [1] =>
                        id = 7,
                        name = "LCD",
                        parent_id = 5,
                        children =>
                                    [0] =>
                                          id = 8,
                                          name = "Gloss",
                                          parent_id = 7,
                                          children = null
                                    [1] =>
                                          id = 9,
                                          name = "Matte",
                                          parent_id = 7,
                                          children = null
[1] =>
      id = 4,
      name = "Printers",
      parent_id = 1,
      children =>
                 ....

我有一个扁平的字符串数据，例如：

• 电视
• TV_PLASMA_光泽
• 电视_液晶

'_' 是子类别的分隔符。

查找类别 ID 数组的最佳算法是什么？

示例输入：

1. 电视
2. TV_PLASMA_光泽
3. 电视_液晶

示例输出：

1. 数组：5
2. 数组：5、6、8
3. 数组：5、7

语言无关紧要——它只是一种算法——但在这种情况下，我更喜欢 C#。

谢谢你。

Answer 1

使用HashMap(Dictionary<string, int>在这种情况下会很好)，遍历您的树并将 (name, id) 对添加到 HashMap。

对于任何输入，您传入输入字符串和哈希图。

• 在分隔符上拆分字符串，在本例中为 '_' ( input.Split(new char[]{'_'}))
• 对于每个字符串部分，在 hashmap 中查找其 id，并将其添加到输出字符串或数组中

*

public int[] GetIDsFromString(string input, Dictionary<string, int> lookup)
{
  string stringParts = input.Split(new char[]{'_'});
  int[] retval = new int[stringParts.Length];
  int retIndex = 0;
  foreach(var s in stringParts)
    if (lookup.contains(s))
      retval[retIndex++] = lookup[s];
    else
      throw new Exception(string.format("string contained invalid item {0}", s));
  return retval;
}

Answer 2

使用字典（反向）查找与名称相关的 ID

Dictionary<string,int> ids = new Dictionary<string,int>();
ids.Add("TV", 5);
ids.Add("PLASMA", 6);
// And so on

现在，在查找 id 之前拆分输入字符串

string input = "TV_PLASMA_Gloss";
string[] categories = input.Split('_');
int[] result = new int[categories.Length];
for (int i = 0; i < categories.Length; i++) {
    int id;
    if (ids.TryGetValue(categories[i], out id)) {
        result[i] = id;
    } else {
        result[i] = -1; // Unknown category
    }
}

Answer 3

就是这样，我会使用递归来做到这一点：

定义一个函数，它接受一个字符串数组和你的结构/对象数组或其他任何东西。在调用函数之前解析字符串数组：

string = "TV_PLASMA_Gloss"
array[0] = "TV"
array[1] = "PLASMA"
array[2] = "Gloss"

数组中的第一个字符串将针对所有“顶级”条目进行测试。如果有匹配的条目，将使用剩余的数组和匹配的条目再次调用该函数。

如果数组中只剩下一个字符串，我们返回找到的条目的 id。这样我们就可以进行递归调用并构建我们想要的 integer-id-array。

调用层次结构如下所示：

-> function({"TV","PLASMA","Gloss"}, entry)
   -> function({"PLASMA","Gloss"}, matched_entry)
       -> function({"Gloss"}, matched_entry)
       <- id = 8
   <- id = 6,8
<- id = 5,6,8