实现二叉树是学习一门编程语言过程中必不可少的一项训练内容，但是对于Rust而言，难度系数要远超常规语言。
我们首先以C语言的风格来定义二叉树的节点：
struct TreeNode<T> {
value: T,
left: TreeNode<T>,
right: TreeNode<T>,
}
由于 Rust 中要求变量必须有且只有一个所有权拥有者，这样的定义是无法通过编译的。
在TreeNode定义中已经拥有了 left, right 的所有权，而 left 和 right 自身又是 TreeNode 结构，形成了无限循环，而无限循环导致了无限的内存空间。
为了避免形成无限的内存空间，在Rust中，只能将节点定义引用用智能指针包裹起来，比如，可以将节点定义修改为：
use std::rc::Rc;
struct TreeNode<T> {
value: T,
left: Rc<TreeNode<T>>,
right: Rc<TreeNode<T>>,
}
但是这样的定义仍然存在问题，在创建初始节点时，left与right两个变量都会空，但是这个"空"值如何怎样赋给TreeNode呢？
在Rust中并没有C语言中的void *可以用于表征通用指针，如果为空，则将其赋值为NULL，在Rust中，则需要用到Option来达到同样的目的。
节点定义修改如下：
use std::rc::Rc;
struct TreeNode<T> {
value: T,
left: Option<Rc<TreeNode<T>>>,
right: Option<Rc<TreeNode<T>>>,
}
基于这个定义，可以实现一颗基本的二叉树了:
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));
}
至此，基本二叉树算是实现了，但是仍然有问题，比如当前的定义无法修改节点中的value变量。
root.left.unwrap().value = 1024;
类似的操作将会报错，因为Rc包裹的指针属于不可变引用，即无法修改其内部的value变量。
为了修改value变量，需要进一步调整节点定义：
use std::{cell::RefCell, rc::Rc};
struct TreeNode<T> {
value: T,
left: Option<Rc<RefCell<TreeNode<T>>>>,
right: Option<Rc<RefCell<TreeNode<T>>>>,
}
借助于RefCell提供的内部可变性，可以对左右子树内部的值进行修改。
完整的二叉树实现代码如下：
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);
}
