Here we give definitions and links to several different types of tree structures
Simple Definitions:
A tree (or free tree) is a connected, acyclic, undirected graph
If an undirected graph is acyclic, but disconnected, it is called a forest.
rooted trees have a distinguished node called the root - r.
x is an ancestor of y if x is on the unique simple path between r and y.
In the case above, y is a descendent of x.
- A node is both a descendent and a ancestor to itself.
If x is an ancestor to y and x!=y then x is a proper acestor of y.
- Proper descendent is similarly defined.
We use child and parent for nodes with edges between them. Likewise we use the term siblings for nodes that have the same parent.
A node with no children is an external node
A non-leaf node is an internal node.
The subtree rooted at x is the tree induced by descendants of x, rooted at x.
The number of children of a node in a rooted tree T is called the degree of the node.
The length of the path (edges) from the root r to a node x is the depth of x in T.
The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf.
The height of a tree is the height of its root.
The following are equivalent:
- G is a free tree.
Any 2 vertices in G are connected by a unique SimplePath
- G is connected, but if any edge is removed from E, the resulting graph is disconnected
- G is connected, and |E|=|V|-1.
- G is acyclic, and |E|=|V|-1.
- G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.