Tree Flashcards
What is a tree
an abstract data type that stores elements hierarchically, not linearly
what is the root element?
an element without a parent
what are the associations of non-root elements
one parent and zero or more children elements
Formal definition of tree
Define tree T as a set of nodes
1) If T is nonempty, it has a special node, called the root of T , that has no parent.
2) Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.
What is a sibling node in a tree
two nodes with the same parent
What is a leaf node
a node with no children
what is another name for a leaf node
external node
What is an edge in a tree
An edge of tree T is a pair of nodes (u,v) such that u is the parent of v
What is a path in a tree
A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge.
What is the depth of a position of a tree?
The number of ancestors of the position, excluding the position itself
What is the depth of the root a of tree?
Zero
Recursive algorithm to find the depth of a tree
If root return 0 otherwise return depth of parent + 1
What is the height of a position of a tree?
The maximum of the depths of its leaf positions
What is a recursive algorithm to get the depth of the position of a tree?
If leaf return 0, otherwise return max of height of children + 1
