實現(xiàn)二叉樹是學習一門編程語言過程中必不可少的一項訓練內容独悴，但是對于Rust而言襟铭，難度系數(shù)要遠超常規(guī)語言系洛。
我們首先以C語言的風格來定義二叉樹的節(jié)點：
struct TreeNode<T> {
value: T,
left: TreeNode<T>,
right: TreeNode<T>,
}
由于 Rust 中要求變量必須有且只有一個所有權擁有者而晒，這樣的定義是無法通過編譯的碎绎。
在TreeNode定義中已經(jīng)擁有了 left, right 的所有權螃壤，而 left 和 right 自身又是 TreeNode 結構抗果，形成了無限循環(huán)，而無限循環(huán)導致了無限的內存空間映穗。
為了避免形成無限的內存空間窖张，在Rust中，只能將節(jié)點定義引用用智能指針包裹起來蚁滋，比如宿接，可以將節(jié)點定義修改為：
use std::rc::Rc;
struct TreeNode<T> {
value: T,
left: Rc<TreeNode<T>>,
right: Rc<TreeNode<T>>,
}
但是這樣的定義仍然存在問題，在創(chuàng)建初始節(jié)點時辕录，left與right兩個變量都會空睦霎，但是這個"空"值如何怎樣賦給TreeNode呢？
在Rust中并沒有C語言中的void *可以用于表征通用指針走诞，如果為空副女，則將其賦值為NULL，在Rust中蚣旱，則需要用到Option來達到同樣的目的碑幅。
節(jié)點定義修改如下：
use std::rc::Rc;
struct TreeNode<T> {
value: T,
left: Option<Rc<TreeNode<T>>>,
right: Option<Rc<TreeNode<T>>>,
}
基于這個定義，可以實現(xiàn)一顆基本的二叉樹了:
fn main() {
let mut root = TreeNode {
value: 0,
left: None,
right: None,
};
let left_node = TreeNode {
value: 1,
left: None,
right: None,
};
let right_node = TreeNode {
value: 2,
left: None,
right: None,
};
root.left = Some(Rc::new(left_node));
root.right = Some(Rc::new(right_node));
}
至此塞绿，基本二叉樹算是實現(xiàn)了沟涨，但是仍然有問題，比如當前的定義無法修改節(jié)點中的value變量异吻。
root.left.unwrap().value = 1024;
類似的操作將會報錯裹赴，因為Rc包裹的指針屬于不可變引用，即無法修改其內部的value變量诀浪。
為了修改value變量棋返，需要進一步調整節(jié)點定義：
use std::{cell::RefCell, rc::Rc};
struct TreeNode<T> {
value: T,
left: Option<Rc<RefCell<TreeNode<T>>>>,
right: Option<Rc<RefCell<TreeNode<T>>>>,
}
借助于RefCell提供的內部可變性，可以對左右子樹內部的值進行修改雷猪。
完整的二叉樹實現(xiàn)代碼如下：
use std::cell::RefCell;
use std::rc::Rc;
use::std::process;
#[derive(Debug, Default)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
fn insert(&mut self, dir: &String, val: TreeNode) {
match dir.as_ref() {
"left" => self.left = Some(Rc::new(RefCell::new(val))),
"right" => self.right = Some(Rc::new(RefCell::new(val))),
_ => {
println!("Insert Error: Only left and right supported");
process::exit(1);
}
}
}
fn delete(&mut self, dir: &String) {
match dir.as_ref() {
"left" => self.left = None,
"right" => self.right = None,
_ => {
println!("Delete Error: Only left and right supported");
process::exit(1);
}
}
}
}
fn traverse(node: &TreeNode) {
println!("Node value: {:?}", node.val);
match node.left {
Some(ref x) => traverse(&x.borrow()),
_ => {}
}
match node.right {
Some(ref x) => traverse(&x.borrow()),
_ => {}
}
}
fn main() {
println!("rust tree test");
let mut tree = TreeNode{val: 1, ..Default::default()};
let left = TreeNode{val: 2, ..Default::default()};
tree.insert(&String::from("left"), left);
let mut right = TreeNode{val: 3, ..Default::default()};
let left1 = TreeNode{val: 4, ..Default::default()};
right.insert(&String::from("left"), left1);
let right1 = TreeNode{val: 5, ..Default::default()};
right.insert(&String::from("right"), right1);
tree.insert(&String::from("right"), right);
println!("begin tree traverse");
traverse(&tree);
tree.delete(&String::from("left"));
println!("after tree traverse");
traverse(&tree);
}
