如何检索在Javascript基数特里的所有数据/字 [英] How to retrieve all the data/words in a radix trie in Javascript

问题描述

我已经能够煮了在JavaScript基数树的例子（没有优化，所以不要判断）

到目前为止，我已经能够添加，横向和查找节点。

我无法写一个函数，可以检索所有节点，这是我需要assistance.Thank提前

  //如图：
// http://programminggeeks.com/c-$c$c-for-radix-tree-or-trie/

//使一类的树，这样你可以定义方法树的所有节点
//这实际上是在结构树继承功能
功能树（）{
    this.character =不确定的;

    //如果此节点是一个完整的单词的末尾
    //这是我们能够区分卖和卖，如果两者都搜索
    this.isword = FALSE;

    //如何巢节点，这样就产生一个树结构
    this.node = {}; // [新树（），新树（），新树（）];

    // ABCDEFGHIJKLMNOPQRSTUVWXYZ
    VAR开始= 97，
        结束=启动+ 25;

    函数构造函数（）{
        对于（VAR X =启动，X＆LT; =结束; X ++）{
            //现在他们都是未签名的对象
            that.node [X] = NULL //新树（）
        }
        返回;
    }

    构造函数（本）;
    回到这一点;
}

Tree.prototype.addNode =功能（字）{
    返回this.transverseNodes（文字，真实）;
};

Tree.prototype.searchForNodes =功能（字）{
    返回this.transverseNodes（字，假）;
};

Tree.prototype.stringToNodes =功能（字）{
    VAR nodeArray = []
    为（变种X = 0，长度= word.length; X  - 其中，长度，X ++）{
        nodeArray.push（word.char $ C $猫（X））;
    }
    返回nodeArray;
};

Tree.prototype.transverseNodes =功能（文字，布尔）{
    //使所有字母的小写创建一致性
    变种节点= this.stringToNodes（word.toLowerCase（））;
    //的console.log（节点）;

    //启动与父/根椐
    VAR currentTreeNode =本

    //横向如果节点已被添加，如果不加检查它
    //如果它已经加入并终止字设置isword属性设置为true
    对于（VAR I = 0，长度= nodes.length; I＆LT;长度;我++）{
        VAR节点=节点[I]

        //如果当前树节点的定义，因此未将其覆盖
        如果（currentTreeNode.node [节点] === NULL）{

            如果（！布尔）{
                //如果布尔未定义的假的，那么这是一个搜索
                返回false;
            }

            //创建一个节点
            currentTreeNode.node [节点] =新树（）;
            currentTreeNode.node [节点] .character = String.fromChar code（节点）;
        }

        //检查节点是该字的最后一个字符
        如果（（nodes.length  -  1）===我）{
            //执行console.log（nodes.length  -  1，I）
            如果（！布尔）{
                //如果布尔未定义的假的，那么这是一个搜索
                返回true;
            }

            currentTreeNode.node [节点] .isword = TRUE;
        }

        //进入嵌套的节点
        currentTreeNode = currentTreeNode.node [节点]
    };

    回到这一点;
};

VAR树=新树（）

//创建节点
tree.addNode（猫）;
tree.addNode（骆驼）;
tree.addNode（安全套）;
tree.addNode（大灾难）;
tree.addNode（奶奶）;
tree.addNode（lamboghini）;

//搜索节点
的console.log（tree.searchForNodes（猫））; // 真正
的console.log（tree.searchForNodes（投石车））; // 假
的console.log（tree.searchForNodes（大灾难））; // 真正
的console.log（tree.searchForNodes（妈妈））; // 假
的console.log（tree.searchForNodes（lamboghini））; // 真正

//检索所有节点
//的console.log（tree.retrieveAllNodes（））;
 

解决方案

这个提议设有一个迭代和递归的方法获取的树中的话。

