How to retrieve all the data/words in a radix trie

问题:

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

回答1:

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
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: 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
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; }

回答2:

I'm not sure if you're doing that for studying, but if not, I suggest you to not reinvent the wheel, and try some library that already exists for that purpose, e.g. Javid Jamae's RadixTreeJS.