Skip to content

Latest commit

 

History

History
332 lines (280 loc) · 12.2 KB

5.simple-binary-tree.md

File metadata and controls

332 lines (280 loc) · 12.2 KB
Raw

Rust 学习之基于 RefCell 的简单二叉树

最近，在力扣平台刷题时，无意中刷到了一个关于二叉树的题目：二叉树的最小深度，打算使用 Rust 实现它。

不得不承认，我的思路有些死板。当我将该题的 project 新建好后，把预备代码准备完成，我是准备先进行数据的组装，因为求二叉树的最小深度的前提是你得有一棵”树“，于是乎，参照“力扣”给出的节点数据结构，我开始实现”树“的加载。

// 力扣给出的节点结构
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
use std::cell::RefCell;
use std::rc::Rc;

struct Solution {}
impl Solution {
    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        
    }
}

在实现 min_depth 之前，我打算先实现树的生成。

可以看出，实际上存储时的节点结构是 Option<Rc<RefCell<TreeNode>>>。其中的 Rc 和 RefCell 是 Rust 中的智能指针。

Rc 是引用计数指针，通过 clone 的方式可以被多个变量拥有对应的引用所有权，如此导致的是存储于 Rc 指针中的值是不可变的。如果我们要将值存储到其中，如何做到呢？答案就是使用内部可变的 RefCell 指针。

准备工作

在开始写代码之前，我们先用 cargo 创建一个项目：

// 假设我们的项目目录名称是 _111_minimum-depth-of-binary-tree
cargo new --lib _111_minimum-depth-of-binary-tree
cd _111_minimum-depth-of-binary-tree

此时 cargo 为你的项目生成了如下的目录结构：

├── Cargo.lock
├── Cargo.toml
└── src
    └── lib.rs

由于只是个比较小的代码库，因此具体的代码实现可以直接写在 lib.rs 文件中。

二叉树的生成

上面提到的“树”的加载，其实就是指生成二叉树的过程。简单起见，我们以力扣中给定的示例数据为例，使用数字作为二叉树的值。给定一个数组作为数节点的值：[3, 9, 20, 15, 7]，生成一个树前，先明确以下 2 点：

  • 1.确定一个根节点，如果为空，则实例化一个节点作为树的根节点 root
  • 2.后续所有节点的插入，都以根节点 root 作为起始入口

生成一棵树，我们先假设只有一个节点，入参是 [3]。我们可以通过 TreeNode 的 new 函数实例化一个节点：

let node = TreeNode::new(3);
let root_op: Option<Rc<RefCell<TreeNode>>> = Some(Rc::new(RefCell::new(node)));

这只是简单的将一个值包装成根节点，实际情况下，我们会将一批数据加入到树中，从而生成“茂盛”的树状结构。为此，我们一步一步来，先声明一个 TreeTrait trait，其中我们会声明一些抽象方法，用于树的初始化、节点的新增、删除等：

trait TreeTrait {
    // 实例化一棵树
    fn new(value: i32) -> Self;

    // 插入
    fn insert(self: &mut Self, value: i32) -> Result<i32, String>;

    // 搜索
    fn search(self: &mut Self, value: i32) -> Option<Rc<RefCell<TreeNode>>>;
    
    // 删除
    fn delete(self: &mut Self, value: i32) -> Result<i32, String>;
}

然后，我们需要声明一个树的结构 Tree，并为它实现 TreeTrait trait：

#[derive(Debug)]
struct Tree {
    root: TreeNode,
    length: u32,
}

impl TreeTrait for Tree {
    fn new(self: &mut Tree, value: i32) -> Option<Rc<RefCell<TreeNode>>> {
        todo!()
    }
    fn insert(self: &mut Tree, value: i32) -> Option<Rc<RefCell<TreeNode>>> {
        todo!()
    }
    fn search(self: &mut Self, value: i32) -> Option<Rc<RefCell<TreeNode>>> {
        todo!()
    }
    fn delete(self: &mut Self, value: i32) -> Result<i32, String> {
        todo!()
    }
}

辅助方法

在开始执之前，需要做些准备一些东西 ——— 辅助方法。由于节点的类型是 Option<Rc<RefCell<TreeNode>>>，再加上 Rust 语法的所有权、借用等问题，会导致取数值比较、参数传递时不是很方便，因此我们编写一些方法，简化开发过程中的调用。

获取 Rc 引用

智能指针 Rc，可以认为是对某个数据的引用，我们可以通过 Rc::clone() 的方式复制多份引用，赋值给多个变量，这样可以实现多个变量都指向同一个“树节点”，因为获取引用的调用会比较繁琐，因此我们将其封装为方法 get_rc()，放在 impl Tree 块中，其实现如下：

impl Tree {
    fn get_rc(rc_rc: &Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(ref new_node_rf) = *rc_rc {
            let new_rc = Rc::clone(new_node_rf);
            Some(new_rc)
        } else {
            None
        }
    }
}

通过节点获取对应的值

还好，因为此次为了简化实现过程，节点存储的的数据是简单的 i32 类型，它是可 Copy 的，我们通过一个函数用于获取类型为 Option<Rc<RefCell<TreeNode>>> 的变量的值，并将其放在 impl Tree 块中：

impl Tree {
    fn get_val(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let rc = Tree::get_rc(node);
        return rc.unwrap().borrow().val;
    }
}

编写测试用例测试一下它的功能：

#[test]
fn test_get_val() {
    let node = Some(Rc::new(RefCell::new(TreeNode::new(3))));
    assert_eq!(3, node.unwrap().borrow().val);
}

