我试图找出典型的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
}
}
像这样表示图节点的规范方法是什么?
1条答案
按热度按时间but5z9lq1#
问:像这样表示图节点的规范方法是什么?
一旦你引入了兄弟链接,这似乎是一个典型的“混淆所有权”的案例:对于严格树,你可以让每个父节点拥有它的子节点,但是兄弟节点链接意味着这是一个图,并且一个给定的节点有多个所有者。
AFAIK有两个主要的方法来解决这个问题,至少在安全生 rust
这两种方法基本上都是围绕所有权约束工作的,一种方法是混淆所有权本身,另一种方法是将所有权转移到更高的权力(数组)。
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=68d092d0d86dc32fe07902c832262ef4看起来或多或少是你正在寻找使用Rc和内部可变性:
注意,我假设树一旦创建就不可变,只有兄弟链接需要事后生成,所以我只为它们添加了内部可变性,我还使用了可能不必要的弱指针。如果树被置于不一致的状态,它不会保存任何东西。它所需要的只是一些
upgrade()
和downgrade()
调用,而不是clone()
,所以它“It“这不是什么大麻烦。除此之外,你的尝试还有很多问题:
Option
是不必要的,函数显然期望 * 设置一个兄弟 *,只需给予它一个兄弟,并删除不必要的测试外层match
在您需要的时候是很好的,在这里,您可能不需要,if let
可以很好地完成这个任务,特别是因为没有else
分支new
(如果只有一个)