Need help creating a Tree/Node struct

help
2

You can't use references to build trees or graphs. References are intended only for giving out temporary immutable views into an existing data structure. Among other things, they enforce that the thing they point at cannot be modified for the entire duration in which the reference exists.

As for owned references (i.e. Box), you also cannot use those because of your parent pointers. Ownership cannot be cyclical, but node.children[0].parent would give you back node, which is cyclical.

This leaves you three options:

Remove the parent pointers.

If we remove the parent pointers, then it is no longer cyclical and we can use ownership. Note that Box isn't needed because Vec already puts the elements on the heap.

struct Node {
    value: String,
    children: Vec<Node>,
}

Use reference counting for shared ownership

The Rust language provides a type called Rc that allows for shared ownership.

struct Node {
    parent: Option<Weak<RefCell<Node>>>,
    value: String,
    children: Vec<Rc<RefCell<Node>>>,
}

Unfortunately, the Rc type provides only immutable access to its contents. To modify the inner value, a RefCell is necessary. This strategy can be pretty unpleasant for that reason, and I recommend avoiding it.

(If you don't need to modify the nodes after creating them, then you do not need the RefCell.)

Use integers instead of references

People tend to find this option ugly, but it actually works really well.

struct Graph {
    nodes: Vec<Node>,
}

struct Node {
    parent: Option<usize>,
    value: String,
    children: Vec<usize>,
}

Notice how none of these solutions involve any lifetimes. A struct should never be annotated with a lifetime unless it is a temporary view into an existing data structure.

11 Likes