problem with trees

If you are a new Irrlicht Engine user, and have a newbie-question, this is the forum for you. You may also post general programming questions here.
Post Reply
pibeytor
Posts: 17
Joined: Thu Nov 01, 2007 2:13 pm

problem with trees

Post by pibeytor »

hi everyone

I've been working with something and I'm a little lost..

**the code is in english**, just find and replace jijij

there are 2 functions left: print and check spelling.
it's like a syntax corrector.

you write your word and the program tells you if you got some errors and
tells you what options are correct...

like ms word, but more simple...



this is what i got so far:
the program just add words to the memory... but doesn't print or compare any.


hope you can help me out.
thank you very much for your time.

ps. i will incorporate irrlicht user interface after.

Code: Select all

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

class node{
   public:
      node(char l){
      letter=l;
      brother = NULL;
      upper_left_son=NULL;
      father = NULL;
   }
      char letter;
      node *brother;
      node *upper_left_son;
      node *father;
};//end class - node

class Tree{
public:
   void add(string word);
   void add(node *,node *,string,int,int);
   //void print();	dont know
   //void compare();	dont know

private:
    node *root;
};
void Tree::add(string word)
{
   node *newNode = new node(word[0]);

   if(root == NULL)
   {
      root = newNode;
   }
   else
   {
      for(node *tmp = root; tmp != NULL; tmp = tmp->brother)
      {
         if(tmp->letter==word[0])
         {
            break;
         }

         if(tmp->brother == NULL)
         {
            tmp->brother = newNode;
            break;
         }
      }
   }

   for(int i = 1; i < word.length(); i++)
   {
      newNode = new node(word[i]);
      add(root,newNode,word,0,i);
   }
}

void Tree::add(node *key, node *newNode, string word, int index, int limit)
{
   if (index < limit)
   {
      for(node *temp = key; temp != NULL; temp = temp -> brother )
      {
         if(temp -> letter == word[index])
         {
            add(temp->upper_left_son, newNode , word , index + 1 , limit);
            
            if(index == limit-1)
            {
               if(temp -> upper_left_son == NULL)
               {
                  temp -> upper_left_son = newNode;
               }
               else
               {
                  for(node *temp2 = temp -> upper_left_son ; temp2 != NULL ; temp2 = temp2 -> brother)
                  {
                     if(temp2->letter==word[limit])
                     {
                        break;
                     }

                     if(temp2->brother == NULL)
                     {
                        temp2->brother = newNode;
                        break;
                     }
                  }
               }
            }
         }
      }
   }
}
   
int main(){
string word;
Tree *a = new Tree();

//a bunch of words with "a"
a->add("word");a->add("aaronita");a->add("aba");a->add("ababa");a->add("ababillarse");
a->add("ababol");a->add("abacal");a->add("abacalero");a->add("abacero");a->add("abachar");
a->add("abacora");a->add("abad");a->add("abada");a->add("abadiado");a->add("abandonar");
a->add("anabdonismo");a->add("abandonista");a->add("abanear");a->add("abanico");a->add("abanicazo");
a->add("abanico");a->add("abanillo");a->add("abanino");a->add("abarajar");a->add("abarañar");
a->add("abaratamiento");a->add("abaratar");a->add("abarcar");a->add("acarrado");a->add("abarraganimiento");
a->add("abarraganarse");a->add("abarrajado");a->add("abarrotar");a->add("abarrotero");a->add("abastecimiento");
a->add("abcedario");a->add("abedul");a->add("abejonear");a->add("abellota");a->add("abellotado");



cout<<"Syntax reviewer\n"<<endl;
//String word;

cout<<"type a word: ";
cin>>word;


   return 0;
} 


Last edited by pibeytor on Thu Feb 21, 2008 9:57 pm, edited 1 time in total.
MasterGod
Posts: 2061
Joined: Fri May 25, 2007 8:06 pm
Location: Israel
Contact:

Post by MasterGod »

1. Try to debug it.
2. If you want us to help with your code rewrite it in simple english.
Image
Dev State: Abandoned (For now..)
Requirements Analysis Doc: ~87%
UML: ~0.5%
pibeytor
Posts: 17
Joined: Thu Nov 01, 2007 2:13 pm

Post by pibeytor »

it's translated now.. thx!

by the way.. i'm using visual c++...

the code for "add" works fine; it adds words , but it's still missing 2 functions: compare and print.. i don't know how to show the words in memory to the screen...
zeno60
Posts: 342
Joined: Sun May 21, 2006 2:48 am
Location: NC, USA
Contact:

Post by zeno60 »

Maybe I am missing something, but after a quick glance it appears you are only adding the first letter of any "word" added to the tree. How do you expect to print the word the node contains later if it is not being stored anywhere?

Comparing should be simple enough given the nature of the tree you are attempting to create. A binary tree, where a node has only 1 or 2 child nodes, left and right with the left node being lexicographically smaller (if a string) and the right being lexicographically larger. This also applies to any children of the nodes own children. So comparing something to the head node, if found smaller, you can continue through the left child's children and cut out having to compare with half of the tree (given it was initialized correctly and that it is pretty well balanced.) It is also simple enough to drill through the tree and print as binary trees have the extra special ability to print in a number of different ways (postfix, prefix, infix). Prefix would give you the ability to print your entire tree in alphabetical order (again, if setup correctly) by simply having the node call its left child print method, then its own, then its right childs.

Code: Select all

     d
    / \
   b   e
  / \
a    c 
Post Reply