Basically, if your tree is static or you only add nodes, the easiest option is to store all nodes in a Vec and have the child/parent links be indices. I recommend the typed-index-collection crate if you go that route.
If you need to move/delete nodes a lot then either Rc<Refcell< or you can wrap the Vec in something that takes care of the admin of fixing up pointers.
If you want to get really fancy you can even do things like compacting GC. You’re basically implementing a memory allocator at that point.
Note that you might say “what’s the point of Rust if I just have to implement a memory allocator to bypass the borrow checker?” but that’s silly. You still get the benefits of Rust for the rest of your code, and Rust still prevents things like type confusion and UB.
Basically, if your tree is static or you only add nodes, the easiest option is to store all nodes in a Vec and have the child/parent links be indices. I recommend the typed-index-collection crate if you go that route.
If you need to move/delete nodes a lot then either Rc<Refcell< or you can wrap the Vec in something that takes care of the admin of fixing up pointers.
E.g. see this crate https://crates.io/crates/orx-tree
If you want to get really fancy you can even do things like compacting GC. You’re basically implementing a memory allocator at that point.
Note that you might say “what’s the point of Rust if I just have to implement a memory allocator to bypass the borrow checker?” but that’s silly. You still get the benefits of Rust for the rest of your code, and Rust still prevents things like type confusion and UB.