Using Box to build a tree

In C I made a program that played a game with the user. It asked questions until no more data were available and then it guessed an answer. If the answer was wrong, the user could add another question, and could play again. The idea was that the program would learn by playing. The basic data-structure I used was a tree of structs, with in it a pointer to another node if the answer was yes, a pointer to another node if the answer was no, and a union with a question, or if the nodes were NULL with an answer.

I am trying to rewrite this in Rust, to learn how Rust does these things. With some help of ChatGPT I think something like this should do what I want:

enum TreeNode {
    Question {
        text: String,
        yes: Box<TreeNode>,
        no: Box<TreeNode>,
    },
    Answer {
        text: String,
    },
}

The enum makes it possible not only to have the advantage of the union in C of not wasting space, but also it should make it more straight forward if I have reached an answer. Not by testing the pointers being NULL, but simply by testing if I have a TreeNode::Question or a TreeNode::Answer.

And as I understand it, the Box plays the role of the pointer in C.

Do I understand this correctly? And next step, is this "doing C stuff in Rust" the best way to approach the problem, or would Rust allow for a better way to solve the problem of a growable structure of data-elements with two branches?

The Box type is a kind of pointer in the general sense: it's a smart pointer, i.e. a UDT that provides indirection.

The Box here, in this case plays the role of the pointer in your equivalent C code. However, C only has one kind of pointer, while Rust has many pointer-like types. Box is only one of them. Box is essentially an owned, heap-allocated piece of data. There are other smart pointers like Rc and Arc for reference counting (multiple ownership); raw pointers *const T and *mut T which behave much like raw pointers in C (no type-checked ownership), and references &T and &mut T (no ownership, but temporary borrows verified at compile-time).

A tree is a tree in every language. It's fine to build trees in Rust.

5 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.