I am trying to find a good way to remember how tree traversals work.
At a high level, is it basically:
pre-order = lisp
in-order = infix notation
post-order = forth
?
I am trying to find a good way to remember how tree traversals work.
At a high level, is it basically:
pre-order = lisp
in-order = infix notation
post-order = forth
?
Consider a node N
in the tree and let A
and B
be the two subtrees below N
. Then:
N
, A
, B
A
, N
, B
A
, B
, N
So the pre/in/post word simply determines where the N
is in relation to A
and B
.
The way I remember it is where I would put the recursive calls when implementing it in code.
So for pre-order I'll call my callback before recursing, in-order will recurse on left then call the callback then recurse on right, and post-order will do all the recursion before calling the callback.
struct Tree<T> {
value: T,
left: Option<Box<Tree<T>>>,
right: Option<Box<Tree<T>>>,
}
impl<T> Tree<T> {
fn pre(&self, callback: &dyn Fn(&T)) {
callback(&self.value);
if let Some(left) = &self.left { left.pre(callback);
if let Some(right) = &self.right { right.pre(callback); }
}
fn in_(&self, callback: &dyn Fn(&T)) {
if let Some(left) = &self.left { left.in_(callback); }
callback(&self.value);
if let Some(right) = &self.right { right.in_(callback); }
}
fn post(&self, callback: &dyn Fn(&T)) {
if let Some(left) = &self.left { left.post(callback); }
if let Some(right) = &self.right { right.post(callback); }
callback(&self.value);
}
}
Preorder/inorder/postorder traversal is not particularly related to prefix/infix/postfix notation, except that they use the same Latinate prefixes (no pun intended):
In prefix notation, an operator is placed (i.e., fixed) before its operands. In preorder graph traversal, a node is visited (i.e., ordered) before its children. Although mathematical notation is often represented with a tree, there is no particularly strong connection between the two concepts.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.