pointers - 创建可变二叉树时键入名称 T undefined

Question

我是 Rust 的新手，为了练习，我正在构建一个简单的通用二叉树。这就是我用 C++ 创建一个的方式

template<typename T>
struct Node
{
    T data;
    Node<T>* parent;
    Node<T>* left;
    Node<T>* right;
};

template<typename T>
struct Bintree
{
    Node<T>* root;  
};

但是 Rust 中的相同(大概)代码似乎不起作用:

use std::ptr;

struct Node<T> {
    data: T,
    left: &Node<T>,
    right: &Node<T>,
    parent: &Node<T>,
}

struct Tree<T> {
    root: &Node<T>,
}

impl Tree<T> {
    pub fn new() -> Tree<T> {
        Tree { root: ptr::null() }
    }

    pub fn insert(&self, value: T) {
        if root.is_null() {
            self.root = Node {
                data: value,
                left: ptr::null(),
                right: ptr::null(),
                parent: ptr::null(),
            };
        }
    }
}

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

这里是错误:

error[E0412]: type name `T` is undefined or not in scope
  --> src/main.rs:14:15
   |
14 |     impl Tree<T> {
   |               ^ undefined or not in scope
   |
   = help: no candidates by the name of `T` found in your project; maybe you misspelled the name or forgot to import an external crate?

error[E0412]: type name `T` is undefined or not in scope
  --> src/main.rs:15:30
   |
15 |         pub fn new() -> Tree<T> {
   |                              ^ undefined or not in scope
   |
   = help: no candidates by the name of `T` found in your project; maybe you misspelled the name or forgot to import an external crate?

error[E0412]: type name `T` is undefined or not in scope
  --> src/main.rs:19:37
   |
19 |         pub fn insert(&self, value: T) {
   |                                     ^ undefined or not in scope
   |
   = help: no candidates by the name of `T` found in your project; maybe you misspelled the name or forgot to import an external crate?

error[E0425]: unresolved name `root`. Did you mean `self.root`?
  --> src/main.rs:20:16
   |
20 |             if root.is_null() {
   |                ^^^^

error[E0106]: missing lifetime specifier
 --> src/main.rs:5:15
  |
5 |         left: &Node<T>,
  |               ^ expected lifetime parameter

error[E0106]: missing lifetime specifier
 --> src/main.rs:6:16
  |
6 |         right: &Node<T>,
  |                ^ expected lifetime parameter

error[E0106]: missing lifetime specifier
 --> src/main.rs:7:17
  |
7 |         parent: &Node<T>,
  |                 ^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/main.rs:11:15
   |
11 |         root: &Node<T>,
   |               ^ expected lifetime parameter

我真的不明白这有什么问题。我真的不明白 Rust 的指针是如何工作的。

Answer 1

在这种情况下，你有一个基本的语法错误，应该是

impl<T> Tree<T>

从那里，您会看到您需要 if self.root.is_null()。

然后，数据结构需要生命周期说明符，因为您正在使用引用。使用最直接的语法最终会导致

error[E0309]: the parameter type `T` may not live long enough

所以你在那里使用 T: 'a...你最终得到:

use std::ptr;

struct Node<'a, T: 'a> {
    data: T,
    left: &'a Node<'a, T>,
    right: &'a Node<'a, T>,
    parent: &'a Node<'a, T>,
}

struct Tree<'a, T: 'a> {
    root: &'a Node<'a, T>,
}

impl<'a, T> Tree<'a, T> {
    pub fn new() -> Tree<'a, T> {
        Tree { root: ptr::null() }
    }

    pub fn insert(&self, value: T) {
        if self.root.is_null() {
            self.root = Node {
                data: value,
                left: ptr::null(),
                right: ptr::null(),
                parent: ptr::null(),
            };
        }
    }
}

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

这给出了另一个错误

21 |             root: ptr::null(),
   |                   ^^^^^^^^^^^ expected reference, found *-ptr

这是因为 ptr::null() 返回原始指针，但您已声明您的数据结构使用引用。

好吧，我就到此为止了。让我们回到您的问题...

I am new to Rust, and for an exercise, I am building a simple generic binary tree.

我建议您应该考虑其他 而不是编写数据结构。它们在 Rust 中并不简单。如果您仍然想采用这种方法，我可以推荐 Too Many Lists .