Tree ADTs
From
(Created page with 'A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the '''root''' together with any number of successors which are also trees ...') |
(→Paths) |
||
| Line 1: | Line 1: | ||
A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the '''root''' together with any number of successors which are also trees ('''subtrees''' in this case), which are disjoint from each other and from the root. The roots of the subtrees are called '''children''' of the root, and there is an '''edge''' from each node to its children, and a node is said to be the '''parent''' of its children. A node that has at least one child is called an '''internal node''', and a node that has no children is called a '''leaf node'''. | A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the '''root''' together with any number of successors which are also trees ('''subtrees''' in this case), which are disjoint from each other and from the root. The roots of the subtrees are called '''children''' of the root, and there is an '''edge''' from each node to its children, and a node is said to be the '''parent''' of its children. A node that has at least one child is called an '''internal node''', and a node that has no children is called a '''leaf node'''. | ||
| - | ==Paths== | + | == Paths == |
| - | If | + | |
| - | sequence is called a path. The length of the path is the number of edges, which is one less | + | If n<sub>1</sub>, n<sub>2</sub>, …, n<sub>n</sub> is a sequence of nodes in the tree such that ni is the parent of n<sub>i+1</sub>, then this sequence is called a path. The length of the path is the number of edges, which is one less than the number of node: in this case the length of the path is n-1. If there is a path from a node M to a node N, then N is called a '''descendent''' of M and M is called an '''ancestor''' of N. |
| - | than the number of node: in this case the length of the path is n-1. If there is a path from a | + | |
| - | node M to a node N, then N is called a descendent of M and M is called an ancestor of N. | + | |
==Depth/Level== | ==Depth/Level== | ||
Revision as of 14:03, 28 March 2009
A tree is a finite set of elements called nodes. The set is either empty, or consists of a node called the root together with any number of successors which are also trees (subtrees in this case), which are disjoint from each other and from the root. The roots of the subtrees are called children of the root, and there is an edge from each node to its children, and a node is said to be the parent of its children. A node that has at least one child is called an internal node, and a node that has no children is called a leaf node.
Paths
If n1, n2, …, nn is a sequence of nodes in the tree such that ni is the parent of ni+1, then this sequence is called a path. The length of the path is the number of edges, which is one less than the number of node: in this case the length of the path is n-1. If there is a path from a node M to a node N, then N is called a descendent of M and M is called an ancestor of N.
Depth/Level
The depth of a node M in the tree is the length of the path from the root to M. Thus the depth of the root is 0. The height of the tree is 1 more than the depth of the deepest node. All nodes at depth d are said to be at level d.
