Problem with binary tree program

This is a discussion on Problem with binary tree program within the C++ Programming forums, part of the General Programming Boards category; In my program, I pick a pivot p from a database S of strings, compute the median r of the ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    2

    Problem with binary tree program

    In my program, I pick a pivot p from a database S of strings, compute the median r of the distances of other string objects to p and then divide the other objects into roughly equal-sized subsets S1 and S2 as follows:
    S1={o e S \{p}|d(p,o)<r}
    S2={o e S \{p}|d(p,o)>=r}
    where d(p,o) is the distance of the database object o to pivot p.Thus, the objects in S1 are inside the ball of radius r around p, while the objects in S2 are outside this ball. Applying this rule recursively leads to a binary tree,where a pivot object is stored in each internal node, with the left and right subtrees corresponding to the subsets inside and outside the corresponding ball,respectively.

    Below I give the function for the above criteria but when I call the function from main and try to print the tree in preorder, nothing gets printed nor does the program terminate. I will really appreciate if someone can help me find the errors in my code and where I am going wrong:

    Code:
    void query_ball()
    {
    
    string str;
    int i=0,p;
    int arr[1000];
    char B[40];
    char C[40];
    vector<string> myStrings(1000);
    int r;
    int n1;
    
    ifstream file("text.txt"); //this file is the database containing 1000 strings
    
    for(p=0;p<1000;p++)
    {
    getline(file,str);
    strcpy(B,str.c_str());
    myStrings[p]=B; // copying the file strings to vector myStrings
    }
    srand(time(0));
    int pos;
    pos=rand()%1000;
    strcpy(C,myStrings[pos].c_str()); // C is the pivot picked randomly
    
    for(i=pos;i<=998;i++) // deleting element at myStrings[pos] which contains pivot C
    myStrings[i]=myStrings[i+1];
    
    myStrings[i]="";
    
    
    for(p=0;p<999;p++)
    {
    strcpy(B,myStrings[p].c_str());
    arr[p]=edit(B,C); // arr contains edit distances between other string objects and pivot C
    }
    
    /*edit function relates to edit distances of pivot from other string objects. An edit distance between 2 strings is found by changing one string to another with the minimum number of insertions, deletions and/or replacement of characters in the strings.*/
    
    n1=(999+1)/2;
    r=arr[n1]; // r is the median of the distances of other objects to pivot C
    
    for (p=-1; p<999; p++) //p starts with -1 to check first if Root is Null
    {
    
    if (Root == NULL)
    {
    Root = new TreeNode();
    Root->val = C;
    }
    
    else
    {
    TreeNode* temp = Root;
    while(temp!=NULL)
    { strcpy(B,myStrings[p].c_str());
    
    
    if (edit(B,C)<r) // checking distances inside ball of radius r
    {
    if (temp->LChild==NULL)
    { TreeNode* t = new TreeNode();
    t->val = B;
    
    temp->LChild=t;
    }
    else
    {
    TreeNode* t = new TreeNode();
    t->val = B;
    temp->LChild = temp->LChild->t;
    
    }
    }
    
    if (edit(B,C)>=r) // checking distances outside ball of radius r
    {
    
    if (temp->RChild==NULL)
    { TreeNode* t = new TreeNode();
    t->val = B;
    
    temp->RChild=t;
    }
    
    else
    {
    TreeNode* t = new TreeNode();
    t->val = B;
    temp->RChild = temp->RChild->t;
    
    }
    }
    }
    
    }
    }
    
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Fix your indentation, then we'll take a look at it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    also using strcpy and char[] buffers is like the stone age of C++. Where you learning C++ from?

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    2
    In my program, I pick a pivot p from a database S of strings, compute the median r of the distances of other string objects to p and then divide the other objects into roughly equal-sized subsets S1 and S2 as follows:
    S1={o e S \{p}|d(p,o)<r}
    S2={o e S \{p}|d(p,o)>=r}
    where d(p,o) is the distance of the database object o to pivot p.Thus, the objects in S1 are inside the ball of radius r around p, while the objects in S2 are outside this ball. Applying this rule recursively leads to a binary tree,where a pivot object is stored in each internal node, with the left and right subtrees corresponding to the subsets inside and outside the corresponding ball,respectively.

    Below I give the function for the above criteria but when I call the function from main and try to print the tree in preorder, nothing gets printed nor does the program terminate. I will really appreciate if someone can help me find the errors in my code and where I am going wrong:

    Code:
    void query_ball()
    {
    
       string str;
       int i=0,p;
       int arr[1000];
       char B[40];
       char C[40];
       vector<string> myStrings(1000);
       int r;
       int n1;
    
       ifstream file("text.txt"); //this file is the database containing 1000 strings
    
       for(p=0;p<1000;p++)
      {
           getline(file,str);
           strcpy(B,str.c_str());
           myStrings[p]=B; // copying the file strings to vector myStrings
       }
       
       srand(time(0));
       int pos;
       pos=rand()%1000;
       strcpy(C,myStrings[pos].c_str()); // C is the pivot picked randomly
    
       for(i=pos;i<=998;i++) // deleting element at myStrings[pos] which contains   pivot C
            myStrings[i]=myStrings[i+1];
    
        myStrings[i]="";
    
    
       for(p=0;p<999;p++)
      {
             strcpy(B,myStrings[p].c_str());
             arr[p]=edit(B,C); // arr contains edit distances between other string    objects and pivot C
       }
    
    /*edit function relates to edit distances of pivot from other string objects. An edit distance between 2 strings is found by changing one string to another with the minimum number of insertions, deletions and/or replacement of characters in the strings.*/
    
       n1=(999+1)/2;
       r=arr[n1]; // r is the median of the distances of other objects to pivot C
    
       for (p=-1; p<999; p++) //p starts with -1 to check first if Root is Null
       {
    
             if (Root == NULL)
           {
               Root = new TreeNode();
               Root->val = C;
            }
    
          else
           {
                TreeNode* temp = Root;
                 while(temp!=NULL)
             {       
                   strcpy(B,myStrings[p].c_str());
    
                    if (edit(B,C)<r) // checking distances inside ball of radius r
                  {
                       if (temp->LChild==NULL)
                      {            
                            TreeNode* t = new TreeNode();
                            t->val = B;
                            temp->LChild=t;
                       }
                        else
                       {
                            TreeNode* t = new TreeNode();
                             t->val = B;
                             temp->LChild = temp->LChild->t;
    
                         }
                      }
    
                     if (edit(B,C)>=r) // checking distances outside ball of radius r
                     {
    
                           if (temp->RChild==NULL)
                          { 
                              TreeNode* t = new TreeNode();
                               t->val = B;
                               temp->RChild=t;
                           }
    
                           else
                           {
                              TreeNode* t = new TreeNode();
                               t->val = B;
                               temp->RChild = temp->RChild->t;
    
                              }
                      }
            }
    
        }
     }
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undirected graph and Binary Tree problem
    By arafat21 in forum C Programming
    Replies: 3
    Last Post: 05-02-2008, 05:52 AM
  2. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 10:42 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21