struct - 调用带 `self`的方法时不修改数据结构

Question

我正在写一个二叉树结构，我在 insert 函数上遇到了问题。在我的节点调用插入数据的函数后，节点没有被修改。

use std::ptr;

#[derive(Clone, Copy)]
struct Node<T> {
    data: Option<T>,
    left: *mut Node<T>,
    right: *mut Node<T>,
}

impl<T> Node<T> {
    pub fn new(data: T) -> Node<T> {
        Node {
            data: Some(data),
            left: ptr::null_mut(),
            right: ptr::null_mut(),
        }
    }

    pub fn insert(mut self, data: T) {
        let tmp = self.data.unwrap();
        self.data = None;

        self.left = &mut Node::new(data);
        self.right = &mut Node::new(tmp);
    }
}

impl<T: std::fmt::Display> std::fmt::Display for Node<T>
    where T: std::fmt::Debug
{
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self.data {
            Some(ref x) => {
                write!(f, "Node data: {}, left: {}, right: {}", x, 
                        if self.left.is_null() {"null"} else {"not null"}, 
                        if self.right.is_null() {"null"} else {"not null"}, 
                    )
            }
            None => {
                write!(f, "Node data: None, left: {}, right: {}",  
                        if self.left.is_null() {"null"} else {"not null"}, 
                        if self.right.is_null() {"null"} else {"not null"}, 
                    )
            }
        }
    }
}

fn main() {
    let mut root: Node<i32> = Node::new(32);
    println!("Root before insert : {}", root);
    root.insert(42);
    println!("Root after insert: {}", root);
}

还有执行的痕迹

Root before insert : Node data: 32, left: null, right: null
Root after insert : Node data: 32, left: null, right: null

我的节点在函数插入后没有被修改。我该怎么做才能解决这个问题？

Answer 1

既然你看起来很困惑，让我们开始吧!

首先，没有理由使用裸指针。此外，我建议反对使用 Copy，因为它只是隐藏了所有权问题。最后，派生 Debug 比手动实现格式化要容易得多(并且它允许以更自动化的方式试验结构的布局)。

#[derive(Debug)]
struct Node<T> {
    data: Option<T>, // are you sure about using Option here?
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

因此，我们不使用原始指针，而是使用 Box 指针，我们将其放入 Option 中来处理 null 情况。

现在正在 build 中:

impl<T> Node<T> {
    fn new(data: T) -> Node<T> {
        Node {
            data: Some(data),
            left: None,
            right: None,
        }
    }
}

没什么特别的，让我们继续插入:

impl<T> Node<T> {
    fn insert(&mut self, data: T) {
        let current = self.data.take().expect("Cannot insert in empty node!");

        self.left = Some(Box::new(Node::new(current)));
        self.right = Some(Box::new(Node::new(data)));
    }
}

然后我们可以继续显示(使用 Debug 和 "{:?}"):

fn main() {
    let mut root: Node<i32> = Node::new(32);
    println!("Root before insert : {:?}", root);
    root.insert(42);
    println!("Root after insert: {:?}", root);
}

和it works !