General definition#

Trees have nodes that hold the data and edges which connect the nodes. An empty tree obviously has no nodes and therefore no data.

Characteristics#

A Tree like in our real world has a root. The root is the highest node in the tree. Each node is also a root of its own subtree. A child node is a node that is connected to a node above it, the so called parent. A Sibling is a node that shares the same parent. A leaf node has no children as it is hanging alone at the bottom of a subtree. An inner node however has at least 1 child.

Order#

The Order of a tree is the max amount of children a tree is aloud to have. In the above picture we don't know the order of the tree but we can say that it is \(\geq 3\).

Degree#

The degree of a node is the amount of children a specific node has. Often this is denoted as deg(v)=Number of children of node. So in the above tree deg(Q)=2.

Path#

A path is a combination of edges between 2 Nodes. The length of the path is the amount of nodes visited whilst traversing from the start node to the end node. The amount includes the start and the end node. So in the above tree the length of the path from R to H is 4.

Height#

The height of a tree is the length of the longest path from the root to a leaf. In the above tree the height is 5.

Depth#

The depth of a node is the amount of nodes on the path to the root. Often this is denoted as depth(v)=Number of nodes on path to root. So in the above tree depth(L)=4.

Level#

A Level is a grouping of all nodes with the same depth.

Properties#

A Full tree is a tree where all inner nodes have the maximum amount of Nodes according to the order. In the image below both trees are full with an order of 2.

A Complete tree is a tree where each level has the maximum amount of nodes according to the order. In the image below only the left tree is complete with an order of 2.