使用严格的; //如图： // http://programminggeeks.com/c-$c$c-for-radix-tree-or-trie/ //使一类的树，这样你可以定义方法树的所有节点 //这实际上是在结构树继承功能 功能树（）{     this.character =不确定的;     //如果此节点是一个完整的单词的末尾     //这是我们能够区分卖和卖，如果两者都搜索     this.isword = FALSE;     //如何巢节点，这样就产生一个树结构     this.node = {}; // [新树（），新树（），新树（）];     // ABCDEFGHIJKLMNOPQRSTUVWXYZ     VAR开始= 97，         结束=启动+ 25;     函数构造函数（）{         对于（VAR X =启动，X＆LT; =结束; X ++）{             //现在他们都是未签名的对象             that.node [X] = NULL //新树（）         }         返回;     }     构造函数（本）;     回到这一点; } Tree.prototype.addNode =功能（字）{     返回this.transverseNodes（文字，真实）; }; Tree.prototype.searchForNodes =功能（字）{     返回this.transverseNodes（字，假）; }; Tree.prototype.stringToNodes =功能（字）{     VAR nodeArray = []     为（变种X = 0，长度= word.length; X - 其中，长度，X ++）{         nodeArray.push（word.char $ C $猫（X））;     }     返回nodeArray; }; Tree.prototype.transverseNodes =功能（文字，布尔）{     //使所有字母的小写创建一致性     变种节点= this.stringToNodes（word.toLowerCase（））;     //的console.log（节点）;     //启动与父/根椐     VAR currentTreeNode =本     //横向如果节点已被添加，如果不加检查它     //如果它已经加入并终止字设置isword属性设置为true     对于（VAR I = 0，长度= nodes.length; I＆LT;长度;我++）{         VAR节点=节点[I]         //如果当前树节点的定义，因此未将其覆盖         如果（currentTreeNode.node [节点] === NULL）{             如果（！布尔）{                 //如果布尔未定义的假的，那么这是一个搜索                 返回false;             }             //创建一个节点             currentTreeNode.node [节点] =新树（）;             currentTreeNode.node [节点] .character = String.fromChar code（节点）;         }         //检查节点是该字的最后一个字符         如果（（nodes.length - 1）===我）{             //执行console.log（nodes.length - 1，I）             如果（！布尔）{                 //如果布尔未定义的假的，那么这是一个搜索                 返回true;             }             currentTreeNode.node [节点] .isword = TRUE;         }         //进入嵌套的节点         currentTreeNode = currentTreeNode.node [节点]     };     回到这一点; }; Tree.prototype.retrieveAllNodes =功能（）{     //函数穿越过的对象，作为对象和一个空字符串     //出现的词语，作为封闭的对象     功能iterObject（O，R）{         //我怎么样开始，返回功能（...）         //基本返回了未来的话。         //之所以减少，这提供了一个返回值，用字母         //路径的         返回Object.keys（O）。降低（函数（R，键）{             //检查钥匙酒店有truthy值（记住默认             //空值）             如果（O [关键]）{                 //如果是这样，检查物业isword                 如果（O [关键] .isword）{                     //如果在这里的truty，我们有一个打，一个字被发现                     wordList.push（R + O [关键] .character）;                 };                 //检查儿童                 如果（O [关键] .node）{                     //如果节点存在，去一个新的迭代，一个新词                     //扩展                     iterObject（O [关键] .node，R + O [关键] .character）;                 }             }             //返回不可避免的词干             返回ř;         }，r）的;     }     VAR单词表= [];     iterObject（this.node，''）;     返回词表; } VAR树=新树（）; //创建节点 tree.addNode（猫）; tree.addNode（骆驼）; tree.addNode（安全套）; tree.addNode（大灾难）; tree.addNode（奶奶）; tree.addNode（lamboghini）; //搜索节点 snippet.log（tree.searchForNodes（猫））; // 真正 snippet.log（tree.searchForNodes（投石车））; // 假 snippet.log（tree.searchForNodes（大灾难））; // 真正 snippet.log（tree.searchForNodes（妈妈））; // 假 snippet.log（tree.searchForNodes（lamboghini））; // 真正 //获取所有单词 snippet.log（JSON.stringify（tree.retrieveAllNodes（），0，4），'pre'）; //获取整个树 snippet.log（JSON.stringify（树，0,4），'pre'）;

！

＆LT; - 提供'snippet`对象，请参阅http：// meta.stackexchange.com/a/242144/134069 - ＆GT; ＆LT;脚本SRC =htt​​p://tjcrowder.github.io/simple-snippets-console/snippet.js＆GT;＆LT; / SCRIPT＆GT;

