rust 我需要帮助编码一个简单的N元树

6g8kf2rb  于 12个月前  发布在  其他
关注(0)|答案(1)|浏览(73)

树失去了它的元素?
我尝试了几种方法来解决这个问题,但都没有成功。我认为这个问题可能是由于Vec::push()的参数的clone(),但我不知道如何处理它不同。

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();
}

字符串

y1aodyip

y1aodyip1#

您不能有一个Rc<RefCell>的父链接,但有裸子链接。如果您想要(安全)的父链接,您需要两个都是Rc<RefCell>
下面是一个可能的实现:

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的一个。
是的,这是丑陋的。您可以(并且应该)用封装操作的结构体来 Package 顶级Tree。它仍然是丑陋和脆弱的。
在Rust中实现带有父链接的树的正确方法是使用图形库(如petgraph)作为图形,或者使用不安全的代码。无论是哪种方法,初学者都不应该自己实现它。学习Rust有更好的方法。

相关问题