*** IN JAVA ***

Exercise 2a (Trees)

EXERCISE a): Given the below tree structure, identify the following:

Root of the tree

Leaf nodes

Siblings of node 54

Ancestor nodes of node containing 67

Descendants of node 17

Height of the tree

Level of node 72

a) Trees

In Computer Science, a Tree is an abstract data type representing a hierarchical structure. This is a more constrained version of another structure called a graph. A graph is a collection of nodes (usually called vertices) and a collection of links (usually called edges) between them. A tree structure is a type of graph where the any two vertices are connected by exactly one path (sequences of edges). In a Tree ADT, if a nodestudent submitted image, transcription available belowis pointing to nodestudent submitted image, transcription available below,student submitted image, transcription available belowis called the parent ofstudent submitted image, transcription available below, andstudent submitted image, transcription available belowis called the child ofstudent submitted image, transcription available below. Nodes that share parents are called siblings. There exists one special node, called the root, which is the node without parents. The nodes that do not have any children are called leaf nodes. Note that trees cannot have cycles (no "back edges") and they cannot have nodes that point to other nodes which are in a different part of the tree (no "cross edges")[1]. Due to this property, we can associate with each node a level value. The root is defined to be at level zero. Its children are at level 1. In general, the children of nodes at level L are defined to be at level L+1. A sequence of edges in a tree is called a path, with the number of edges in that sequence called the path length. A node is the ancestor of another node if it is above it on the path from the root. Nodes that can be reached by following a path from a particular node are the descendants of that node. Note that the path length of a path from the root to a particular node is the same as the level value of that node. The height of a tree is the length of the longest path from the root to a leaf. A tree can be visualized through a tree diagram. An example is shown below.

student submitted image, transcription available below

[1] These are not formal definitions, but they should provide you with the idea.