如何将对象视为数组并遍历它并将响应保存在 javascript 中，并使用 trie 数据结构？

Question

我是数据结构的初学者。我刚刚开始学习它。我正在尝试使用 trie 数据结构创建一个家族结构。我在这里指的是 github 上的文档： https://gist.github.com/tpae/72e1c54471e88b689f85ad2b3940a8f0#file-trie-js-L44

这是一些代码。

function TrieNode(key) {
  // the "key" value will be the character in sequence
  this.key = key;
  
  // we keep a reference to parent
  this.parent = null;
  
  // we have hash of children
  this.children = {};
  
  // check to see if the node is at the end
  this.end = false;
}

// -----------------------------------------

// we implement Trie with just a simple root with null value.
function Trie() {
  this.root = new TrieNode(null);
}

// inserts a word into the trie.
// time complexity: O(k), k = word length
Trie.prototype.insert = function(word) {
  var node = this.root; // we start at the root 
  
  // for every character in the word
  for(var i = 0; i < word.length; i++) {
    // check to see if character node exists in children.
    if (!node.children[word[i]]) {
      // if it doesn't exist, we then create it.
      node.children[word[i]] = new TrieNode(word[i]);
      
      // we also assign the parent to the child node.
      node.children[word[i]].parent = node;
    }
    
    // proceed to the next depth in the trie.
    node = node.children[word[i]];
    
    // finally, we check to see if it's the last word.
    if (i == word.length-1) {
      // if it is, we set the end flag to true.
      node.end = true;
    }
  }
};

我的疑问是在插入节点时，我们是如何遍历 word 并创建一个节点的：

 node.children[word[i]]

这对我来说是无法理解的。还有如何在函数 TrieNode 中声明键、父项、子项？它们是否被视为在创建对象时初始化的全局变量？为什么在其他函数中声明了 root，它是如何工作的？ P.S。我必须像这样插入树：

var familyHead = {
      name: 'Chit',
      gender:'Male',
      grandfather:'',
      grandmother:'',
      father:'Shan',
      mother:'Anga',
      wife:'Amba',
    children : [
    {
      name: 'Chit',
      gender:'Male',
      grandfather:'',
      grandmother:'',
      father:'Shan',
      mother:'Anga',
      wife:'Amba',
      children :[]
}]

} ... 继续

Answer 1

您可以给 JavaScript objects 属性，这些属性引用相关的 objects 来完成您想要形成的 graph。（不要使用 trie，那是为了别的。）

例如，为每个人创建一个普通的JavaScript object。

// Create an to represent each unique person
const chit = { name: 'Chit', gender: 'male' };
const shan = { name: 'Shan', gender: 'male' };
const anga = { name: 'Anga', gender: 'female' };
const anba = { name: 'Anba', gender: 'female' };

// Give them properties that establish the relationships as required
chit.father = shan;
chit.mother = anga;
chit.wife = amba;
/// ...

目前有 uni-directional 个链接。如果您还希望父亲拥有他们的 children 的数组，那么您必须在构建它时维护这个数据结构。您将需要一些方便的功能来执行此操作。

要在两个人之间建立 parent-child 关系，至少必须发生一件事：

child object 应将其 parent 属性设置为 parent object.

如果，为了方便或效率，你还想维护每个人拥有的 children 列表的缓存，那么进一步：

parent object 应该将 child object 添加到其 children 数组中。

这样做过度指定了 parent-child 关系，因此数据结构必须保持完整性。这意味着您需要提供函数来在检查不一致的同时对树进行修改。例如，同时尝试为同一个 child 建立两个 parent-child 关系，或者建立一个没有 parent 的 child（someone 将需要没有 parent 因为你不能存储无限深的世代历史），或者将一个人列为 child 但不能同时拥有相同的child 被列为具有相同的 parent。

在这样的函数中，现在可能会检查整个树的完整性，但只检查被修改的结构部分可能就足够了。