奖励：下面是一个版本，非常小的开销。

使用严格的; 功能树（）{     回到这一点; } Tree.prototype.addNode =功能（字）{     this.stringToNodes（字）。降低（功能（节点，性格，I，A）{         如果（！节点[人物]）{             节点[人物] = {};         }         如果（我===则为a.length - 1）{             节点【性状】.isword = TRUE;         }         返回节点【性状】;     }， 本）;     回到这一点; }; Tree.prototype.searchForNodes =功能（字）{     功能iterObject（O，R）{         返回Object.keys（O）。降低（函数（R，键）{             如果（关键===isword'和;＆安培; R ===字）{                 发现= TRUE;             }             typeof运算的问题o [关键] ==='对象'和;＆安培; iterObject（O [关键]，R +键）;             返回ř;         }，r）的;     }     VAR发现= FALSE;     iterObject（此，''）;     返回发现; }; Tree.prototype.stringToNodes =功能（字）{     返回word.toLowerCase（）分裂（''）。 }; Tree.prototype.retrieveAllNodes =功能（）{     功能iterObject（O，R）{         返回Object.keys（O）。降低（函数（R，键）{             关键===isword'和;＆安培; wordList.push（r）的;             typeof运算的问题o [关键] ==='对象'和;＆安培; iterObject（O [关键]，R +键）;             返回ř;         }，r）的;     }     VAR单词表= [];     iterObject（此，''）;     返回词表; } VAR树=新树（）; //创建节点 tree.addNode（猫）; tree.addNode（骆驼）; tree.addNode（安全套）; tree.addNode（大灾难）; tree.addNode（奶奶）; tree.addNode（lamboghini）; //搜索节点 snippet.log（tree.searchForNodes（猫））; // 真正 snippet.log（tree.searchForNodes（投石车））; // 假 snippet.log（tree.searchForNodes（大灾难））; // 真正 snippet.log（tree.searchForNodes（妈妈））; // 假 snippet.log（tree.searchForNodes（lamboghini））; // 真正 //获取所有单词 snippet.log（JSON.stringify（tree.retrieveAllNodes（），0，4），'pre'）; //获取整个树 snippet.log（JSON.stringify（树，0,4），'pre'）;

！

＆LT; - 提供'snippet`对象，请参阅http：// meta.stackexchange.com/a/242144/134069 - ＆GT; ＆LT;脚本SRC =htt​​p://tjcrowder.github.io/simple-snippets-console/snippet.js＆GT;＆LT; / SCRIPT＆GT;

I've been able to cook up a Radix tree example in JavaScript (not optimised, so don't judge)

So far I have been able to Add, Transverse and Find nodes.

I'm having trouble writing a function that can retrieve all nodes, this is where I require assistance.Thank you in advance

// As illustrated in:
// http://programminggeeks.com/c-code-for-radix-tree-or-trie/

// Make a class of the Tree so that you can define methods all nodes of the tree
// which are actually Trees in structure inherit the functions
function Tree() {
    this.character = undefined;

    // if this node is the end of a complete word
    // this was we can differentiate "sell" and "sells" if both are searched for
    this.isword = false;

    // How to nest the nodes, thus creating a tree structure
    this.node = {}; // [new Tree(), new Tree(), new Tree()];

    // abcdefghijklmnopqrstuvwxyz
    var start = 97,
        end = start + 25;

    function constructor(that) {
        for (var x = start; x <= end; x++) {
            // for now they are all unsigned objects
            that.node[x] = null // new Tree()
        }
        return that;
    }

    constructor(this);
    return this;
}

Tree.prototype.addNode = function(word) {
    return this.transverseNodes(word, true);
};

Tree.prototype.searchForNodes = function(word) {
    return this.transverseNodes(word, false);
};

Tree.prototype.stringToNodes = function(word) {
    var nodeArray = []
    for (var x = 0, length = word.length; x < length; x++) {
        nodeArray.push(word.charCodeAt(x));
    }
    return nodeArray;
};

