Rust Program to Implement Binary Tree Data Structure


Binary Tree Data Structure

Rust Programming Language


Binary Tree Data Structure


Problem


Rust program that implements a binary tree data structure.

Input


// Define a struct for a binary tree node
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

// Define a function to insert a new node into the binary tree
fn insert_node(root: &mut Option<Box<Node>>, value: i32) {
    if let Some(ref mut node) = root {
        if value < node.value {
            insert_node(&mut node.left, value);
        } else {
            insert_node(&mut node.right, value);
        }
    } else {
        *root = Some(Box::new(Node {
            value,
            left: None,
            right: None,
        }));
    }
}

// Define a function to print out the contents of the binary tree in order
fn inorder_traversal(root: &Option<Box<Node>>) {
    if let Some(ref node) = root {
        inorder_traversal(&node.left);
        println!("{}", node.value);
        inorder_traversal(&node.right);
    }
}

fn main() {
    // Create an empty root node
    let mut root = None;

    // Insert some values into the binary tree
    insert_node(&mut root, 5);
    insert_node(&mut root, 3);
    insert_node(&mut root, 7);
    insert_node(&mut root, 1);
    insert_node(&mut root, 9);

    // Print out the contents of the binary tree in order
    inorder_traversal(&root);
}{codeBox}

Output


1
3
5
7
9{codeBox}

Explanation


In this example, the Node struct represents a single node in the binary tree, containing a value and pointers to its left and right child nodes. The insert_node function recursively inserts new nodes into the binary tree based on their values, and the inorder_traversal function recursively prints out the contents of the binary tree in order.

The main function creates an empty root node, inserts some values into the binary tree, and then prints out the contents of the binary tree in order.

This is the inorder traversal of the binary tree that was created in the main function, which includes the values 1, 3, 5, 7, and 9. The inorder traversal visits the left subtree first, then the root node, and then the right subtree. In this case, the left subtree of the root node contains the values 1 and 3, the right subtree contains the values 7 and 9, and the root node itself contains the value 5. Therefore, the inorder traversal visits the nodes in the order 1, 3, 5, 7, 9.


Post a Comment