m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-14 16:45:34 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-14 16:45:34 +0200
commitf9327f40de61dc6e0ef994bc8d661fe17c096157 (patch)
tree6fdfff86414d17c5b25ddc05631a669a0e8411c3
parent5de51f2643906035cdcc827a47a18413b97f1c56 (diff)
Add in order traversal
-rw-r--r--mgr.tex10
1 files changed, 10 insertions, 0 deletions
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