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
|
#include <iostream>
#include <initializer_list>
struct tree // note: may not be balanced (ergo, not a binary search tree).
{
tree() = default ;
tree( std::initializer_list<int> il ) { for( int key : il ) add_leaf(key) ; }
// copy constructor etc. (rule of five)
void add_leaf( int key )
{
if( root == nullptr ) root = new node{key} ;
else add_leaf( key, root ) ;
}
void print_in_order() const
{
std::cout << "[ " ;
print_in_order(root) ;
std::cout << "]\n" ;
}
private:
struct node
{
int key ;
node* left = nullptr ;
node* right = nullptr ;
};
node* root = nullptr ;
void add_leaf( int key, node* p )
{
node*& where = key < p->key ? p->left : p->right ; // note: reference
if( where == nullptr ) where = new node{key} ;
else add_leaf( key, where ) ;
}
void print_in_order( const node* p ) const
{
if( p != nullptr )
{
print_in_order( p->left ) ;
std::cout << p->key << ' ' ;
print_in_order( p->right ) ;
}
}
};
int main()
{
tree t { 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80 };
t.print_in_order() ;
for( int v : { 59, 19, 79, 99, 49, 29 } ) t.add_leaf(v) ;
t.print_in_order() ;
}
|