gpt-4.1-mini-2025-04-14· OpenAI
LMArena Human Preference 140K
Implement a generic tree data structure in Rust.
- User
Implement a generic tree data structure in Rust.
- Assistant
Certainly! Below is a simple implementation of a generic tree data structure in Rust. This example uses
RcandRefCellto allow multiple ownership and interior mutability, which is common for tree structures where nodes can have multiple children and you want to mutate the tree after creation.use std::cell::RefCell; use std::rc::{Rc, Weak}; type NodeRef<T> = Rc<RefCell<TreeNode<T>>>; #[derive(Debug)] pub struct TreeNode<T> { pub value: T, pub parent: Option<Weak<RefCell<TreeNode<T>>>>, pub children: Vec<NodeRef<T>>, } impl<T> TreeNode<T> { pub fn new(value: T) -> NodeRef<T> { Rc::new(RefCell::new(TreeNode { value, parent: None, children: vec![], })) } pub fn add_child(parent: &NodeRef<T>, child_value: T) -> NodeRef<T> { let child = TreeNode::new(child_value); child.borrow_mut().parent = Some(Rc::downgrade(parent)); parent.borrow_mut().children.push(Rc::clone(&child)); child } pub fn parent(node: &NodeRef<T>) -> Option<NodeRef<T>> { node.borrow() .parent .as_ref() .and_then(|weak_parent| weak_parent.upgrade()) } pub fn children(node: &NodeRef<T>) -> Vec<NodeRef<T>> { node.borrow().children.clone() } } fn main() { // Example usage: let root = TreeNode::new("root"); let child1 = TreeNode::add_child(&root, "child1"); let child2 = TreeNode::add_child(&root, "child2"); let grandchild = TreeNode::add_child(&child1, "grandchild"); println!("Root: {:?}", root.borrow().value); println!("Children of root:"); for child in TreeNode::children(&root) { println!(" - {}", child.borrow().value); } if let Some(parent) = TreeNode::parent(&grandchild) { println!("Parent of grandchild: {}", parent.borrow().value); } }Explanation:
TreeNode<T>holds a value of generic typeT.- Each node has a
parentwhich is aWeakreference to avoid reference cycles. - Each node has a vector of
childrenwhich areRc<RefCell<TreeNode<T>>>. newcreates a new node with no parent and no children.add_childadds a child to a parent node, setting the child's parent pointer.parentreturns anOption<NodeRef<T>>to the parent node if it exists.childrenreturns a vector of children nodes.
This structure allows you to build and traverse a generic tree with parent and child relationships. Let me know if you want traversal methods or other features!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.