JavaScript中的n-ary树 [英] n-ary tree in JavaScript

问题描述

在JavaScript中存储n-ary树（例如目录层次结构）的最佳方式是什么？

What is the best way to store n-ary tree (ex: directory hierarchy) in JavaScript ?

我需要对其进行以下操作：
1.添加
2.删除
3更新

I need to have following operations on it: 1. add 2. delete 3 update

有没有提供此功能的JavaScript库？

Is there any JavaScript library which provide this feature ?

谢谢，
Gaurav

Thanks, Gaurav

推荐答案

JavaScript对象基本上是键/值对的映射，这意味着如果我正确理解你，你可以直接使用它们。

JavaScript objects are fundamentally maps of key/value pairs, which means you can use them directly for this if I understand you correctly.

例如，假设你在树中存储单词，每个级别都被那个字母键入单词的位置：

For instance, suppose you store words in the tree where each level is keyed by the letter in that position of the word:

function storeWord(t, word) {
    var index, ch, entry;

    for (index = 0; index < word.length; ++index) {
        ch = word.charAt(index);
        entry = t[ch];
        if (!entry) {
            t[ch] = entry = {};
        }
        t = entry;
    }
    t.terminal = true;
}

var tree = {};
storeWord(tree, "test");
storeWord(tree, "testing");
// Results in tree looking like this:
// tree = {
//     t: {
//         e: {
//             s: {
//                 t: {
//                     terminal: true,
//                     i: {
//                         n: {
//                             g: {
//                                 terminal: true
//                             }
//                         }
//                     }
//                 }
//             }
//         }
//     }
// }

根据您的需要，您的条目可能更复杂

Depending on your needs, your entries may be more complex than just being the next level of the tree.

上面显示了存储的基础知识，其中涵盖了添加和更新。

The above shows the basics of storing, which covers both "add" and "update".

对于删除操作，再次取决于数据的组织方式，但是要从对象中删除属性，您可以使用 delete 关键字。最简单的：

For delete operations, again it depends on how your data is organized, but to remove a property from an objcct, you use the delete keyword. At its simplest:

var foo = {};   // A blank object
foo.bar = 42;   // Now it has a property called bar
delete foo.bar; // Now it doesn't, we've _removed_ the property entirely

所以当删除一个单词时，您会发现它是否由树中的终端表示，如果是，则删除终端和导致其变为空的节点。

So when removing a word, you'd find whether it was represented by a terminal in the tree and, if so, remove the terminal and any nodes leading up to it that had become empty.

告诉节点是否为空，您可以使用这样的函数：

To tell whether a node is empty, you can use a function like this:

function emptyNode(node) {
    var name;
    for (name in node) {
        if (node.hasOwnProperty(name)) { // This is optional if you're using raw objects
            return false; // Not empty
        }
    }
    return true; // Empty
}

使用上述，您可以构建一个 deleteWord 函数。

Using the above, you can build a deleteWord function.

这篇关于JavaScript中的n-ary树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！