We started by writing a portion of the lab program together
in zoom class.

The program name is...
/2020/d/btree.cpp

Look in chapter-20 of our Gaddis textbook for help.

Functions we wrote together...
   1. Node structure
   2. BST class
   3. constructor and overloaded constructor
   4. destructor
   5. insert function
   6. display graphical tree

Binary tree functions still needed...

1. Search the tree for a data value
   Return the address of a found node, null if not found.



do this for Friday 4/24

2. A function to remove a node based on its data value.
   Use the Gaddis textbook for this.
   Chapter-20

Just write this function like the book does. Good enough.



3. Show tree traversal orders (non-graphical)
   Show pre-order  VLR
   Show in-order   LVR
   Show post-order LRV
   You should write a function for each of these.

4. A function to remove all nodes. (clear the tree)
   This is not a destructor, but similar to the destructor we wrote together.

5. Destructor to cleanup the tree when out of scope.


6. Functions that count and return...
      a. how many nodes in the tree.
      b. how many levels in the tree.
      c. the number of leaf-nodes in the tree.
      d. the number of nodes with exactly one child node.
(see below for tips on how to write these)


Below is a main function to start testing with.
Add your own tests for the functions you add.


int main()
{
    BST b;
    cout << "inserting values into b...\n";
    b.insert(5);
    b.insert(2);
    b.insert(8);
    b.insert(9);
    b.insert(3);
    b.insert(6);
    b.insert(1);
    b.display();
    cout << endl;
    cout << "n leaves: " << b.nleaves();
    cout << endl;
    //
    b.removeAllNodes();
    //
    cout << "test of n-nodes with one child...\n";
    int arr1[] = {9,8,7,3,2,1,10,11,12,13,4,5,6};
    for (int i=0; i<(int)(sizeof(arr1)/sizeof(int)); i++)
        b.insert(arr1[i]);
    b.display();
    cout << endl;
    cout << "n leaves: " << b.nleaves() << endl;
    cout << "n nodes with 1-child: " << b.nOneChild() << endl;
    cout << endl;
    return 0;
}



You may also create a menu like this...

Lab-13 binary search tree

Menu options
1. Clear the binary tree
2. Insert a value
3. Insert several (n) random values
4. Display tree (graphical)
5. Delete a value
6. Show all traversals
7. Show statistical counts
8. Other things
9. End program

Enter your choice:

Functions that count and return a number...

a. how many nodes in the tree.

The number of nodes in any BST sub-tree is
   1
   plus the number of nodes in the root's left sub-tree
   plus the number of nodes in the root's right sub-tree

   Use resursion.
   It is very simple.


b. how many levels in the tree.

The number of levels in any BST sub-tree is

   1
   plus the greater of
      the number of levels in the root's left sub-tree
      the number of levels in the root's right sub-tree

   Please use the max function in <cmath>


c. the number of leaf-nodes in the tree.

   The number of nodes with no children.


d. the number of nodes with exactly one child node.

   The number of nodes with 1 child.



All the solutions above assume that the root node is not null.
If root node null, all above have a count of zero.