Rust实现二叉树

实现二叉树是学习一门编程语言过程中必不可少的一项训练内容，但是对于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);
}