From f9327f40de61dc6e0ef994bc8d661fe17c096157 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 14 Oct 2021 16:45:34 +0200 Subject: Add in order traversal --- mgr.tex | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 4c95210..9aa3d92 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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 -- cgit v1.2.3