Rust实现N叉树时元素丢失问题求助

问题本质 #

你代码里的节点丢失，核心是所有树节点都是值拷贝的独立实例，没有实现引用共享：

• add方法中，你把新节点克隆一份放进父节点的child，又返回原节点——这俩是完全没关系的对象。给返回的tree3加子节点，修改的是这个独立副本，父节点tree0里存的tree3克隆体根本没变化，所以打印tree0时看不到4、5。
• 另外，parent字段存的是父节点的克隆体，不是原父节点的引用，完全不符合树的父子关联逻辑。

修正后的代码 #

用Rc<RefCell<T>>实现节点的引用共享，让所有操作都指向同一个实例：

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

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

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

impl<T> Tree<T>
where
    T: Debug + Clone,
{
    // 直接返回包裹好的引用类型，避免值拷贝
    pub fn new(elm: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            elm,
            child: Vec::new(),
            parent: None,
        }))
    }

    // 给指定父节点添加子节点，返回子节点的引用
    pub fn add(parent: &Rc<RefCell<Self>>, elm: T) -> Rc<RefCell<Self>> {
        let child_node = Rc::new(RefCell::new(Self {
            elm,
            child: Vec::new(),
            parent: Some(Rc::clone(parent)),
        }));
        // 将子节点引用加入父节点的子列表
        parent.borrow_mut().child.push(Some(Rc::clone(&child_node)));
        child_node
    }

    // 递归打印整个树
    pub fn print(node: &Rc<RefCell<Self>>) {
        let node_ref = node.borrow();
        println!("elm={:?}", node_ref.elm);
        for child in &node_ref.child {
            if let Some(child) = child {
                Self::print(child);
            }
        }
    }
}

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

    Tree::print(&tree0);
}

代码说明 #

1. 引用共享：所有节点都用Rc<RefCell<Tree<T>>>包裹，确保父子节点指向同一个实例，不会因为克隆产生独立副本。
2. add方法逻辑：创建子节点时，父节点引用直接克隆传入，同时把新节点的引用加入父节点的子列表，外部拿到的子节点和父节点里存的是同一个对象。
3. print方法：通过borrow()获取节点的不可变引用，递归打印所有子节点，全程不需要克隆任何节点。

运行后输出完整的树结构：

elm=0
elm=1
elm=2
elm=3
elm=4
elm=5

更直观的调用方式 #

如果习惯tree0.add(1)这种方法调用风格，可以给Rc<RefCell<Tree<T>>>扩展方法：

// 给引用类型扩展add方法
impl<T> Rc<RefCell<Tree<T>>>
where
    T: Debug + Clone,
{
    pub fn add(&self, elm: T) -> Rc<RefCell<Tree<T>>> {
        let child = Tree::new(elm);
        child.borrow_mut().parent = Some(Rc::clone(self));
        self.borrow_mut().child.push(Some(Rc::clone(&child)));
        child
    }
}

// main函数可以简化为：
fn main() {
    let tree0 = Tree::new(0);
    tree0.add(1);
    tree0.add(2);
    let tree3 = tree0.add(3);

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

    Tree::print(&tree0);
}

内容的提问来源于stack exchange，提问作者YaOo