Binary Trees in C++: Part 1

			
						       10
						     /    \
						    6      14
						   / \    /  \
						  5   8  11  18

struct node
{
  int key_value;
  node *left;
  node *right;
};

	
class btree
{
    public:
        btree();
        ~btree();

        void insert(int key);
        node *search(int key);
        void destroy_tree();

    private:
        void destroy_tree(node *leaf);
        void insert(int key, node *leaf);
        node *search(int key, node *leaf);
        
        node *root;
};

btree::btree()
{
  root=NULL;
}

btree::~btree()
{
  destroy_tree();
}

void btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
  }
}

void btree::insert(int key, node *leaf)
{
  if(key< leaf->key_value)
  {
    if(leaf->left!=NULL)
     insert(key, leaf->left);
    else
    {
      leaf->left=new node;
      leaf->left->key_value=key;
      leaf->left->left=NULL;    //Sets the left child of the child node to null
      leaf->left->right=NULL;   //Sets the right child of the child node to null
    }  
  }
  else if(key>=leaf->key_value)
  {
    if(leaf->right!=NULL)
      insert(key, leaf->right);
    else
    {
      leaf->right=new node;
      leaf->right->key_value=key;
      leaf->right->left=NULL;  //Sets the left child of the child node to null
      leaf->right->right=NULL; //Sets the right child of the child node to null
    }
  }
}

node *btree::search(int key, node *leaf)
{
  if(leaf!=NULL)
  {
    if(key==leaf->key_value)
      return leaf;
    if(key<leaf->key_value)
      return search(key, leaf->left);
    else
      return search(key, leaf->right);
  }
  else return NULL;
}

void btree::insert(int key)
{
  if(root!=NULL)
    insert(key, root);
  else
  {
    root=new node;
    root->key_value=key;
    root->left=NULL;
    root->right=NULL;
  }
}

node *btree::search(int key)
{
  return search(key, root);
}

void btree::destroy_tree()
{
  destroy_tree(root);
}

 
va_list a_list; 

 
#include <cstdarg>
#include <iostream>

using namespace std;

double average ( int num, ... )
{
  va_list arguments;                     // A place to store the list of arguments
  double sum = 0;

  va_start ( arguments, num );           // Initializing arguments to store all values after num
  for ( int x = 0; x < num; x++ )        // Loop until all numbers are added
    sum += va_arg ( arguments, double ); // Adds the next value in argument list to sum.
  va_end ( arguments );                  // Cleans up the list

  return sum / num;                      // Returns some number (typecast prevents truncation)
}
int main()
{
  cout<< average ( 3, 12.2, 22.3, 4.5 ) <<endl;
  cout<< average ( 5, 3.3, 2.2, 1.1, 5.5, 3.3 ) <<endl;
}

 
void recurse()
{
  recurse(); //Function calls itself
}

int main()
{
  recurse(); //Sets off the recursion
}

 
#include <iostream>

using namespace std;

void recurse ( int count ) // Each call gets its own count
{
  cout<< count <<"\n";
  // It is not necessary to increment count since each function's
  //  variables are separate (so each count will be initialized one greater)
  recurse ( count + 1 );
}

int main()
{
  recurse ( 1 ); //First function call, so it starts at one        
}

 
void doll ( int size )
{
  if ( size == 0 )   // No doll can be smaller than 1 atom (10^0==1) so doesn't call itself
    return;          // Return does not have to return something, it can be used
                     //  to exit a function
  doll ( size - 1 ); // Decrements the size variable so the next doll will be smaller.
}
int main()
{
  doll ( 10 ); //Starts off with a large doll (it's a logarithmic scale)
}

 
void printnum ( int begin )
{
  cout<< begin;
  if ( begin < 9 )         // The base case is when begin is greater than 9
  {                           //  for it will not recurse after the if-statement
      printnum ( begin + 1 ); 
  }
  cout<< begin;         // Outputs the second begin, after the program has
                              //  gone through and output
}

 
----------        ----------
- Data   -        - Data   -    
----------        ----------   
- Pointer- - - -> - Pointer-  
----------        ----------

 
struct node {
  int x;
  node *next;
};

int main()
{
  node *root;      // This will be the unchanging first node

  root = new node; // Now root points to a node struct
  root->next = 0;  // The node root points to has its next pointer
                   //  set equal to a null pointer
  root->x = 5;     // By using the -> operator, you can modify the node
                   //  a pointer (root in this case) points to.
}

 
struct node {
  int x;
  node *next;
};

