Binary Tree - Definitions For Rooted Trees

Definitions For Rooted Trees

  • A directed edge refers to the link from the parent to the child (the arrows in the picture of the tree).
  • The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.
  • A leaf node has no children.
  • The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
  • The depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero.
  • Siblings are nodes that share the same parent node.
  • A node p is an ancestor of a node q if it exists on the path from the root to node q. The node q is then termed as a descendant of p.
  • The size of a node is the number of descendants it has including itself.
  • In-degree of a node is the number of edges arriving at that node.
  • Out-degree of a node is the number of edges leaving that node.
  • The root is the only node in the tree with In-degree = 0.
  • All the leaf nodes have Out-degree = 0.

Read more about this topic:  Binary Tree

Famous quotes containing the words definitions, rooted and/or trees:

    Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
    There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.
    Edmond De Goncourt (1822–1896)

    However global I strove to become in my thinking over the past twenty years, my sons kept me rooted to an utterly pedestrian view, intimately involved with the most inspiring and fractious passages in human development. However unconsciously by now, motherhood informs every thought I have, influencing everything I do. More than any other part of my life, being a mother taught me what it means to be human.
    Mary Kay Blakely (20th century)

    The sugar maple is remarkable for its clean ankle. The groves of these trees looked like vast forest sheds, their branches stopping short at a uniform height, four or five feet from the ground, like eaves, as if they had been trimmed by art, so that you could look under and through the whole grove with its leafy canopy, as under a tent whose curtain is raised.
    Henry David Thoreau (1817–1862)