52.219 Trees

Example of trees ... your family, contents of a book, bill of materials (bom, a parts explosion), organisation chart, databases (sometimes), object oriented class/sub-class/instance, structure of program (program calls functions, functions call functions, and so on), expressions. Mathematical description of a tree ... "A connected graph with no cycles".
   (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)
   (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