m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 14:32:03 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 14:32:03 +0200
commit211b76591f2a35aa4234a7b1554abac8c4d10a0c (patch)
tree682290a924c2fba3f2b0002552e2b9093693a319
parent3509ea1cea043944b676bc33f41ed9bb1867f7cf (diff)
Define tree traversals
-rw-r--r--mgr.tex16
1 files changed, 16 insertions, 0 deletions
diff --git a/mgr.tex b/mgr.tex
index 65e596a..7074ec3 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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