Как извлечь все данные/слова в натальной в Javascript синтаксического дерева

Question

Я был в состоянии приготовить пример Radix дерева в JavaScript (не оптимизирован, так что не судите)

До сих пор я был в состоянии Add, Transverse и Find узлов.

У меня возникли проблемы при записи функции, которая может retrieve всех узлов, это где я требую assistance.Thank Вы заранее

// 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()); 

Answer 1

Это предложение имеет итеративный и рекурсивный подход для получения слов в дереве.

'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 
 
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 words 
 
console.log(JSON.stringify(tree.retrieveAllNodes(), 0, 4)); 
 
// retrieving whole tree 
 
console.log(JSON.stringify(tree, 0, 4));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Bonus: Ниже версия с очень небольшими накладными расходами.

'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 
 
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 words 
 
console.log(JSON.stringify(tree.retrieveAllNodes(), 0, 4)); 
 
// retrieving whole tree 
 
console.log(JSON.stringify(tree, 0, 4));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Я не уверен, что если вы делаете, что для изучения, но если нет, я предлагаю вам не изобретать велосипед и попробовать библиотеку, которая уже существует для этой цели, например Javid Jamae's RadixTreeJS.