int main()
{
  node *root;       // This won't change, or we would lose the list in memory
  node *conductor;  // This will point to each node as it traverses the list

  root = new node;  // Sets it to actually point to something
  root->next = 0;   //  Otherwise it would not work well
  root->x = 12;
  conductor = root; // The conductor points to the first node
  if ( conductor != 0 ) {
    while ( conductor->next != 0)
      conductor = conductor->next;
  }
  conductor->next = new node;  // Creates a node at the end of the list
  conductor = conductor->next; // Points to that node
  conductor->next = 0;         // Prevents it from going any further
  conductor->x = 42;
}

 
conductor = root;
if ( conductor != 0 ) { //Makes sure there is a place to start
  while ( conductor->next != 0 ) {
    cout<< conductor->x;
    conductor = conductor->next;
  }
  cout<< conductor->x;
}

 
conductor = root;
while ( conductor != NULL ) {
  cout<< conductor->x;
  conductor = conductor->next;
}

Lesson 14: Accepting command line arguments

In C++ it is possible to accept command line arguments. Command-line arguments are given after the name of a program in command-line operating systems like DOS or Linux, and are passed in to the program from the operating system. To use command line arguments in your program, you must first understand the full declaration of the main function, which previously has accepted no arguments. In fact, main can actually accept two arguments: one argument is number of command line arguments, and the other argument is a full list of all of the command line arguments. 

 int main ( int argc, char *argv[] )

 #include <fstream>#include <iostream>using namespace std;int main ( int argc, char *argv[] ){  if ( argc != 2 ) // argc should be 2 for correct execution    // We print argv[0] assuming it is the program name    cout<<"usage: "<< argv[0] <<" <filename>\n";  else {    // We assume argv[1] is a filename to open    ifstream the_file ( argv[1] );    // Always check to see if file opening succeeded    if ( !the_file.is_open() )      cout<<"Could not open file\n";    else {      char x;      // the_file.get ( x ) returns false if the end of the file      //  is reached or an error occurs      while ( the_file.get ( x ) )        cout<< x;    }    // the_file is closed implicitly here  }}

Lesson 13: More on Functions

In lesson 4 you were given the basic information on functions. However, I left out one item of interest. That item is the inline function. Inline functions are not very important, but it is good to understand them. The basic idea is to save time at a cost in space. Inline functions are a lot like a placeholder. Once you define an inline function, using the 'inline' keyword, whenever you call that function the compiler will replace the function call with the actual code from the function. 

 
#include <iostream>

using namespace std;

inline void hello()
{ 
  cout<<"hello";
}
int main()
{
  hello(); //Call it like a normal function...
  cin.get();
}

Lesson 12: Introduction to Classes 

C++ is a bunch of small additions to C, with a few major additions. One major addition is the object-oriented approach (the other addition is support for *Generic programming, which we'll cover later). As the name object-oriented programming suggests, this approach deals with objects. Of course, these are not real-life objects themselves. Instead, these objects are the essential definitions of real world objects. Classes are collections of data related to a single object type. Classes not only include information regarding the real world object, but also functions to access the data, and classes possess the ability to inherit from other classes. (Inheritance is covered in a later lesson.) 

If a class is a house, then the functions will be the doors and the variables will be the items inside the house. The functions usually will be the only way to modify the variables in this structure, and they are usually the only way even to access the variables in this structure. This might seem silly at first, but the idea to make programs more modular - the principle itself is called "encapsulation". The key idea is that the outside world doesn't need to know exactly what data is stored inside the class--it just needs to know which functions it can use to access that data. This allows the implementation to change more easily because nobody should have to rely on it except the class itself. 

 
#include <iostream>

using namespace std;

class Computer // Standard way of defining the class
{
public:
  // This means that all of the functions below this(and any variables)
  //  are accessible to the rest of the program.
  //  NOTE: That is a colon, NOT a semicolon...
  Computer();
  // Constructor
  ~Computer();
  // Destructor
  void setspeed ( int p );
  int readspeed();
protected:
  // This means that all the variables under this, until a new type of
  //  restriction is placed, will only be accessible to other functions in the
  //  class.  NOTE: That is a colon, NOT a semicolon...
  int processorspeed;
};
// Do Not forget the trailing semi-colon

Computer::Computer()
{
  //Constructors can accept arguments, but this one does not
  processorspeed = 0;
}

Computer::~Computer()
{
  //Destructors do not accept arguments
}

void Computer::setspeed ( int p )
{
  // To define a function outside put the name of the class
  //  after the return type and then two colons, and then the name
  //  of the function.
  processorspeed = p;
}
int Computer::readspeed()  
{
  // The two colons simply tell the compiler that the function is part
  //  of the class
  return processorspeed;
}

int main()
{
  Computer compute;  
  // To create an 'instance' of the class, simply treat it like you would
  //  a structure.  (An instance is simply when you create an actual object
  //  from the class, as opposed to having the definition of the class)
  compute.setspeed ( 100 ); 
  // To call functions in the class, you put the name of the instance,
  //  a period, and then the function name.
  cout<< compute.readspeed();
  // See above note.
}