如何在 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方法中我无法分配给我向下遍历的节点。但是要删除 aNode我必须为其父级分配不同的值。

我找到了这个实现，但它不适合我编译（再次出现借用检查器问题）。

Answer 1

作为起点，我们可以使用递归解决方案来避免迭代解决方案面临的许多借用问题。

为了能够删除根节点，关键思想是要求函数delete返回以该节点为根的新子树；为了协调事物，需要对 Tree 进行一些细微的修改：

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

我添加了Box图层，因为Node包含Option<Box<Node<T>>>；这允许我们像处理另一个子节点一样处理根。

然后，我编写递归代码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
    }
}

这是从Treevia 调用的：

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

完整的代码可以在 Playground 上找到。