diff options
| -rw-r--r-- | mgr.tex | 16 |
1 files changed, 16 insertions, 0 deletions
@@ -115,6 +115,22 @@ Binary trees are trees where each node has either no children (the node is a leaf), or exactly two children (which, based on their order, can be called the left and the right child). +The \definedterm{post-order} of $V(T)$ is an ordering of $T$'s vertices produced +by the following recursive procedure: + +\begin{enumerate} + \item First traverse the root's subtrees. + \item Visit the root. +\end{enumerate} + +Similarly, the \definedterm{pre-order} of $V(T)$ is produced by the following +recursive procedure: + +\begin{enumerate} + \item First visit the root. + \item Traverse the root's subtrees. +\end{enumerate} + \subsection{Tree automata} Consider the case of binary trees labeled with $\Sigma$. A |