Rust中具有指向同级节点的指针的二叉树节点

jc3wubiy  于 2022-12-26  发布在  其他
关注(0)|答案(1)|浏览(125)

我试图找出典型的setSibling 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(left);
      SetSibling(right);
   }
}

当然铁 rust 是一个不同的世界,所以我现在被迫考虑所有权。我糟糕的尝试。

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
    }
}

像这样表示图节点的规范方法是什么?

but5z9lq

but5z9lq1#

问:像这样表示图节点的规范方法是什么?
一旦你引入了兄弟链接,这似乎是一个典型的“混淆所有权”的案例:对于严格树,你可以让每个父节点拥有它的子节点,但是兄弟节点链接意味着这是一个图,并且一个给定的节点有多个所有者。
AFAIK有两个主要的方法来解决这个问题,至少在安全生 rust

  • 引用计数和内部可变性,如果每个节点都是引用计数的,兄弟链接可以是引用或弱引用,几乎没有问题,主要缺点是这需要内部可变性,导航是“粗糙的”,尽管一些实用方法可以帮助
  • 将图“展开”为数组,并使用索引来间接访问树,主要缺点是这需要线程化或保持对数组的反向引用(具有内部可变性),或者迭代地执行所有操作

这两种方法基本上都是围绕所有权约束工作的,一种方法是混淆所有权本身,另一种方法是将所有权转移到更高的权力(数组)。
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=68d092d0d86dc32fe07902c832262ef4看起来或多或少是你正在寻找使用Rc和内部可变性:

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

#[derive(Default)]
pub struct TreeNode {
    left: Option<Rc<TreeNode>>,
    right: Option<Rc<TreeNode>>,
    sibling: RefCell<Option<Weak<TreeNode>>>,
    v: u8,
}

impl TreeNode {
    pub fn new(v: u8) -> Rc<Self> {
        Rc::new(TreeNode {
            v,
            ..TreeNode::default()
        })
    }
    pub fn new_with(left: Option<Rc<TreeNode>>, right: Option<Rc<TreeNode>>, v: u8) -> Rc<Self> {
        Rc::new(TreeNode {
            left,
            right,
            v,
            sibling: RefCell::new(None),
        })
    }
    pub fn set_siblings(self: &Rc<Self>) {
        let Some(left) = self.left() else { return };
        let right = self.right();

        left.sibling.replace(right.map(Rc::downgrade));

        if let Some(sibling) = self.sibling() {
            // not sure this is correct, depending on construction, with
            // 3  5
            //  \  \
            //  2  4
            //   \/
            //   1
            // (2) has a sibling (4) but doesn't have a right node, so 
            // unconditionally setting right.sibling doesn't seem correct
            right
                .unwrap()
                .sibling
                .replace(sibling.left().map(Rc::downgrade));
        }

        left.set_siblings();
        right.map(|r| r.set_siblings());
    }

    pub fn left(&self) -> Option<&Rc<Self>> {
        self.left.as_ref()
    }
    pub fn right(&self) -> Option<&Rc<Self>> {
        self.right.as_ref()
    }
    pub fn sibling(&self) -> Option<Rc<Self>> {
        self.sibling.borrow().as_ref()?.upgrade()
    }
}

fn main() {
    let t = TreeNode::new_with(
        TreeNode::new_with(TreeNode::new(1).into(), TreeNode::new(2).into(), 3).into(),
        TreeNode::new(4).into(),
        5,
    );
    t.set_siblings();

    assert_eq!(t.left().and_then(|l| l.sibling()).unwrap().v, 4);
    let ll = t.left().and_then(|l| l.left());
    assert_eq!(ll.map(|ll| ll.v), Some(1));
    ll.unwrap().sibling().unwrap();
    assert_eq!(
        t.left()
            .and_then(|l| l.left())
            .and_then(|ll| ll.sibling())
            .unwrap()
            .v,
        2
    );
}

注意,我假设树一旦创建就不可变,只有兄弟链接需要事后生成,所以我只为它们添加了内部可变性,我还使用了可能不必要的弱指针。如果树被置于不一致的状态,它不会保存任何东西。它所需要的只是一些upgrade()downgrade()调用,而不是clone(),所以它“It“这不是什么大麻烦。
除此之外,你的尝试还有很多问题:

  • 引用和内容具有相同的生命周期通常是一个错误,编译器 * 将 * 信任您告诉它的内容,这可能会产生相当奇怪的效果(例如,告诉编译器某些内容将被永远借用)
  • SetSibling(顺便说一句,命名约定不正确)获取Option是不必要的,函数显然期望 * 设置一个兄弟 *,只需给予它一个兄弟,并删除不必要的测试外层
  • match在您需要的时候是很好的,在这里,您可能不需要,if let可以很好地完成这个任务,特别是因为没有else分支
  • rust通常使用方法,创建示例的方法(如果需要)习惯上称为new(如果只有一个)

相关问题