Binary Tree

 A tree is a hierarchical data structure: an element of a tree is located below some elements and above some other elements.

Here is an example of a tree holding letters: 

      tree
      ----
       j    <-- root
     /   \
    f      k  
  /   \      \
 a     h      z    <-- leaves

Tree Vocabulary

Uses

file system
-----------
     /    <-- root
  /     \
...    home
      /    \
   ugrad    course
    /      /   |   \
  ...  cs101 cs112 cs113

Recursive Data Structure

For example, let's look at our tree of letters and examine the part starting at f and everything under it... 

      tree
      ----
       j
     /   \
    f      k  
  /   \      \
 a     h      z

Binary Trees

A tree whose elements have at most 2 children is called a binary tree.

Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

 Since we want to be able to represent a tree in C++, how are we going to store this hierarchical structure?

Similarly to a linked list, we can have a node that contains data and two pointers: to the left child and to the right child. If a node does not have a right or a left child, the respective pointer is NULL.

So, our first example tree of letters would look something like:

           |
           v
         -----
         | j |
         |---|
         | | |
         /---\
        v     v
    -----     -----
    | f |     | k |
    |---|     |---|
    | | |     |0| |
    /---\     ----\
   v     v         v
-----   -----      -----
| a |   | h |      | z |
|---|   |---|      |---|
|0|0|   |0|0|      |0|0|
-----   -----      -----

Special case: Empty Tree

 Implementing a tree in C++ is a tricky design problem: it is hard (if at all possible) to come up with a structure that's simple and convenient at the same time.

The model that we consider here is fairly straightforward. However, as we will see, it does not quite satisfy the recursive property that we have stated above: "a subtree of a tree is itself a tree". This causes some problems in writing recursive functions for this model.

Our approach is to have two separate classes:

• a class BTNode for a node of a tree (files btnode.h and btnode.cpp)
• a class BTree for a tree itself (files btree.h and btree.cpp)

class BTNode {
public:
  ...

private:
  ItemType data;
  BTNode *lChild;
  BTNode *rChild;
};

class BTree {
public:
  ...

private:
  BTNode* rootPtr;
};

 Class BTNode has the following methods:

class BTNode {
public:
  // Constructors.
  BTNode();
  BTNode(ItemType);

  // Destructor
  ~BTNode();

  // Get fields of node.
  ItemType getData() const;
  BTNode *getLeftChild() const;
  BTNode *getRightChild() const;

  // Set fields of node.
  void setData(ItemType);
  void setLeftChild(BTNode *);
  void setRightChild(BTNode *);

private:
  ItemType data;
  BTNode *lChild;
  BTNode *rChild;
};

The methods for the class BTree are as follows:

class BTree{
public:
        // tree destructor
        ~BTree();
        
        // check if the tree is empty
        bool isEmpty();

        // set the value of the root
        void setRoot(BTNode *);

        // get the value of the root
        BTNode *getRoot();

private:
        BTNode *rootPtr;
};

Lab assignment

      tree
      ----
       j   
     /   \
    f      k  
  /   \      \
 a     h      z

[j[f[a[][]][h[][]]][k[][z[][]]]]

Exercise  In the file treetest.cpp write and test the functions described below. Write these functions one-by-one, compile and test your program before starting the other one.

Note that each tree function has an auxiliary function for nodes that performs a recursive call. Important: Make sure that all the functions that use trees as arguments are call-by-reference. If a tree is passed by value, it gets out of scope, and its destructor is called.

1. A function that computes the height of a tree.
2. A function that computes number of nodes of a tree
3. A function that takes two trees by reference and changes the second one to be the mirror image of the first one, i.e. all right children of the first tree become left children of the scond tree, and vice versa.