-1

我试图add在二叉树中实现一个操作：

use std::cell::RefCell;
use std::cmp::PartialOrd;

type Link<T> = RefCell<Option<Box<Node<T>>>>;

struct Node<T> {
    key: T,
    left: Link<T>,
    right: Link<T>,
}

struct Tree<T> {
    root: Link<T>,
}

impl<T> Node<T> {
    fn new(val: T) -> Self {
        Node {
            key: val,
            left: RefCell::new(None),
            right: RefCell::new(None),
        }
    }
}

impl<T: PartialOrd> Tree<T> {
    fn new() -> Self {
        Tree {
            root: RefCell::new(None),
        }
    }

    fn add(&self, val: T) {
        let mut next = self.root.borrow();
        let node = Box::new(Node::new(val));
        match next.as_ref() {
            None => {
                self.root.replace(Some(node));
                ()
            }
            Some(root_ref) => {
                let mut prev = root_ref;
                let mut cur: Option<&Box<Node<T>>> = Some(root_ref);
                while let Some(node_ref) = cur {
                    prev = node_ref;
                    if node.key < node_ref.key {
                        next = node_ref.left.borrow();
                    } else {
                        next = node_ref.right.borrow();
                    }
                    cur = next.as_ref();
                }
                if node.key < prev.key {
                    prev.left.replace(Some(node));
                } else {
                    prev.right.replace(Some(node));
                }
            }
        }
    }
}

fn main() {}

我不明白为什么next变量的寿命不够长：

error[E0597]: `next` does not live long enough
  --> src/main.rs:36:15
   |
36 |         match next.as_ref() {
   |               ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `next` does not live long enough
  --> src/main.rs:51:27
   |
51 |                     cur = next.as_ref();
   |                           ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

next存在于函数的整个范围内，add并且在我看来，包含对它的引用的其他变量在删除之前next就被删除了。

编译器这么说"values in a scope are dropped in the opposite order they are created"，暗示有另一种方法来声明变量并解决这个问题，但我不知道如何。

4

1 回答 1

1

我看到的问题是，为了更新树的叶节点，您必须保存对每个中间步骤的引用，而不仅仅是它的父节点，因为在更新价值。而 Rust 的生命周期就是无法做到这一点。

也就是说，Rust 不能在循环中做到这一点，但它可以在递归函数中做到这一点，而树最好用递归函数来实现。

自然地，您的递归结构是Node，不是Tree，但是这样的东西可以工作（有很多方法可以让借用工作）：

impl<T: PartialOrd> Node<T> {
    fn add(&self, val: T) {
        let mut branch = if val < self.key {
            self.left.borrow_mut()
        } else {
            self.right.borrow_mut()
        };
        if let Some(next) = &*branch {
            next.add(val);
            return;
        }
        //Separated from the if let so that branch is not borrowed.
        *branch = Some(Box::new(Node::new(val)));
    }
}

然后，impl Tree只是将工作转交给这个。

如果像其他人指出的那样，您摆脱了TreevsNode和RefCell...

于 2018-08-06T18:26:06.573 回答