Ad:

C++ Discussion Thread
Marked Solved
Views: 2883

Feb 26th, 2009

N-ary Trees

Expand Post »

Alright, I need to create an N-ary tree that contains a list of words all of the same length so that we can create a word ladder from it. Given a word (like cat), we are suppose to put that as the root and from a dictionary we are given, supposed to fill in the tree so that nodes point to nodes that are one letter off. So, cat should point to the words like bat, eat, hat, cot, can, cap, etc. The part that seems to be throwing me is that bat needs to also point to the words like eat and hat as well as point to it's select words like bet and bag.

I was working on writing an insert function, but I'm stuck because of that fact. I did arrange the words so that those that were 1 letter off would come first, that way getting listed under the root before attempting to scale the rest of the tree. But I some how need to then compare all the children to the other nodes in the tree, and if off by one, add pointers between them as well.

Would I be better doing that after all the words are in the tree, or should I do that while I insert a new node, or is there a better way to handle this?

And, when making the new node, how should I handle the vector? Should I just let it stay empty until we know that it's the parent of something new, or should I put something in it for the time being? This is what I have so far before actually realizing that I'm not sure what I'm doing.

C++ Syntax (Toggle Plain Text)
struct node
        {
           node* parent;
           vector <node*> children;
           string data;
        };
 
void NTree::insert(string d)
{
    node* t = new node;
    node* parent = NULL;
    vector <node*> children;
    t->data = d;
 
  if(isEmpty()) root = t;  // if new tree, make insert the root
  else
  { node* curr;
    curr = root;
   ....
   }
}
struct node
        {
           node* parent;
           vector <node*> children;
           string data;
        };

void NTree::insert(string d)
{
    node* t = new node;
    node* parent = NULL;
    vector <node*> children;
    t->data = d;

  if(isEmpty()) root = t;  // if new tree, make insert the root
  else
  { node* curr;
    curr = root;
   ....
   }
}

Similar Threads

Creating an n-ary tree in C++
K-ary Trees in Java

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Feb 26th, 2009

Re: N-ary Trees

Post-it notes and a whiteboard would be my suggestion.

If you're still in the dark as to what the nature of the problem really is, then hacking code is the last thing you should be doing.

What you're tying to do is create one of these
http://en.wikipedia.org/wiki/Entity-relationship_model

Some of the more outlandish designs you come up with can be dismissed in a few minutes. But it might take you a week of coding to come to the same conclusion with your existing approach.
But each failure tells you more about the problem, so don't look on this as anything negative.

When you have something which seems to do what you want, and you have some kind of API (insert, delete, find, traverse etc), then simulate some runs to see how it all hangs together.

If that passes muster, then try and implement it.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Feb 26th, 2009

Re: N-ary Trees

I was thinking she needed something more complicated too, but now that I look again, maybe she is looking for an n-ary tree. Taking her example, starting with a given root word (e.g. "cat"), generate all words with one letter different:

C++ Syntax (Toggle Plain Text)
* for each letter in word
  * go through all possible letters
  * if you form a word already in the tree, store a pointer
    to it
  * add new words (found in dictionary) to the list for
    this tree node
* for each letter in word
  * go through all possible letters
  * if you form a word already in the tree, store a pointer
    to it
  * add new words (found in dictionary) to the list for
    this tree node

Then go through all new words, changing only letters that haven't yet been changed, checking for the words' preexistence in the tree, checking if it's a word (in the dictionary), adding it if it is.... This would create an n-ary tree, perhaps with some extra structure.

Maybe that's the kind of thing she's looking for.

nucleon

Reputation Points: 163

Solved Threads: 91

Posting Pro in Training

Offline

476 posts
since Oct 2008

Permalink

Feb 26th, 2009

Re: N-ary Trees

The thing is I have to use an N-ary tree, it's part of the assignment. And I don't want someone to write the code for me, I was asking which was a better way to handle it cause that depends how I write my code. What I'm having issues with is how to actually build it.

Say I'm connecting cat to dog with the below dictionary.
bag, bat, bog, bot, cat, cog, cot, dog, dot, eat, fan, fat, ham, hat, hot

First I rearranged it to correspond to cat, thus getting this.
cat, bat, cot, eat, fat, hat, bag, bot, cog, dot, fan, ham, hot, bog, dog

So, since all the ones that are one off are now at the beginning, we know that all the ones from bat to hat go under cat. The thing is that bat should point to bag and bot, but it should also point to eat, fat, and hat. That's the point I'm asking about.

What is the best way to handle this? While inserting, should I have it search through the nodes in the tree and add pointers to the others nodes that are one letter away? Or, should I insert all the words into the tree first and then go through and point to the nodes that are one letter away from said node?

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Feb 26th, 2009

Re: N-ary Trees

I think you'll need something like this:

C++ Syntax (Toggle Plain Text)
typedef vector<Word*> WordList;
class Word : public string // either inherit from string or contain one
{
    vector<WordList*> v;
public:
    ...
};
typedef vector<Word*> WordList;
class Word : public string // either inherit from string or contain one
{
    vector<WordList*> v;
public:
    ...
};

This amounts to a vector of vectors, which I think you may need.

nucleon

Reputation Points: 163

Solved Threads: 91

Posting Pro in Training

Offline

476 posts
since Oct 2008

Permalink

Feb 26th, 2009

Re: N-ary Trees

Well, right now I'm just working on building the actual tree, which I can't use your suggestion for.

I'm trying to write the tree class functions and I started with the insert function. For each node in the tree, we're suppose to use the struct that he gave us, which I posted above.

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Mar 25th, 2009

Re: N-ary Trees

I think you should ask your professor since its your program for his class.. he gets paid to help you

DevC++4.9.9.2

Reputation Points: 10

Solved Threads: 1

Light Poster

Offline

39 posts
since Apr 2008

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Very urgent..need pan and tompkins heart beat detection and classifiaction code

Next Thread in C++ Forum Timeline: C++ importing a Wave audio file

DaniWeb Message

Cancel Changes

User Name
Password