CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: Adding element into an n-ary Tree

  1. #1
    Join Date
    Dec 2014
    Posts
    4

    Adding element into an n-ary Tree

    Hello everybody,

    Am a bigger programmer and currently I'm implementing a T9 (predective text) project in c++ using n-ary Trees.
    I've never used the n-ary tree before so I really have some difficulties

    I have to add words into the tree, knowing that each node of the tree contains a linked list (for the words) and a vector of pointers to access the next node

    the words should be stockes in the different nodes according to their T9 code and then when the user insert a number, my program should display all the words corresponds to that code. For example the code: 4663 matches "good" "home" "gone" ...and so on...

    I would like to understand how can I add the words into the Tree and how can I display them later

    Here are my structs :

    struct NodeList{
    string data;
    NodeList * next;
    };


    struct List{
    NodeList *head;
    };



    struct TreeNode;


    // the tree root
    struct Tree{
    TreeNode * root;
    };


    typedef vector<TreeNode* > TabChildren;


    //the tree node that contains the linked list and the children(nodes)
    struct TreeNode{
    TabChildren children;
    List words;
    };


    //and then the function to add words into the tree
    void addWords(const string & word, Tree &myTree);


    I hope someone can help me how can I add the words and disply them, Thanks guys for ur time

  2. #2
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Adding element into an n-ary Tree

    Why don't you use std::list instead of your home-made List class?

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Dec 2014
    Posts
    4

    Re: Adding element into an n-ary Tree

    I know it's easier using std::list but we were asked to implement the projet using our own home-made List class, so we learn how to do it.

  4. #4
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Adding element into an n-ary Tree

    Should your nodes hold the number information in some place? Or is the idea that the node's index in its container makes that implicit?

    In any case, to insert a word, I'd decompose it into its numerical representation (eg Book => 2665), and then, "simply" walk down the tree children 2,6,6 and 5 (while creating children if needed), and place the word in the final node.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  5. #5
    Join Date
    Dec 2014
    Posts
    4

    Re: Adding element into an n-ary Tree

    Quote Originally Posted by monarch_dodra View Post
    In any case, to insert a word, I'd decompose it into its numerical representation (eg Book => 2665), and then, "simply" walk down the tree children 2,6,6 and 5 (while creating children if needed), and place the word in the final node.

    That's exactely what I did but it doesn't work

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,188

    Re: Adding element into an n-ary Tree

    Quote Originally Posted by Sheera View Post
    That's exactly what I did but it doesn't work
    So post your code so that we can see what you're tried. When posting code please use code tags. Go Advanced, select the formatted code and click '#'. What debugging of this code have you done?
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.0)

  7. #7
    Join Date
    Dec 2014
    Posts
    4

    Re: Adding element into an n-ary Tree

    Quote Originally Posted by 2kaud View Post
    So post your code so that we can see what you're tried. When posting code please use code tags. Go Advanced, select the formatted code and click '#'. What debugging of this code have you done?

    Here's my code without the main:

    Code:
    struct NodeList{
        string data;
        NodeList * next;
    };
    
    
    struct List{
        NodeList *head;
    };
    
    NodeList * newNode(string word, NodeList * pointer = nullptr)
    {
        NodeList * ptr = new NodeList;
        ptr -> data = word;
        ptr -> next = pointer;
        return ptr;
    }
    
    void createList(List & wordsLst)
    {
        wordsLst.head = nullptr;
    }
    
    
    struct TreeNode;
    
    // the tree root
    struct Tree{
        TreeNode * root;
    };
    
    typedef vector<TreeNode* > TabChildren;
    
    //the tree node that contains the linked list and the children(nodes)
    struct TreeNode{
        TabChildren children;
        List words;
    };
    
    
    
    TreeNode *newTreeNode(TabChildren children, List words){
        
        TreeNode * nodePointer = new TreeNode;
        nodePointer -> children = children;
        nodePointer -> words = words;
        
        return nodePointer;
        
    }
    
    void createTree(Tree & t9Tree){
        
        t9Tree.root = new TreeNode;
        t9Tree.root -> words.head = nullptr;
        t9Tree.root -> children.resize(8);
        
        for (int i=2; i<=9; i++) {
            t9Tree.root -> children[i] = nullptr;
        }
    }
    
    TreeNode *addChild(Tree & t9Tree, string const word)
    {
        TreeNode *node = t9Tree.root;
        
        string numericalValue;
        numericalValue = toNumber(word); // a function that gives the numerical value of a word
        
        for (int i=0; i<numericalValue.length(); i++) {
            if (node->children[i] == nullptr)
                node = node->children[i] = new TreeNode;
        }
        return node;
    }
    
    bool addWord(const string & word, Tree & t9Tree)
    {
        List wordsList;
        
        if(t9Tree.root == nullptr)
            addChild(t9Tree, word);
            // adding at the begining of the list
            if(wordsList.head == nullptr) {
                wordsList.head = newNode(word, wordsList.head);
                return true;
            }
        
        NodeList * pointer = wordsList.head;
        
        // if the value exists already
        if(pointer->data == word)
            return false;
        
        // otherwise we continue
        while(pointer->next != nullptr)
            pointer = pointer->next;
        
        if(pointer->next == nullptr) {
            pointer->next = newNode(word, pointer->next);
            return true;
        }
        return false;
    }


    sorry for not using code tags earlier, this is my first post int the forum and am still not used to it.
    Last edited by Sheera; December 18th, 2014 at 12:47 AM.

  8. #8
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Adding element into an n-ary Tree

    My first comment is: "I know it's easier using std::list but we were asked to implement the projet using our own home-made List class, so we learn how to do it." I don't see a home made list class here. If you had an actual list class, you wouldn't have to manipulate "NodeList" inside your Tree implementation. That's just basic encapsulation. I *strongly* recommend you do the project WITH std::list, and then once that works, replace with your own class, *that has the same interface*.

    Also, use member functions and encapsulation.

    Quote Originally Posted by Sheera View Post
    That's exactely what I did but it doesn't work
    Really? Your code is a mess. You need to really take it slow, and make sure what you have written works before going forward. There's literally about one bug per line.

    Also, this is a complicated project, I *STRONGLY* suggest you learn to use your debugger to be able to see "what your program is really doing" vs "what you think it does/should do"

    In particular, I'd *START* by writing the function that *DUMPS* your tree so you can investigate it:

    Quote Originally Posted by Sheera View Post
    Code:
    void createTree(Tree & t9Tree){
        
        t9Tree.root = new TreeNode;
        t9Tree.root -> words.head = nullptr;
        t9Tree.root -> children.resize(8);  //Is that really all you need?
        
        for (int i=2; i<=9; i++) {
            t9Tree.root -> children[i] = nullptr;
        }
    }
    
    TreeNode *addChild(Tree & t9Tree, string const word)
    {
        TreeNode *node = t9Tree.root;
        
        string numericalValue;
        numericalValue = toNumber(word); // a function that gives the numerical value of a word
        
        for (int i=0; i<numericalValue.length(); i++) {
            if (node->children[i] == nullptr)
                node = node->children[i] = new TreeNode;
            else
                ??? Maybe you want to walk down the tree here?
        }
        //So at what point did you insert *something* into the tree?
        return node;
    }
    
    bool addWord(const string & word, Tree & t9Tree)
    {
        List wordsList;
        
        if(t9Tree.root == nullptr)
            addChild(t9Tree, word);
            You did not put a block on your if... Your indentation is wrong.
            // adding at the begining of the list
            if(wordsList.head == nullptr) { //How could this not be null?
                wordsList.head = newNode(word, wordsList.head);
                return true;
            }
        
        NodeList * pointer = wordsList.head;
        
        //This checks only the last value.
        // if the value exists already
        if(pointer->data == word)
            return false;
        
        //This will get you to the last value, but doesn't check anything
        // otherwise we continue
        while(pointer->next != nullptr)
            pointer = pointer->next;
        
        //This is now always true, per the above lo
        if(pointer->next == nullptr) {
            pointer->next = newNode(word, pointer->next);
            return true;
        }
        return false;
    
        Ok... so what about wordsList? Shouldn't you insert that in your tree somewhere?
    }
    sorry for not using code tags earlier, this is my first post int the forum and am still not used to it.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,188

    Re: Adding element into an n-ary Tree

    Have you actually designed this program before you started to code? For something like this I would strongly advise this. Also it seems to me that this would be suited to be a class - rather than separate structs and functions.

    When trying to debug code like this, I find it useful to use pen and paper to draw the tree as produced by the code in conjunction with using the debugger (familiarity with the debugger is an essential skill that I would strongly suggest is quickly acquired). This usually quickly identifies issues with the design/code.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.0)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)