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 for, definitions, rooted and/or trees:
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)
“Only the family, society’s smallest unit, can change and yet maintain enough continuity to rear children who will not be “strangers in a strange land,” who will be rooted firmly enough to grow and adapt.”
—Salvador Minuchin (20th century)
“But we still remember ... above all, the cool, free aspect of the wild apple trees, generously proffering their fruit to us, though still green and crude,—the hard, round, glossy fruit, which, if not ripe, still was not poison, but New English too, brought hither, its ancestors, by ours once. These gentler trees imparted a half-civilized and twilight aspect to the otherwise barbarian land.”
—Henry David Thoreau (1817–1862)