Definition:In-Order Traversal of Labeled Tree/Variant 2
Jump to navigation
Jump to search
Definition
Let $T$ be a binary labeled tree.
In-order traversal of $T$ is an algorithm designed to obtain a string representation of $T$.
The steps are as follows:
This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
$\mathtt{Inorder} (T):$
- $n \gets t$, where $t$ is the root node of $T$.
- If $n$ is a leaf node, output the label of $n$, and stop.
- Let $T_1$ and $T_2$ be the left and right subtrees of $T$.
- Output a left bracket $($.
- If $n$ has only one child, skip this step. Output $\mathtt{Inorder} (T_1)$.
- Output the label of $n$.
- Output $\mathtt{Inorder} (T_2)$.
- Output a right bracket $)$.
- Stop.
Sources
- 2012: M. Ben-Ari: Mathematical Logic for Computer Science (3rd ed.) ... (previous) ... (next): $\S 2.1.3$: Algorithm $2.7$