Rosetta Code

Tree traversal: Difference between revisions

Page Discussion

Tree traversal (view source)

Revision as of 02:05, 5 June 2024

491 bytes removed ,  1 month ago
→‎{{header|Rust}}
No edit summary
Line 10,324:
}
 
// LeftmostFrom left to rightmostright
fn iterative_inorder(&self) -> Vec<&TreeNode<T>> {
let mut stack: Vec<&TreeNode<T>> = Vec::new();
let mut res: Vec<&TreeNode<T>> = Vec::new();
let mut poption_tree = Some(self);
}▼
 
loopwhile {
// Stack parents and right children whileDescend left-descendingleftwards
loopwhile let Some(tree) = option_tree {
match pstack.right {push(tree);
Noneoption_tree => {}tree.left.as_deref();
Some(box ref n) => stack.push(n),
}▼
stack.push(p);▼
match p.left {
None => break,
Some(box ref n) => p = n,
}
▲ }
// Visit the nodes with no right child
p = stack.pop().unwrap();▼
while !stack.is_empty() && p.right.is_none() {▼
res.push(p);
p = stack.pop().unwrap();▼
}
// First node that can potentially have a right child:
res.push(p);
if stack.is_empty() {
break;
} else {
p = stack.pop().unwrap();
}
▲ while !stack.is_empty() && p.right.is_none() {
▲ } }{
▲ plet tree = stack.pop().unwrap();
▲ stackres.push(ptree);
▲ poption_tree = stacktree.pop()right.unwrapas_deref();
}
res
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/364999"