Preliminaries

Cards (13)

  • A tree can be defined in several ways. One natural way to define a tree is recursively. A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a distinguished node r, called the root, and zero or more nonempty (sub)trees T1, T2, …, Tk, each of whose roots are connected by a directed edge from r.
    The root of each subtree is said to be a child of r, and r is the parent of each subtree root.
  • Each node may have an arbitrary number of children, possibly zero. Nodes with no children are known as leaves.
  • Nodes with the same parent are siblings
  • A path from node n1 to nk is defined as a sequence of nodes n1, n2, …, nk such that ni is the parent of ni+1 for 1 ≤ i < k.
  • The length of this path is the number of edges on the path, namely k − 1.
  • There is a path of length zero from every node to itself.
  • Notice that in a tree there is exactly one path from the root to each node.
  • For any node ni, the depth of ni is the length of the unique path from the root to ni.
  • The root is at depth 0.
  • The height of ni is the length of the longest path from ni to a leaf.
  • All leaves are at height 0.
  • The height of a tree is equal to the height of the root.
  • In each node, we have the data, a link to the first child and a link to the next sibling