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 80 81 82 83 84 85 86 87 88
|
#include <queue>
#include <iostream>
class Binary_Tree
{
private:
struct node
{
int data;
node* leftChild = nullptr ;
node* rightChild = nullptr ;
};
node* root = nullptr ;
static void recursive_delete( node* n )
{
if( n != nullptr )
{
recursive_delete( n->leftChild ) ;
recursive_delete( n->rightChild ) ;
delete(n) ;
}
}
static void insert( node* tree, int value ) // invariant: pointer is not null
{
// get a reference to the appropriate child substree
// note: a reference is required because it should be modified if it is null
node*& where = value < tree->data ? tree->leftChild : tree->rightChild ;
if( where == nullptr ) where = new node { value } ;
else insert( where, value ) ;
}
static void push_children( std::queue< const node* >& q, const node* n )
{
// our breadth first is from left to right; so push the left child first
if( n->leftChild ) q.push( n->leftChild ) ;
if( n->rightChild ) q.push( n->rightChild ) ;
}
// non-copyable, non-moveable (move elided for brevity)
Binary_Tree( const Binary_Tree& ) = delete ;
void operator= ( const Binary_Tree& ) = delete ;
public:
Binary_Tree() = default ;
~Binary_Tree() { recursive_delete(root) ; }
bool is_empty() const { return root == nullptr; }
void insert( int value )
{
if( is_empty() ) root = new node { value } ;
else insert( root, value ) ;
}
std::ostream& print_breadth_first( std::ostream& stm = std::cout ) const
{
if( is_empty() ) return stm ;
// we need to print the items level by level, top to bottom
// so use a queue to hold the items at the next lower level (they go to the back of the queue)
// these would be printed only after we are done printing the current level
std::queue< const node* > queue ;
queue.push(root) ; // start with the root
while( !queue.empty() ) // as long as there are no more items to be printed
{
stm << queue.front()->data << ' ' ; // print the item at the current level
push_children( queue, queue.front() ) ; // hold the children for later processing
queue.pop() ; // and remove the item that was printed
}
return stm << '\n' ;
}
};
int main()
{
Binary_Tree my_tree ;
for( int value : { 12, 78, 23, 32, 44, 11, 92, 64, 81, 10, 19, 17 } )
{
my_tree.insert(value) ;
my_tree.print_breadth_first() ;
}
}
| |