1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Problem with binary tree program

Discussion in 'C' started by rsk8332, Apr 9, 2008.

  1. rsk8332

    rsk8332 New Member

    Joined:
    Feb 23, 2008
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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;
                                 
                   }
                }  
       }
    
    }
    }
    
    }
     
    Last edited by a moderator: Apr 9, 2008

Share This Page