rust - 如何在 Rust 中为二叉树编写删除函数？

Question

我正在尝试学习一些 Rust 并从实现二叉树开始。虽然插入和按顺序遍历似乎很容易，但我在删除方法中的借用检查器遇到了一些麻烦。
到目前为止的代码是:

use std::cmp::{Ordering, PartialOrd};
use std::fmt::Display;

struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T: Display + PartialOrd> Node<T> {
    fn new(val: T) -> Self {
        Node {
            value: val,
            left: None,
            right: None,
        }
    }

    fn print_inorder(&self) {
        print!("[");
        self.inorder(|x| print!("{}, ", x));
        print!("]\n")
    }

    fn inorder(&self, f: fn(&T)) {
        if let Some(ref x) = self.left {
            (*x).inorder(f);
        }
        f(&self.value);
        if let Some(ref x) = self.right {
            (*x).inorder(f);
        }
    }

    fn insert(&mut self, val: T) {
        let mut node = self;

        loop {
            if val == node.value {
                return;
            }

            let child = match val.partial_cmp(&node.value).expect("Key comparison failed") {
                Ordering::Less => &mut node.left,
                Ordering::Equal => return,
                Ordering::Greater => &mut node.right,
            };

            match child {
                Some(ref mut c) => node = c,
                None => { *child = Some(Box::new(Node::new(val))); return}
            }
        }
    }

    fn delete(&mut self, val: T) -> bool {
        if self.value == val {
            unimplemented!{"Cannot remove root (yet) :/"};
        }

        let mut node = self;

        loop {
            if val < node.value {
                if let Some(ref mut c) = node.left {

                    if c.value == val {
                        if c.left.is_none() && c.right.is_none() {
                            // Error: cannot assign to node.left here
                            node.left = None;
                        }
                        else if c.left.is_some() && c.right.is_none() {
                            // Error: again cannot assign to node.left but cannot even access c.left
                            node.left = c.left;
                        }
                        else if c.left.is_none() && c.right.is_some() {
                            node.left = c.right;
                        }
                        else {
                            // TODO: walk through child tree and get rightmost element
                        }
                        return true;
                    } else {
                        node = c;
                    }
                }
                else {
                    return false;
                }
            }
        }
    }
}

struct Tree<T> {
    root: Option<Node<T>>
}

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

    fn insert(&mut self, val: T) {
        match self.root {
            Some(ref mut n) => n.insert(val),
            None => self.root = Some(Node::new(val))
        }
    }

    fn print(&self) {
        match self.root {
            Some(ref n) => n.print_inorder(),
            None => println!("[]")
        }
    }
}

fn main() {
    println!("Hello, world!");

    let mut t = Tree::<i64>::new();
    t.print();
    t.insert(14);
    t.print();
    t.insert(7);
    t.insert(21);
    t.print();
}

所以在 delete方法我不能分配给我向下遍历的节点。但是要删除一个 Node我必须为其父级分配不同的值。
我找到了 this implementation但它不会为我编译(再次出现借用检查器问题)。

Answer 1

作为起点，我们可以使用递归解决方案来避免迭代解决方案面临的许多借用问题。
为了能够删除根节点，关键思想是问delete函数返回以节点为根的新子树；在 Tree 中需要稍作修改，以协调事物:

struct Tree<T> {
    root: Option<Box<Node<T>>>
}

我添加了 Box层，因为 Node包含 Option<Box<Node<T>>> ;这允许我们像处理另一个子节点一样处理 root。
然后，我编写递归 delete :

fn delete(mut this: Box<Node<T>>, target: &T) -> Option<Box<Node<T>>> {
    if target < &this.value {
        if let Some(left) = this.left.take() {
            this.left = Self::delete(left, target);
        }
        return Some(this);
    }

    if target > &this.value {
        if let Some(right) = this.right.take() {
            this.right = Self::delete(right, target);
        }
        return Some(this);
    }

    assert!(target == &this.value, "Faulty Ord implementation for T");

    match (this.left.take(), this.right.take()) {
        (None, None) => None,
        (Some(left), None) => Some(left),
        (None, Some(right)) => Some(right),
        (Some(mut left), Some(right)) => {
            if let Some(mut rightmost) = left.rightmost_child() {
                rightmost.left = Some(left);
                rightmost.right = Some(right);
                Some(rightmost)
            } else {
                left.right = Some(right);
                Some(left)
            }
        },
    }
}

//  Returns the rightmost child, unless the node itself is that child.
fn rightmost_child(&mut self) -> Option<Box<Node<T>>> {
    match self.right {
        Some(ref mut right) =>  {
            if let Some(t) = right.rightmost_child() {
                Some(t)
            } else {
                let mut r = self.right.take();
                if let Some(ref mut r) = r {
                    self.right = std::mem::replace(&mut r.left, None);
                }
                r
            }
        },
        None => None
    }
}

这是从 Tree 调用的通过:

fn delete(&mut self, target: &T) {
    if let Some(root) = self.root.take() {
        self.root = Node::delete(root, target);
    }
}

complete code可在操场上使用。