diff options
| -rw-r--r-- | mgr.tex | 10 |
1 files changed, 10 insertions, 0 deletions
@@ -213,6 +213,8 @@ 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). +\subsubsection{Tree traversals} + The \definedterm{post-order} of $V(T)$ is an ordering of $T$'s vertices produced by the following recursive procedure: @@ -229,6 +231,14 @@ recursive procedure: \item Traverse the root's subtrees. \end{enumerate} +Finally, the following procedure produces the \definedterm{in-order} of $V(T)$: + +\begin{enumerate} + \item First traverse the left subtree. + \item Visit the root. + \item Traverse the right subtree. +\end{enumerate} + \subsection{Tree automata} Consider the case of binary trees labeled with $\Sigma$. A |