Tree.prototype.transverseNodes = function(word, bool) {
    // make all of the letters lowercase to create uniformity
    var nodes = this.stringToNodes(word.toLowerCase());
    // console.log(nodes);

    // start with parent/root tree
    var currentTreeNode = this

    // transverse checking if node has been added, if not add it
    // if it was already added and it terminates a word set it "isword" property to true
    for (var i = 0, length = nodes.length; i < length; i++) {
        var node = nodes[i];

        // If the current tree node is defined so not overwrite it
        if (currentTreeNode.node[node] === null) {

            if (!bool) {
                // if bool is undefined of false, then this is a search
                return false;
            }

            // create a node
            currentTreeNode.node[node] = new Tree();
            currentTreeNode.node[node].character = String.fromCharCode(node);
        }

        // check if the node is the last character of the word
        if ((nodes.length - 1) === i) {
            // console.log(nodes.length - 1, i)
            if (!bool) {
                // if bool is undefined of false, then this is a search
                return true;
            }

            currentTreeNode.node[node].isword = true;
        }

        // get into the nested node
        currentTreeNode = currentTreeNode.node[node];
    };

    return this;
};

var tree = new Tree()

// Create the nodes
tree.addNode("cat");
tree.addNode("camel");
tree.addNode("condom");
tree.addNode("catastrophe");
tree.addNode("grandma");
tree.addNode("lamboghini");

// Search the nodes
console.log(tree.searchForNodes("cat")); // true
console.log(tree.searchForNodes("catapult")); // false
console.log(tree.searchForNodes("catastrophe")); // true
console.log(tree.searchForNodes("mama")); // false
console.log(tree.searchForNodes("lamboghini")); // true

// retrieving all node
// console.log(tree.retrieveAllNodes());

解决方案

This proposal features an iterative and recursive approach for getting the words in the tree.

'use strict';
// As illustrated in:
// http://programminggeeks.com/c-code-for-radix-tree-or-trie/

// Make a class of the Tree so that you can define methods all nodes of the tree
// which are actually Trees in structure inherit the functions
function Tree() {
    this.character = undefined;

    // if this node is the end of a complete word
    // this was we can differentiate "sell" and "sells" if both are searched for
    this.isword = false;

    // How to nest the nodes, thus creating a tree structure
    this.node = {}; // [new Tree(), new Tree(), new Tree()];

    // abcdefghijklmnopqrstuvwxyz
    var start = 97,
        end = start + 25;

    function constructor(that) {
        for (var x = start; x <= end; x++) {
            // for now they are all unsigned objects
            that.node[x] = null // new Tree()
        }
        return that;
    }

    constructor(this);
    return this;
}

Tree.prototype.addNode = function (word) {
    return this.transverseNodes(word, true);
};

Tree.prototype.searchForNodes = function (word) {
    return this.transverseNodes(word, false);
};

Tree.prototype.stringToNodes = function (word) {
    var nodeArray = []
    for (var x = 0, length = word.length; x < length; x++) {
        nodeArray.push(word.charCodeAt(x));
    }
    return nodeArray;
};

Tree.prototype.transverseNodes = function (word, bool) {
    // make all of the letters lowercase to create uniformity
    var nodes = this.stringToNodes(word.toLowerCase());
    // console.log(nodes);

    // start with parent/root tree
    var currentTreeNode = this

    // transverse checking if node has been added, if not add it
    // if it was already added and it terminates a word set it "isword" property to true
    for (var i = 0, length = nodes.length; i < length; i++) {
        var node = nodes[i];

        // If the current tree node is defined so not overwrite it
        if (currentTreeNode.node[node] === null) {

            if (!bool) {
                // if bool is undefined of false, then this is a search
                return false;
            }

            // create a node
            currentTreeNode.node[node] = new Tree();
            currentTreeNode.node[node].character = String.fromCharCode(node);
        }

        // check if the node is the last character of the word
        if ((nodes.length - 1) === i) {
            // console.log(nodes.length - 1, i)
            if (!bool) {
                // if bool is undefined of false, then this is a search
                return true;
            }
            currentTreeNode.node[node].isword = true;
        }

        // get into the nested node
        currentTreeNode = currentTreeNode.node[node];
    };

    return this;
};

