I need help for coding a simple an N-ary tree

Question

The tree looses its elements???

I tried several ways to solve this problem but I didn't succeed. I think that the problem could be due to the clone() of the argument to Vec::push(), but I dont know how to manage it differenly.

use std::{cell::RefCell, fmt::Debug, rc::Rc};

type Link<T> = Option<Rc<RefCell<Tree<T>>>>;

#[derive(Clone, Debug)]
pub struct Tree<T>
where
    T: Clone,
    T: Debug,
{
    elm: T,
    child: Vec<Tree<T>>,
    parent: Link<T>,
}

impl<T> Tree<T>
where
    T: Clone,
    T: Debug,
{
    pub fn new(elm: T) -> Self {
        Self {
            elm: elm,
            child: Vec::<Tree<T>>::new(),
            parent: None,
        }
    }
    pub fn add(&mut self, elm: T) -> Self {
        let new_tree = Tree {
            elm: elm,
            child: Vec::<Tree<T>>::new(),
            parent: Some(Rc::new(RefCell::new(self.clone()))),
        };

        self.child.push(new_tree.clone());
        new_tree
    }

    pub fn print(&mut self) {
        println!("elm={:?}", self.elm);
        if 0 != self.child.len() {
            for elm in self.child.iter() {
                elm.clone().print();
            }
        }
    }
}

fn main() {
    let mut tree0 = Tree::new(0);
    tree0.add(1);
    tree0.add(2);
    let mut tree3 = tree0.add(3);

    tree3.add(4);
    tree3.add(5);

    tree0.print();
}

Answer 1

You can't have a parent link which is Rc<RefCell> but have bare children links. If you want (safe) parent links, you need both to be Rc<RefCell>.

Here's a possible implementation:

use std::{cell::RefCell, fmt::Debug, rc::Rc};

type Link<T> = Rc<RefCell<Tree<T>>>;

#[derive(Clone, Debug)]
pub struct Tree<T> {
    elm: T,
    child: Vec<Link<T>>,
    parent: Option<Link<T>>,
}

impl<T> Tree<T> {
    pub fn new(elm: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            elm: elm,
            child: Vec::new(),
            parent: None,
        }))
    }
    pub fn add(this: &Rc<RefCell<Self>>, elm: T) -> Rc<RefCell<Self>> {
        let new_tree = Rc::new(RefCell::new(Tree {
            elm: elm,
            child: Vec::new(),
            parent: Some(Rc::clone(this)),
        }));

        this.borrow_mut().child.push(Rc::clone(&new_tree));
        new_tree
    }

    pub fn print(&self)
    where
        T: Debug,
    {
        println!("elm={:?}", self.elm);
        for elm in self.child.iter() {
            elm.borrow().print();
        }
    }
}

fn main() {
    let tree0 = Tree::new(0);
    Tree::add(&tree0, 1);
    Tree::add(&tree0, 2);
    let tree3 = Tree::add(&tree0, 3);

    Tree::add(&tree3, 4);
    Tree::add(&tree3, 5);

    tree0.borrow().print();
}

Playground.

Yes, this is ugly. You can (and should) wrap the top-level Tree with a struct that encapsulates the operations. It'll still be ugly and fragile.

The correct way to implement a tree with parent links in Rust is either as a graph, by using a graph library such as petgraph, or with unsafe code. Either way you should not implement it yourself as a beginner. There are better ways to learn Rust.