DaniWeb Forum Index > Software Development > C++

how to print null subtree of a null subtree?

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

Thread Solved

« First

•

Join Date: Aug 2005

Posts: 5,266

Reputation: iamthwee is a splendid one to behold

Solved Threads: 377

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#21

Jan 7th, 2007

•

Originally Posted by sivaslieko++

thanks a lot for everything iamthwee, but I am almost out of mind. I could not make it. I think I should give up

Don't give up!

I have a complete working version right here which I have written myself using my method.

So I CAN guarantee you it does work.

I don't just want to post it however, because you're sooo close.

Like I said read over my examples and apply it to your example.

:p

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 49

Reputation: sivaslieko++ is an unknown quantity at this point

Solved Threads: 0

sivaslieko++ sivaslieko++ is offline

Offline

Light Poster

Re: how to print null subtree of a null subtree?

#22

Jan 7th, 2007

Should I continue to use Queue method or should I completely change it with array method?

While using Queue I stored the pointers to values stored in the tree into the queue and called these values like "p->item" and store each subnode into queue with below code:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
 if(p->left!=NULL)
    myQ.Qinsert(p->left);
 if(p->right!=NULL)
    myQ.Qinsert(p->right);
 if(p->left!=NULL)
    myQ.Qinsert(p->left);
 if(p->right!=NULL)
    myQ.Qinsert(p->right);

But in array method, you store values not pointers into array so I could not call the left subtrees as Queue method? What should I do....

Sory I tire you a bit iamthwee : (

Last edited by WaltP; Jan 7th, 2007 at 2:17 pm. Reason: Please start using CODE tags. See BBCODEs post in the Announcements

•

Join Date: Aug 2005

Posts: 5,266

Reputation: iamthwee is a splendid one to behold

Solved Threads: 377

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#23

Jan 7th, 2007

Use my array example. Yes. You don't need the queue anymore.

Do you want me to explain how to use it with your example.

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 49

Reputation: sivaslieko++ is an unknown quantity at this point

Solved Threads: 0

sivaslieko++ sivaslieko++ is offline

Offline

Light Poster

Re: how to print null subtree of a null subtree?

#24

Jan 7th, 2007

pleaseee

•

Join Date: Aug 2005

Posts: 5,266

Reputation: iamthwee is a splendid one to behold

Solved Threads: 377

iamthwee

Offline

Posting Expert

Re: how to print null subtree of a null subtree?

#25

Jan 7th, 2007

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
            23
            /  \
          1     45
            \    / \
             2  31  52
              \   \
               3  234
                 \
                  5
            23
            /  \
          1     45
            \    / \
             2  31  52
              \   \
               3  234
                 \
                  5

First of all we need to find out how much space to allocate for our array. This is simply $2^h - 1$ Where h is the tree height or number of levels. In your case it is $2^5-1 = 31$ .

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int array[32]
int array[32]

Now we initialise all those to -1. Remember we have defined -1 to be null.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
for (int i=0; i <32; i++)
{
   array[i] = -1;
}
for (int i=0; i <32; i++)
{
   array[i] = -1;
}

Now we use 23 1 45 2 31 52 3 234 5 and start of from left to right inserting each number into our array.

For example 23 is the root so say array[0]=23

Now we move on to 1. From our tree 1 is to the left of 23. So 2i+1 = 2*0+1 = 1

Therefore array[1]=1

Now we move onto 45. From our tree 45 is on the right of 23. So 2i+2 = 2* 0+2 = 2
Therefore array[2] =45

Now move onto 2. From our tree 2 is on the right of 1. So 2i+2 = 2*1+2 =4

Therefore array[4]=2

Now move onto 31. From our tree 31 is to the left of 45. So 2i+1=2*2+1=5

Therefore array[5]=31.

And so on.

Once you have finished filling the entire array. Print it out using my code I have provided before.

Last edited by iamthwee; Jan 7th, 2007 at 12:12 pm.

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 49

Reputation: sivaslieko++ is an unknown quantity at this point

Solved Threads: 0

sivaslieko++ sivaslieko++ is offline

Offline

Light Poster

Re: how to print null subtree of a null subtree?

#26

Jan 7th, 2007

hi iamthwee at this point I could not achieve tree traversal I think there is something necessary related with recursion. How did you travers the tree? Could you please explain?

My code is below:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
void BST::BreadthFirstTraversal(){
 
 BSTNode *p=root;
 int myArray[32];
 
 for(int i = 0; i<32;i++){
  myArray[i]=-1;
 }
 
 int m;
 
 if(root!=NULL){
 
  myArray[0] = root->item;
 
  while(m<sizeof(myArray)){   
 
   if(p->left!=NULL){
    myArray[2*m+1] = p->left->item;     
   }   
 
   if(p->right!=NULL){
    myArray[2*m+2] = p->right->item;
   }  
 
  }
 }
 
 for(int t = 0; t<32;t++){
  cout<<myArray[t];
 }
}
void BST::BreadthFirstTraversal(){
 
 BSTNode *p=root;
 int myArray[32];

 for(int i = 0; i<32;i++){
  myArray[i]=-1;
 }

 int m;
 
 if(root!=NULL){
  
  myArray[0] = root->item;
 
  while(m<sizeof(myArray)){   

   if(p->left!=NULL){
    myArray[2*m+1] = p->left->item;     
   }   

   if(p->right!=NULL){
    myArray[2*m+2] = p->right->item;
   }  

  }
 }
 
 for(int t = 0; t<32;t++){
  cout<<myArray[t];
 }
}