Tree.prototype.retrieveAllNodes = function () {

    // function for traversing over object, takes the object and an empty string for
    // the appearing words, acts as closure for the object
    function iterObject(o, r) {
        // how i like to start functions with return (...)
        // returns basically the up coming word.
        // reason for reduce, this provides a return value, with the letters
        // of the path
        return Object.keys(o).reduce(function (r, key) {
            // check if the key property has a truthy value (remember the default
            // null values)
            if (o[key]) {
                // if so, check the property isword
                if (o[key].isword) {
                    // if its truty here, we have a hit, a word is found
                    wordList.push(r + o[key].character);
                };
                // check for children
                if (o[key].node) {
                    // if node exist, go on with a new iteration and a new word
                    // extension
                    iterObject(o[key].node, r + o[key].character);
                }
            }
            // return the inevitable word stem
            return r;
        }, r);
    }

    var wordList = [];
    iterObject(this.node, '');
    return wordList;
}

var tree = new Tree();

// Create the nodes
tree.addNode("cat");
tree.addNode("camel");
tree.addNode("condom");
tree.addNode("catastrophe");
tree.addNode("grandma");
tree.addNode("lamboghini");

// Search the nodes
snippet.log(tree.searchForNodes("cat")); // true
snippet.log(tree.searchForNodes("catapult")); // false
snippet.log(tree.searchForNodes("catastrophe")); // true
snippet.log(tree.searchForNodes("mama")); // false
snippet.log(tree.searchForNodes("lamboghini")); // true

// retrieving all words
snippet.log(JSON.stringify(tree.retrieveAllNodes(), 0, 4), 'pre');
// retrieving whole tree
snippet.log(JSON.stringify(tree, 0, 4), 'pre');

<!-- Provides the `snippet` object, see http://meta.stackexchange.com/a/242144/134069 -->
<script src="http://tjcrowder.github.io/simple-snippets-console/snippet.js"></script>

Bonus: Below is a version with very small overhead.

'use strict';
function Tree() {
    return this;
}

Tree.prototype.addNode = function (word) {
    this.stringToNodes(word).reduce(function (node, character, i, a) {
        if (!node[character]) {
            node[character] = {};
        }
        if (i === a.length - 1) {
            node[character].isword = true;
        }
        return node[character];
    }, this);
    return this;
};

Tree.prototype.searchForNodes = function (word) {

    function iterObject(o, r) {
        return Object.keys(o).reduce(function (r, key) {
            if (key === 'isword' && r === word) {
                found = true;
            }
            typeof o[key] === 'object' && iterObject(o[key], r + key);
            return r;
        }, r);
    }

    var found = false;
    iterObject(this, '');
    return found;
};


Tree.prototype.stringToNodes = function (word) {
    return word.toLowerCase().split('');
};

Tree.prototype.retrieveAllNodes = function () {

    function iterObject(o, r) {
        return Object.keys(o).reduce(function (r, key) {
            key === 'isword' && wordList.push(r);
            typeof o[key] === 'object' && iterObject(o[key], r + key);
            return r;
        }, r);
    }

    var wordList = [];
    iterObject(this, '');
    return wordList;
}

var tree = new Tree();

// Create the nodes
tree.addNode("cat");
tree.addNode("camel");
tree.addNode("condom");
tree.addNode("catastrophe");
tree.addNode("grandma");
tree.addNode("lamboghini");

// Search the nodes
snippet.log(tree.searchForNodes("cat")); // true
snippet.log(tree.searchForNodes("catapult")); // false
snippet.log(tree.searchForNodes("catastrophe")); // true
snippet.log(tree.searchForNodes("mama")); // false
snippet.log(tree.searchForNodes("lamboghini")); // true

// retrieving all words
snippet.log(JSON.stringify(tree.retrieveAllNodes(), 0, 4), 'pre');
// retrieving whole tree
snippet.log(JSON.stringify(tree, 0, 4), 'pre');

<!-- Provides the `snippet` object, see http://meta.stackexchange.com/a/242144/134069 -->
<script src="http://tjcrowder.github.io/simple-snippets-console/snippet.js"></script>

这篇关于如何检索在Javascript基数特里的所有数据/字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！