The preorder tree traversal
Rust Programming Language
Problem
Rust program that performs a preorder traversal of a binary tree.
Input
struct TreeNode {val: i32,left: Option<Box<TreeNode>>,right: Option<Box<TreeNode>>,}impl TreeNode {fn new(val: i32) -> Self {Self { val, left: None, right: None }}}fn preorder_traversal(root: Option<Box<TreeNode>>) {if let Some(node) = root {println!("{}", node.val);preorder_traversal(node.left);preorder_traversal(node.right);}}fn main() {// Construct the treelet mut root = TreeNode::new(1);root.left = Some(Box::new(TreeNode::new(2)));root.right = Some(Box::new(TreeNode::new(3)));root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(4)));root.left.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));root.right.as_mut().unwrap().left = Some(Box::new(TreeNode::new(6)));root.right.as_mut().unwrap().right = Some(Box::new(TreeNode::new(7)));// Perform the preorder traversalprintln!("Preorder traversal:");preorder_traversal(Some(Box::new(root)));}{codeBox}
Output
Preorder traversal:1245367{codeBox}
Explanation
In this implementation, the TreeNode struct represents a node in the binary tree. Each node has a value and pointers to its left and right children. The preorder_traversal function performs a preorder traversal of the tree recursively by first printing the current node's value, then visiting the left subtree, and finally visiting the right subtree. The main function constructs a sample tree and performs a preorder traversal of the tree, printing out the values of each visited node.
The preorder traversal visits the nodes of the tree in a "top-down" order, where the current node is visited before its children. This program can be easily modified to suit different tree structures or algorithms.