如何在Rust中实现带父节点引用的树形数据结构？

你遇到的是Rust所有权规则下的典型场景：子节点用Box<Node>持有独占所有权，但父节点引用需要避免循环引用和违反借用规则。直接用裸不安全指针不是最优解，以下是几种安全且规范的实现方式：

方案一：用Rc<RefCell<Node>> + Weak<RefCell<Node>>实现安全双向引用 #

这是Rust中处理双向引用树形结构的标准方案，通过共享所有权+弱引用避免循环引用，内部可变性支持修改节点关系：

use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct Node {
    parent: Option<Weak<RefCell<Node>>>,
    child_1: Option<Rc<RefCell<Node>>>,
    child_2: Option<Rc<RefCell<Node>>>,
}

impl Node {
    // 创建根节点（无父节点）
    fn new_root() -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            parent: None,
            child_1: None,
            child_2: None,
        }))
    }

    // 创建子节点并关联父节点
    fn new_child(parent: &Rc<RefCell<Node>>) -> Rc<RefCell<Self>> {
        let child = Rc::new(RefCell::new(Node {
            parent: Some(Rc::downgrade(parent)),
            child_1: None,
            child_2: None,
        }));
        // 将子节点挂载到父节点的第一个空位置
        parent.borrow_mut().child_1.get_or_insert(child.clone());
        child
    }
}

核心逻辑说明： #

• Rc：让父节点和子节点共享节点的所有权，解决单一所有权无法双向引用的问题
• Weak：父节点引用使用弱引用，不会增加引用计数，避免父子节点形成循环引用导致内存泄漏
• RefCell：提供内部可变性，允许在共享所有权的前提下修改节点的子节点或父节点

方案二：用ID索引替代直接引用 #

如果不想引入智能指针的复杂度，可以给每个节点分配唯一ID，通过容器管理所有节点，父/子字段存储对应ID：

use std::collections::HashMap;
use std::sync::atomic::{AtomicU64, Ordering};

// 全局原子变量生成唯一节点ID
static NEXT_ID: AtomicU64 = AtomicU64::new(1);

struct Node {
    id: u64,
    parent: Option<u64>,
    child_1: Option<u64>,
    child_2: Option<u64>,
}

struct Tree {
    nodes: HashMap<u64, Node>,
}

impl Tree {
    fn new() -> Self {
        Tree { nodes: HashMap::new() }
    }

    // 添加根节点
    fn add_root(&mut self) -> u64 {
        let id = NEXT_ID.fetch_add(1, Ordering::Relaxed);
        self.nodes.insert(id, Node {
            id,
            parent: None,
            child_1: None,
            child_2: None,
        });
        id
    }

    // 给指定父节点添加子节点（最多2个）
    fn add_child(&mut self, parent_id: u64) -> Option<u64> {
        if !self.nodes.contains_key(&parent_id) {
            return None;
        }

        let child_id = NEXT_ID.fetch_add(1, Ordering::Relaxed);
        // 插入子节点
        self.nodes.insert(child_id, Node {
            id: child_id,
            parent: Some(parent_id),
            child_1: None,
            child_2: None,
        });

        // 更新父节点的子节点引用
        let parent = self.nodes.get_mut(&parent_id).unwrap();
        if parent.child_1.is_none() {
            parent.child_1 = Some(child_id);
        } else if parent.child_2.is_none() {
            parent.child_2 = Some(child_id);
        } else {
            // 子节点已满，回滚操作
            self.nodes.remove(&child_id);
            return None;
        }

        Some(child_id)
    }
}

核心逻辑说明： #

• 完全避开Rust的所有权和借用规则，通过ID查找节点，实现简单
• 适合不需要频繁直接访问父/子节点，或可以接受容器查找开销的场景

关于裸不安全指针的问题 #

不推荐直接使用裸指针（*const Node/*mut Node），原因如下：

• 裸指针绕过Rust的安全检查，极易出现悬垂指针、数据竞争等内存安全问题
• 需要手动管理内存生命周期，调试难度大
• 只有在对Rust内存模型有深入理解，且有明确性能需求必须使用时，才考虑这种方案

内容的提问来源于stack exchange，提问作者Евгений Павлов