15-16, 18 April 2002

Link back to last week — Non-recursive in-order and post-order traversals.

Count.txt            Functions to count categories of nodes

Data Hiding Example:  A general tree (arbitrarily many children at each node) is stored as its associated binary tree.  The external behavior of the general tree is as expected (for instance, a post-order traversal exhausts all children of a node before listing the node itself), but the underlying algorithms used are different because of the (hidden) implementation used to store the general tree (for instance, in-order traversal of the associated binary tree actually visits the nodes in a general-tree post-order fashion).

GenTree.h          Header: struct and class definitions and prototypes
GenTree.cpp       Implementation code

TstGenTr.cpp     Main to exercise the general tree class
GenTree.exe       Executable — Note that "TreeInp.txt" must be in the default directory for this to work.

TreeInp.txt          Input file expected by GenTree.exe

DemoRun.txt       Specimen run (from a Linux machine)

GenTree.rtf         Word-processor file (all code segments formatted to 2-column text)

String.h               Header file for minimal String class implementation used
String.cpp           Member function implementation

DEQueue.h          Header file for a double-ended queue (stack and queue behaviors in the same structure)
DEQueue.cpp     Member function implementation file (required for level-order traversal)

Binary Tree Program Example:  Prefix notation calculator based on a binary expression tree

ExprTree.cpp       Expression tree — Prefix notation calculator
ExprTree.exe       Executable version
ExprTree.rtf         Class hand-out — above code as two-column eight-point text.
ExprWalk.rtf        Hand-out on recursive versus non-recursive implementations
ExprWalk.txt       Above in pure-text form