建立新的parent-child关系时，检查child是否已经有parent。如果他们这样做了，有两种策略来处理这个问题，这取决于编辑谁是一个人的parent的其他生物学上不可变的属性是否有意义（例如，考虑像[=82=这样的过程]领养)

抛出异常。
通过从 parent 的 children 数组中删除 child 来编辑关系，然后再更新以设置新的 parent.

在这里，我将提供一个允许每个性别 parent 的实现。我将 parent 的性别映射到 mother 或 father 属性名称只是为了说明这样做的便利性。例如，如果您发现需要表示有两个母亲的家庭，那么您将需要使用 parent 数组。（但是您的示例使用 mother 和 father，我也将如此。）

const parent_property_name = {
  male: 'father',
  female: 'mother'
};

function establishParentChildRelationship(parent, child) {
   if (!child.parent) child.parent = {};
   if (child[parent_property_name[parent.gender]]) throw new Error('child already has a parent of that gender');
   child[parent_property_name[parent.gender]] = parent;
   if (!parent.children) parent.children = [];
   parent.children.push(child);
}

希望您能看到，由于需要维护，通常不会进一步存储显式祖父和祖母关系那个树。父亲的父亲是隐含的祖父，可以这样确定。同样，parent 的兄弟姐妹是阿姨和叔叔等。仅根据 parent-child 关系就可以确定堂兄弟姐妹和堂兄弟姐妹。无需再次显式存储它。此外，必须考虑是否需要显式定义 mother 和 father 因为它们可能来自 parent + gender. （或者不代表像 female-father 这样的概念可以吗？这些事情的细节可能会由您工作的法律框架来定义。但世界是一个复杂的地方。）

然而，婚姻关系（法律或宗教或其他）确实需要额外的链接。还必须考虑数据结构是否允许复数婚姻（这可能需要一个数组，很像 children）和 same-gender 婚姻（'married' + 'gender' => 'husband' 或 'wife'）。但是对于一夫一妻制的婚姻，人们可以想象，最低限度地，用 maritalPartner.

来表示它

function establishMonogamousMaritalPartnerRelationship(person1, person2) {
   if (person1.maritalPartner || person2.maritalPartner) throw new Error('already married!');
   person1.maritalPartner = person2;
   person2.maritalPartner = person1;

您还可以根据需要使用将性别映射到 husband 或 wife 的技巧。或者如果你想代表复数婚姻，那么你可以使用一组伴侣（就像 children 所做的那样。）

可能需要再次修改数据结构，以便能够表示这些关系随时间变化的复杂性。（例如离婚或第二次婚姻、收养、解放、性别转变或重新分配等）

让我也花点时间澄清一下 trie 的用途。（不适用于家谱。）

trie 将单词表示为一棵树，其中每个节点都是一个字母，每个节点的 parent 节点是它之前的字母。一个完整的单词在树中的节点上用一个标志标记，即单词的最后一个字母。

考虑一个存储单词的特里树be、bee、bell 和 ball：

.
└── b
    ├── a
    │   └── l
    │       └── l*
    └── e*
        ├── e*
        └── l
            └── l*

标有 * 的节点代表完整的单词（在您的示例中带有 end 标志）。请注意，即使允许更多字母跟随一个单词以形成不同的作品，一个单词也可能会结束。（例如：be 是一个词，即使它后面可能跟有 e 或 l）。每个带有 end 标志的节点，代表一个由其在树中的祖先决定的词。

最后，让我快速回答您关于 key、parent 和 children 是如何在函数 TrieNode.[=42= 中声明的性质的问题]

你看到的是JavaScript构造函数。我建议你阅读 the basics Or this answer.

但在这种特定情况下，调用 new TrieNode('X') 将创建一个 JavaScript object，基本上如下所示：

{ key: 'X', parent: null, children: {}, end: false }

如何将对象视为数组并遍历它并将响应保存在 javascript 中，并使用 trie 数据结构？

How an object can be treated as an array and iterates through it and save the response in javascript with trie data structure?

javascript

trie

family-tree

node.js