-
December 16th, 2014, 06:22 PM
#1
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
-
December 17th, 2014, 12:49 AM
#2
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
-
December 17th, 2014, 08:36 AM
#3
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.
-
December 17th, 2014, 10:00 AM
#4
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.
-
December 17th, 2014, 04:59 PM
#5
Re: Adding element into an n-ary Tree
Originally Posted by monarch_dodra
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
-
December 17th, 2014, 05:18 PM
#6
Re: Adding element into an n-ary Tree
Originally Posted by Sheera
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++23 Compiler: Microsoft VS2022 (17.6.5)
-
December 17th, 2014, 06:29 PM
#7
Re: Adding element into an n-ary Tree
Originally Posted by 2kaud
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.
-
December 18th, 2014, 04:49 AM
#8
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.
Originally Posted by Sheera
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:
Originally Posted by Sheera
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.
-
December 18th, 2014, 05:22 AM
#9
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++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|