In this module we have introduce vocabulary related to trees and what makes a tree a tree. To recap, we have introduced the following:

  • Child - a node with an edge that connects to another node closer to the root.
  • Degree
    • Degree of a node - the number of children a node has. The degree of a leaf is zero.
    • Degree of a tree - the number of children the root of the tree has.
  • Edge - connection between two nodes. In a tree, the edge will be pointing in a downward direction.
  • Leaf - a node with no children.
  • Node - the general term for a structure which contains an item, such as a character or even another data structure.
  • Parent - a node with an edge that connects to another node further from the root. We can also define the root of a tree with respect to this definition;
  • Root - the topmost node of the tree; a node with no parent.

Now we will work on creating our own implementation of a tree. These definitions will serve as a resource to us when we need refreshing on meanings; feel free to refer back to them as needed.