Rust中实现带兄弟指针的二叉树节点及setSibling功能的规范方式

我想实现C语言中经典的setSibling练习的Rust等价代码。以下是C语言实现（假设树为完全平衡状态，即最低层节点完全填充）：

// Assume the tree is fully balanced, i.e. the lowest level is fully populated.
struct Node {
   Node * left;
   Node * right;
   Node * sibling;
}

void setSibling(Node * root) {
   if (!root) return;
   if (root->left) {
      root->left->sibling = root->right;
      if (root->sibling) root->right->sibling = root->sibling->left;
      setSibling(root->left);
      setSibling(root->right);
   }
}

由于Rust的所有权机制与C不同，我在尝试实现时遇到了问题，以下是我的初步尝试：

struct TreeNode<'a> {
    left: Option<&'a TreeNode<'a>>,
    right: Option<&'a TreeNode<'a>>,
    sibling: Option<&'a TreeNode<'a>>,
    value: String
}

fn BuildTreeNode<'a>(aLeft: Option<&'a TreeNode<'a>>, aRight: Option<&'a TreeNode<'a>>, aValue: String) -> TreeNode<'a> {
    TreeNode {
        left: aLeft,
        right: aRight,
        value: aValue,
        sibling: None
    }
}

fn SetSibling(node: &mut Option<&TreeNode>) {
    match node {
        Some(mut n) => {
            match n.left {
                Some(mut c) => {
                    //c*.sibling = n.right;
                    match n.sibling {
                        Some(s) => { n.right.unwrap().sibling = s.left },
                        None => {}
                    }
                },
                None => {}
            }
        },
        None => return
    }
}

请问在Rust中，表示这类图节点的规范方式是什么？

在Rust中处理这类带共享可变引用的图/树节点，最规范的方式是结合Rc（引用计数，实现共享所有权）和RefCell（内部可变性，允许在共享引用下修改内部字段）。你的初始尝试使用了普通引用，但普通引用受限于严格的生命周期规则，无法处理节点间的交叉引用，也不能在不可变引用下修改sibling字段。

核心思路 #

1. Rc：让多个节点共享同一个节点的所有权，解决跨节点引用的所有权问题，每次克隆会增加引用计数，计数归零时自动释放节点。
2. RefCell：提供内部可变性，允许在持有共享引用的情况下修改内部字段，其借用规则在运行时检查，而非编译时。

完整实现代码 #

use std::cell::RefCell;
use std::rc::Rc;

// 定义带共享所有权和内部可变性的树节点
#[derive(Debug)]
struct TreeNode {
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
    sibling: Option<Rc<RefCell<TreeNode>>>,
    value: String,
}

impl TreeNode {
    // 创建新节点的辅助函数
    fn new(value: String) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(TreeNode {
            left: None,
            right: None,
            sibling: None,
            value,
        }))
    }
}

fn set_sibling(node: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node_rc) = node {
        let mut node_ref = node_rc.borrow_mut();
        // 确保当前节点同时有左右子节点
        if let (Some(left_rc), Some(right_rc)) = (&node_ref.left, &node_ref.right) {
            // 左子节点的兄弟设为右子节点
            left_rc.borrow_mut().sibling = Some(right_rc.clone());
            
            // 如果当前节点有兄弟，右子节点的兄弟设为当前兄弟的左子节点
            if let Some(sibling_rc) = &node_ref.sibling {
                if let Some(sibling_left_rc) = &sibling_rc.borrow().left {
                    right_rc.borrow_mut().sibling = Some(sibling_left_rc.clone());
                }
            }
            
            // 递归处理左右子节点
            set_sibling(Some(left_rc.clone()));
            set_sibling(Some(right_rc.clone()));
        }
    }
}

// 测试示例
fn main() {
    // 构建完全平衡树
    let root = TreeNode::new("root".to_string());
    let left = TreeNode::new("left".to_string());
    let right = TreeNode::new("right".to_string());
    let left_left = TreeNode::new("left_left".to_string());
    let left_right = TreeNode::new("left_right".to_string());
    let right_left = TreeNode::new("right_left".to_string());
    let right_right = TreeNode::new("right_right".to_string());

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());
    left.borrow_mut().left = Some(left_left.clone());
    left.borrow_mut().right = Some(left_right.clone());
    right.borrow_mut().left = Some(right_left.clone());
    right.borrow_mut().right = Some(right_right.clone());

    set_sibling(Some(root.clone()));

    // 验证结果
    assert_eq!(left.borrow().sibling.as_ref().unwrap().borrow().value, "right");
    assert_eq!(left_right.borrow().sibling.as_ref().unwrap().borrow().value, "right_left");
    println!("测试通过！");
}

补充说明 #

• 如果场景不需要跨节点共享所有权（比如树是一次性构建且无交叉引用），可以使用Box<T>，但sibling这种需要跨节点引用的场景下，Box的独占所有权特性无法满足需求。
• RefCell的运行时借用检查会在出现非法借用（比如同时持有多个可变引用）时触发 panic，编写代码时需注意避免此类情况。

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