DaniWeb Forum Index > Software Development > C++

C++ RSS

N-ary Trees

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

N-ary Trees

Feb 26th, 2009

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.

 Help with Code Tags 
 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;
   ....
   }
}

•

Join Date: Dec 2005

Posts: 5,850

Reputation: Salem has a reputation beyond repute

Solved Threads: 749

Salem

Offline

Void main'ers are DOOMed

Re: N-ary Trees

Feb 26th, 2009

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.

•

Join Date: Oct 2008

Posts: 476

Reputation: nucleon has a spectacular aura about

Solved Threads: 91

nucleon

Offline

Posting Pro in Training

Re: N-ary Trees

Feb 26th, 2009

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:

 Help with Code Tags 
 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.

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

Re: N-ary Trees

Feb 26th, 2009

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?

•

Join Date: Oct 2008

Posts: 476

Reputation: nucleon has a spectacular aura about

Solved Threads: 91

nucleon

Offline

Posting Pro in Training

Re: N-ary Trees

Feb 26th, 2009

I think you'll need something like this:

 Help with Code Tags 
 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.

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

Re: N-ary Trees

Feb 26th, 2009

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.