タイプ名Tは変更可能なバイナリツリーを作成するときに未定義です

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; 
}; 

に1を作成したい方法です。しかしラストで同じ（っぽい）のコードは動作していないよう：

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 

私は何が間違っているのか分かりません。私は本当にルストのポインタの仕組みを理解していない。この場合

Answer 1

、あなたは基本的な構文エラーを持っている、それはあなたがif self.root.is_null()を必要とすることがわかります、そこから

impl<T> Tree<T> 

でなければなりません。

次に、参照を使用しているため、データ構造にライフタイム指定子が必要です。その構文の最も簡単には最終的にあなたがそこにT: 'aを使用して...そしてあなたがで終わる

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

につながる使い方：

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をお勧めします。

Answer 2

私は最終的にそれを行う方法を見つけました。ノード構造体にはstd::ptrの代わりにstd::optionalを使用しました。これは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(&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); 
}