树的实例化

我们会为 Tree 类型实现构造方法 new：

// 返回的是包装后的根节点
fn new(value: i32) -> Tree {
    let node = TreeNode::new(value);
    Tree {
        root: Some(Rc::new(RefCell::new(node))),
        length: 1,
    }
}

我们可以写个测试用例，通过集成测试来对功能代码文件中的函数进行测试，主要是看实例化的树的节点和数量是否和期望的一致：

#[test]
fn test_tree_new() {
    let tree = Tree::new(3);
    let v1 = tree.root.unwrap().borrow().val;

    assert_eq!(3, v1);
    assert_eq!(1, tree.length);
}

新增节点

实例化一个只带有根节点的树后，我们还需要将更多的数据加入到树中，因此我们实现 Tree 的 insert 方法。需要注意的是，这里我们还是遵循二叉树的以下性质：二叉树的左节点小于其父节点的值，右子节点值大于其父节点。insert 实现如下：

// 节点的新增
fn insert(self: &mut Tree, value: i32) -> Result<i32, String> {
    let root = Tree::get_rc(&self.root);
    let mut current_node = root;
    // 声明一个临时变量，用于赋值给 current_node
    let mut current_node_tmp: Option<Rc<RefCell<TreeNode>>>;
    // 使用新的值实例化新的节点
    let new_node = Some(Rc::new(RefCell::new(TreeNode::new(value))));
    loop {
        match current_node {
            Some(ref node_rf) => {
                let mut node_tr = node_rf.borrow_mut();
                let new_node_val = if let Some(ref new_node_rf) = new_node {
                    let new_node_tr = (&new_node_rf).borrow();
                    new_node_tr.val
                } else {
                    return Err("the TreeNode's value is invalid...".to_string());
                };
                if new_node_val > node_tr.val {
                    if node_tr.right == None {
                        node_tr.right = new_node;
                        self.length += 1;
                        return Ok(1);
                    } else {
                        // 获取 right 值的 rc 引用
                        current_node_tmp = Tree::get_rc(&(node_tr.right));
                    }
                } else {
                    if node_tr.left == None {
                        node_tr.left = new_node;
                        self.length += 1;
                        return Ok(1);
                    } else {
                        // 获取 right 值的 rc 引用
                        current_node_tmp = Tree::get_rc(&(node_tr.left));
                    }
                }
            }
            _ => {
                return Err("insert error".to_string());
            },
        }
        current_node = current_node_tmp;
    }
}

当插入成功时，返回正确的 code 代码 1，如果异常，则返回 String 类型的异常信息。测试用例如下：

#[test]
fn test_insert() {
    let mut tree = Tree::new(3);
    if let Ok(code) = tree.insert(4) {
        assert_eq!(1, code);
    } else {
        panic!("insert error")
    }
    let arr = vec![9,6,10,11,5];
    for val in arr {
        match tree.insert(val) {
            Ok(code) => assert_eq!(1, code),
            Err(msg) => {
                println!("{:?}", msg);
                assert!(false);
            }
        }
    }
    // 3,4,9,6,10,11,5
    assert_eq!(7, tree.length);
}

搜索节点

二叉树的典型场景就是查询，在这里，就是给定一个 i32 类型的值，我们从已知的二叉树中查询该值是否存在。实现如下：

fn search(self: &mut Self, value: i32) -> Option<Rc<RefCell<TreeNode>>> {
    let mut current_node = Tree::get_rc(&self.root);
    let needle_node = Some(Rc::new(RefCell::new(TreeNode::new(value))));
    let needle_val = Tree::get_val(&needle_node);
    loop {
        let current_val = Tree::get_val(&current_node);
        if current_val == needle_val {
            return current_node;
        } else {
            // 比它小，则从左子树查找，否则从右子树查找
            if needle_val > current_val {
                current_node = Tree::get_rc(&current_node.unwrap().borrow().right);
            } else {
                current_node = Tree::get_rc(&current_node.unwrap().borrow().left);
            }
        }
        if current_node == None {
            break;
        }
    }
    return None;
}

利用 Rust 标准库中的 Option 枚举，我们可以将该方法设计为，当查询到的时候，返回 Option 包装的节点指针；未查询到时，则返回 None。用测试用例测试它：

#[test]
fn test_search() {
    let mut tree = Tree::new(3);
    let arr = vec![9,6,10,11,5];
    for val in arr {
        match tree.insert(val) {
            Ok(code) => assert_eq!(1, code),
            Err(msg) => {
                println!("{:?}", msg);
                assert!(false);
            }
        }
    }
    let needle = tree.search(10);
    assert_eq!(10, needle.unwrap().borrow().val);
}

删除节点

emmmm，作为练习，删除节点的实现，就交给读者们自己去实现（我不会告诉你们，其实是我不会写...）。

conclusion

至此，基于 RefCell 的二叉树就基本实现了。作为 Rust 新手，我只是用一些简单的方式来实践已知的知识，无论是巩固历史知识，还是对练习 Rust 都是有很多帮助。

诚然，本文描述的是非常简单的场景，实际使用是，我们的数据不可能只是简单的 i32，而可能是字符串、结构体或者一些其他类型数据。而在二叉树存储复杂数据的场景中，我们还需要手动实现数据的判等、复制等操作。在后续的笔记中，我们会慢慢讲解到。

文中提到的所有代码都能在 GitHub 上找到。此外，如果文章有不当之处，或者想和我交流，欢迎提 issue 和我联系~

reference