Topics: Data Structure
A tree is a non-linear and dynamic data structure. It’s dynamic since its structure can change during the execution of a program, and it’s non-linear since each of its elements can be followed by more than one element.
A tree can also be called a hierarchical data structure that contains a collection of elements called nodes, one of them known as root. Between all of these elements, parent-child relations are established.
At the same time, trees are homogeneous structures defined by the concatenation of one node element along with a finite number of disjoint trees called sub-trees.
A binary tree is a special type of tree that is used to save up memory and space, since trees that contain nodes each with a different number of offspring can waste a lot of memory and space.
Graphically, trees can be seen as a graph with the following features:
- Every non-empty tree has one and only one root node
- Loops can’t exist
- The number if lines is always , where is the number of elements in the tree
- A node is a direct child of a node if is being pointed to by
- A node is a direct parent of a node if points to
- Every node that has no children is called a terminal or leaf
- Every node that isn’t the root node nor a terminal node is known as an interior node
- The degree of a node is the number of direct offspring of a node. The degree of the tree is the maximum degree among all the node degrees
- The level is the amount of links that have to be traversed to reach a certain node plus one. By definition, the root node has a level of 1
- The height of a tree is the maximum number of levels among all the levels within the tree