Блог

Я новичок в 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: amp;Node<T>,
    right: amp;Node<T>,
    parent: amp;Node<T>,
}

struct Tree<T> {
    root: amp;Node<T>,
}

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

    pub fn insert(amp;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(amp;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: amp;Node<T>,
  |               ^ expected lifetime parameter

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

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

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

Я действительно не понимаю, что в этом плохого. Я действительно не понимаю, как работают указатели Rust.

В этом случае у вас основная синтаксическая ошибка, она должна быть

 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: amp;'a Node<'a, T>,
    right: amp;'a Node<'a, T>,
    parent: amp;'a Node<'a, T>,
}

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

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

    pub fn insert(amp;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() возвращает необработанные указатели, но вы заявили, что ваша структура данных использует ссылки.

Хорошо, это все, что я собираюсь сделать. Давайте вернемся к вашему вопросу…

Я новичок в Rust, и для упражнения я создаю простое универсальное двоичное дерево.

Я бы посоветовал вам рассмотреть что-то иное, чем написание структуры данных. В Rust они не простые. Если вы все еще хотите использовать этот подход, могу ли я порекомендовать слишком много списков.

Наконец-то я нашел способ сделать это. Я использовал std::optional вместо std::ptr для структуры узла, и это работает как указатель C.

 struct Node<T> {
    id: u32,
    data: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
    parent: Option<Box<Node<T>>>,
}

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

impl<T> Node<T> {
    pub fn new(value: Option<T>,
               left: Option<Box<Node<T>>>,
               right: Option<Box<Node<T>>>,
               parent: Option<Box<Node<T>>>)
               -> Node<T> {
        Node {
            data: value.unwrap(),
            left: left,
            right: right,
            parent: parent,
        }
    }
}

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

    pub fn insert(amp;mut self, value: T) {
        match self.root {
            Some(ref n) => {
                println!("Root is not empty");
            }
            None => {
                println!("Root is empty");
                self.root = Some(Node::new(Some(value), None, None, None));
            }
        }
    }
}

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

    let mut tree: Tree<i32> = Tree::new();
    tree.insert(42);
}