二叉树

Rust 简介 实际上自己接触 Rust 的时间还是很有限的，这里也不会对 Rust 进行长篇大论地介绍，简单来说，Rust 是一个性能和 c++ 相近的系统级编程语言，同时，由于其所有权与变量生命周期等机制的设计，使其相对于 c++ 来说拥有内存安全的优势，几乎不会出现诸如悬垂指针、数组越界、段错误等问题，在微软、百度、字节跳动等公司均有所使用。 关于 Rust 的特性以及未来，知乎这个问题中的一些高赞回答以及相关的评论，非常值得一看。 本文会以二叉树这样一个具体的例子出发，来对 Rust 的一部分知识内容进行学习。 实现二叉树数据结构 定义结构 之前在 Javascript 等语言中，我们只要对对象有所了解，实现一个二叉树的数据结构是非常简单的事情，而在 Rust 中，可能对于新手来说仅仅是实现基本的数据结构就是一个比较脑壳疼的事情。 我们一般会写出类似这样的代码： struct Tree { value: i32, left: Tree, // 直接使用 Tree 是不行的 right: Tree } 自然不会通过 Rust 的编译检查，会报错例如：recursive type has infinite size，不过其同时给我们提供了解决方案，这里我们使用 Box<T> 指针。 另外，考虑到二叉树的左右子树可能为空，所以这里我们还需要增加一个 Option。 最终我们的二叉树数据结构定义如下： #[derive(Debug, Default)] struct Tree { value: i32, left: Option<Box<Tree>>, right: Option<Box<Tree>> } 实现基本的方法 这里我们实现一些二叉树的基本的方法，作为上述结构体的方法，我们将实现以下方法： 获取二叉树节点的值（其实也可以没有这个方法）。 修改二叉树节点的值。 设置子树。 删除子树。 这里除了第一个，其余我们都需要传递 self 的可变引用，我们的实现如下： ...