CMPT 225 Lab 4: General Tree Implementation

In this lab we will familiarize ourselves with the tree general structure and one implementation of it. The general tree structure is used in assignment 3 as well.

Introduction

We can express a hierarchy using a general tree structure. For example the cities in the world are in different countries or sometimes even different states/provinces within countries. Let's say a kid's knowledge of the world is given in the following graph:

The root of this tree keeps the data "World" and it has five children each containing one of the following countries: Canada, France, Japan, Nigeria, and USA. Now, Let's assume one can insert an edge into the graph from a parent to a child using the command insert. If the parent is '-', it means that node is the root of the tree. Then the following commands will build the graph for us:

insert - World
insert World Canada
insert World France
insert World Japan
insert World Nigeria
insert World USA
insert Canada BC
insert Canada Ontario
insert USA Oregon
insert USA NY
insert BC Vancouver
insert BC Burnaby
insert Oregon Portland
insert NY NYC
insert Japan Tokyo
insert France Paris

There are also other functionalities associated with a tree. One can check if a tree is empty, get its size and its root's height, traverse it in preorder or postorder manner, or remove a node from it. In this file you can find the definition of a generic tree where some of these functionalities are implemented (for example insertion, isEmpty, and preorder traversal are taken care of). Your job in this lab is to :

1. Familiarize yourself with the implemented functions
2. Implement the size function (30%)
   You can implement size recursively as the size of the sub-graph rooted at a node is one plus sume of the sizes of sub-graphs rooted at its children.
3. Implement the postorderPrint (20%)
   This is very similar to the preorderPrint. Only in post order traversal, we traverse the subtrees rooted at the children recursively and then we print the data of the node.
4. Implement the remove function (50%)
   There could be many definitions for the remove function differing in what to do with the children of the node that is being removed. Here, we decide to move the children of the deleted node to its parent. For example if BC is removed from the tree drawn above, Vancouver and Burnaby will become children of Canada (and siblings of Ontario).
   Here are some steps that one should take to successfully remove a node from the tree:
   • refuse to remove the node if it is the root and it has children (already taken care of for you)
   • remove this (the pointer to this object) from the children_ of the parent (note that children_ is a vector of pointers). Again, this is already taken care of for you.
   • set the parent_ of all children to the parent_ of this node.
   • add each child c to the children_ of the parent and remove c from children_ of this node.
   • delete this

The signatures of the functions you should implement are already in gTree.h. All you need to do is to fill in the body of them.
To test your implementation you can use this file . It takes a commands.txt file as usual and executes the right functions based on the given commands. If the commands.txt contains the following:

insert - World
insert World Canada
insert World France
insert World Japan
insert World Nigeria
insert World USA
insert Canada BC
insert Canada Ontario
insert USA Oregon
insert USA NY
insert BC Vancouver
insert BC Burnaby
insert Oregon Portland
insert NY NYC
insert Japan Tokyo
insert France Paris
preorderPrint
postorderPrint
getSize
remove BC
preorderPrint
postorderPrint
getSize

compiling and running main will give the following results:

g++ -o main.o main.cpp 
./main.o commands.txt 
preorder:
World Canada BC Vancouver Burnaby Ontario France Paris Japan Tokyo Nigeria USA Oregon Portland NY NYC
postorder:
Vancouver Burnaby BC Ontario Canada Paris France Tokyo Japan Nigeria Portland Oregon NYC NY USA World
16
preorder:
World Canada Ontario Burnaby Vancouver France Paris Japan Tokyo Nigeria USA Oregon Portland NY NYC
postorder:
Ontario Burnaby Vancouver Canada Paris France Tokyo Japan Nigeria Portland Oregon NYC NY USA World
15

What to submit?

1. Completed gTree.h file

Where to submit?

In CourSys under CMPT 225 Lab4 activity.