C++

Forum

 
Binary Tree : leaves and post order

d1g1talarts (55)
I am having trouble getting my # of leaves method working, with leaves being defined as a node whose left and right subtrees are empty trees. The class has three public vars, left_, right_ , and entry_

my code for this looks like 

1
2
3
4
5
6
7
8
9
10
11
 
long
   BinaryTree:: leaves( const BinaryNode * subtree )
{
	if (subtree == NULL)
		return 0;
	if (subtree->left_ == NULL && subtree->right_ == NULL)
		return 1;
	else
		return leaves(subtree->left_) +
		leaves(subtree->right_);
}


Then there is my pre order and post order , pre order is working and post order is not. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
 void
   BinaryTree:: preorder( std::vector< short > & traversal,
      const BinaryNode * subtree )
{
   if( subtree != NULL )
   {
      traversal.push_back( subtree->entry_ );
      preorder( traversal, subtree->left_ );
      preorder( traversal, subtree->right_ );
   }
}
void BinaryTree::postorder(std::vector< short > & traversal,
	const BinaryNode * subtree)
{
	/*if (subtree != NULL)
	{
		traversal.push_back(subtree->entry_);
		preorder(traversal, subtree->right_);
		preorder(traversal, subtree->left_);
	}
}*/
	if (subtree == NULL) return;
	
	postorder(traversal,subtree->left_);
	postorder(traversal,subtree->right_);
	traversal.push_back(subtree->entry_);
	//std::cout << subtree->entry_ << " ";
}


and the main im running with 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
#include <iostream>
#include <string>
#include <vector>

using namespace std;


void 
   getRequest( string & request )
{
   cout << "Enter request: ";
   cin >> request;
}


int
   main()
{
   randomizeSeed();

   BinaryTree theTree;

   string request;
   getRequest( request );

   while( request != "quit" )
   {
      if( request == "build" )
      {
         long treeSize;
         cin >> treeSize;
         theTree.build( treeSize );
      }

      else if( request == "display" )
      {
         theTree.display( cout );
      }

     

      else if( request == "leaves" )
      {
         cout << "leaves is " << theTree.leaves() << endl;
      }

     

      else if( request == "preorder" )
      {
         vector< short > traversal = theTree.preorder();
         cout << "preorder is ";
         for( unsigned long i=0; i<traversal.size(); ++i )
         {
            cout << traversal.at(i) << "  ";
         }
         cout << endl;
      }
	  else if (request == "postorder") {
		  vector< short > traversal = theTree.postorder();
		  cout << "postorder is ";
		  for (unsigned long i = 0; i<traversal.size(); ++i)
		  {
			  cout << traversal.at(i) << "  ";
		  }
		  cout << endl;
	  }
      else
      {
         cout << "Known requests: build <size>, display, size, " 
            << "height, leaves," << endl;
         cout << "                leftmost, preorder, quit" << endl;
      }

      getRequest( request );
   }

   return 0;
}
Last edited on
dhayden (5795)
BinaryTree::leaves() looks okay to me. If it isn't generating the expected results then I'd suspect the build() method. Can you post the complete code?
d1g1talarts (55)
the problem shouldn't be in the build it was a provided piece of the project. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 // Build a randomly shaped tree of size nodes.
void
   BinaryTree:: build( long size )
{
   destroy( tree_ );
   buildRandom( size, tree_ );
}

void
   BinaryTree:: buildRandom( long size, BinaryNode * & subtree )
{
   if( size == 0 )
   {
      subtree = NULL;
   }
   else
   {
      subtree = new BinaryNode( btEntry_ );
      btEntry_++;
      long leftSize = randInt( 0, size );
      buildRandom( leftSize, subtree->left_ );
      long rightSize = size - 1 - leftSize;
      buildRandom( rightSize, subtree->right_ );
   }
}
d1g1talarts (55)
ok... idk why but, leaves is working. Any opinions on postorder?
dhayden (5795)
postorder looks fine to me too.

Please post the full source so we can compile the program and run it. It's nearly impossible to debug a program that you can't run.
doug4 (1535)
When you say post order is not working, what do you mean? What incorrect behavior are you seeing?
Topic archived. No new replies allowed.