(a) composed of nodes
(b) where each node has indegree 1, outdegree zero or more.
(therefore unique parent)
(c) leaf node has outdegree = 0
(d) root is unique node with indegree = 0
(e) unique path from any node to root (vice versa)
(f) NO CYCLES and NO LOOPS
(g) n nodes, n-1 edges
(h) A forest is a collection of trees
Some Definitions
PATH: a sequence of nodes, n1, n2, ...,nk where ni is the parent of ni+1. ANCESTOR: ni is an ancestor of nk if there is a path from ni to nk DESCENDANT: nk is a descendant of ni if there is a path from ni to nk LEAF: a node is a leaf if it has no descendants HEIGHT: of a tree is the length of the longest path DEPTH: of a node ni is the distance from the root to ni. SIBLINGS: ni and nj are siblings if they have the same parent
Traversing a Tree (preorder, inorder, and postorder)
A useful trick for producing the 3 traversals is as follows.
Walk around the outside of the tree, starting at the root, moving
counter clockwise, staying as close to the tree as possible. For
preorder, list the label of the node FIRST time we pass it. For
postorder, list the label of the node the LAST time we pass it. For
inorder, list the label of the node if it is a leaf, otherwise (it is
an "interior" node) list the label of the node the SECOND time we
visit it.
These 3 traversals for trees are described in the source file /home/s7/pat/scheme/pub/tree.scm
Expression trees and relationship between tree traversal
We can think of lists as trees, for example (+ (* A B) (* C D))
is a tree with + as the root node with descendants (* A B) and (* C D),
where (* A B) is a tree with * as the root and A and B as descendants,
and (* C D) is a tree with * as the root, and C and D as descendants.
If we traverse this tree in preorder we get prefix notation, and tarversal in postorder gives us postfix (Polish) notation. Both notations do away with the need for brackets.
Representing a Tree
We might use a vector v, where (vector-ref v i) is the immediate
parent of the ith node, ni. The root node would have (vector-ref v root)
equal to zero. This is "crisp" but looks at the tree "bottom up", and
we cannot easily traverse the tree, or get the desecndants of a node.
An alternative representation is to have an array such that the first row correspond to the labels of nodes, and the second column corresponds to the list of descendants.
Essentially, this is the representation used in the tree.scm implementation. A node has a label attribute (label node) and a descendants attribute (descendants node), where the descendants is a list of nodes. See /home/s7/pat/scheme/pub/tree.scm