在Rust中实现二叉树

发布时间：2024-01-09 16:03
最后更新：2024-06-20 22:38
所属分类：
Rust

二叉树算得上是数据结构中的一种基础结构，在二叉树的基本操作中集中了大量数据结构设计中的常用操作。但是由于Rust语言特性的设计，在其他寓言中十分方便就可以实现的功能，在Rust中就需要绕一段路，二叉树的实现就是这样的一个典型例子。

这篇文章主要的目的就是记录使用Rust实现二叉树数据结构的方法，以及使用Rust实现一些经典数据结构的时候所可能使用的上的一些注意要点和技巧。

定义基本结构

要实现一个二叉树结构，首先要实现的就是二叉树的基本结构。对于二叉树基本结构的组成在本博客的文章《二叉树基础》中有很详细的叙述，所以再这篇文章中就不再赘述了。

一个二叉树的基本结构是由数据节点、左孩子节点和右孩子节点三部分组成的。其中左孩子节点和右孩子节点都是指向另一个数据节点的指针，并如此往复循环就形成了一棵二叉树。但是在许多语言中，二叉树基本结构中的左孩子节点和右孩子节点都是指针，或者说是可变的，这也是完成二叉树的一些必要操作的基础。

但是对于Rust来说，这里就是无法绕开的一个最关键的点。在Rust中，推崇的是数据不可变，尤其是结构体的字段。而获取可变引用的限制条件又非常多，所以在如何能够实现一个可自由操作的左孩子节点和右孩子节点就是一个比较关键的问题了。

例如下面这种简单粗暴的实现方法必然是不可以的。

1
2
3
4
5

struct TreeNode<T> {
  value: T,
  left: TreeNode<T>,
  right: TreeNode<T>,
}

这种定义方式再Java或者C++中是没有问题的，但是再Rust中就会收到一条编译错误，提示你使用了递归类型。这是因为递归类型在Rust的编译期是无法确定其占用内存的大小的，而且在理论上，这种类型是可以占用无穷的内存的。所以左孩子节点和右孩子节点还是要使用指针或者引用类型，一个比较简单的选择是使用Box<TreeNode<T>>类型。Box<T>类型会将其中存储的内容放置在堆上，然后返回一个指向这个堆空间的指针，所以这种实现方式是可以的。

使用Box<T>的实现就是下面的样子。

1
2
3
4
5

struct TreeNode<T> {
  value: T,
  left: Box<TreeNode<T>>,
  right: Box<TreeNode<T>>,
}

但是这里还有一个问题，一个二叉树的节点上它的左孩子节点和右孩子节点并不是始终都存在的，所以这个实现里的左孩子节点和右孩子节点还得使用Option<T>包装一下。另外一个问题就是我们在访问这个节点持有的数据的时候，是不能将其转移走的，所以还需要使用Rc<T>或者Cow<'a, T>把节点持有的值包装一下，在这个示例中，选择使用Cow<'a, T>来实现。

如果是比较关注线程安全，可以使用Arc<T>来代替Rc<T>。 
1
2
3
4
5

struct TreeNode<'a, T> {
  value: Cow<'a, T>,
  left: Option<Box<TreeNode<'a, T>>>,
  right: Option<Box<TreeNode<'a, T>>>,
}

现在再来看看这个实现，这个实现其实已经可以实现一棵二叉树的基本操作了。但是它依旧有一个问题，就是这棵树会持有它所有孩子节点的所有权，那么在完成一些需要共享数据访问的时候就会受到一些操作上的限制而不是那么方便，而且在变更孩子节点的时候是必须获取树的可变实例的。所以，这个二叉树的基本结构在定义的时候，还得利用Rust提供的结构体的内部可变性并且最好考虑树的所有节点能够支持方便的共享访问，那么现在这个二叉树的基本结构实现就会变成下面的样子。

1
2
3
4
5
6
7
8

struct TreeNode<'a, T> {
  value: Cow<'a, T>,
  left: Option<TreeNodeRef<'a, T>>,
  right: Option<TreeNodeRef<'a, T>>,
  parent: Option<TreeNodeRef<'a, T>>
}

type TreeNodeRef<'a, T> = Rc<RefCell<TreeNode<'a, T>>>;

在这个定义里，TreeNodeRef<T>的类型别名定义只是为了可以简化很长的类型书写，并没有其他额外的意图。RefCell<T>可以提供基于引用的内部可变性访问，这也是允许二叉树的两个孩子节点可以自由变换的根本。而将RefCell<T>包装在Rc<T>中，则是为了更加方便的提供孩子节点的共享使用。Rc<T>最终使二叉树的循环数据结构能够完成创建。而且使用Rc<RefCell<T>>做为孩子节点类型的另一个好处是孩子节点的生命期可以超过根节点的生命期。

示例中记录parent节点是非常有用的，很多遍历和操作都需要用到访问其父级节点功能。一个节点的父级节点可以在插入节点的时候设置。

关于Rc<RefCell<T>>的操作技巧

如果只是访问本层节点的内容，Rc<RefCell<T>>的结构基本上不会造成任何困扰，因为Rc<T>和RefCell<T>都实现了Deref特征，所以只需要使用*解引用操作符就可以利用Rust的智能解引用操作直接获取到T的内容。

其实对于所有实现了Deref特征的类型，都可以直接使用*解引用操作符来处理和访问。或者可以换句话说，任何实现了Deref特征的类型，都是指针，例如常见的Rc、Arc、Cow、Box、Ref、RefCell、MutexGuard等。所有实现了Deref特征的类型，其实例都可以直接访问、调用被包装类型的成员以及成员方法。

但如果需要使用可变访问的话，那么就不太一样了。返回一个可变引用需要实现BorrowMut特征，但是很不巧的，Rc<T>是没有实现这个特征的，所以就如果想要获取&mut T，就去必须先对Rc<RefCell<T>>做一次解引用，获取到RefCell<T>。但是RefCell<T>也没有实现BorrowMut特征，只是实现了一个borrow_mut()方法，所以可以直接使用这个方法来获取到一个可变的结构。RefCell<T>的borrow_mut()方法获取到的可变结构是RefMut<T>，这个类型实现了DerefMut，所以就可以使用它来获取&mut T了，也可以用来直接调用T中需要&mut self的方法。

忍了吧，Rust就是这么绕。

所以在后面的示例中，想要从Rc<RefCell<T>>类型中获取到&mut T时，就需要首先获取到&RefCell<T>，这一步需要对Rc<T>解引用，然后再将其转换为一个引用，所以操作是以下样子。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 假设node是一个保存了内容的节点。
let node: Rc<RefCell<TreeNode<i32>>>;

// 这一步是解开Rc<T>，获取到&RefCell<T>。
let ref_node: &RefCell<TreeNode<i32>> = &*node;

// 使用*ref_node是用来解开&RefCell<T>前面的引用。
// 因为RefMut实现了DerefMut特征，所以现在mut mut_node就可以访问TreeNode<T>中需要&mut self参数的成员方法了。
let mut mut_node: RefMut<TreeNode<i32>> = (*ref_node).borrow_mut();

// 其实最简单的使用方法可以调过ref_node，*node可以直接获取到RefCell<T>。
let mut mut_node: RefMut<TreeNode<i32>> = (*node).borrow_mut();

如果想利用RefCell<T>的内部可变性来修改Rc<RefCell<T>>内部实际指向的值，那么就可以使用上面的方法先解引用Rc<T>，再获取&RefCell<T>或者RefMut<T>来操作。只是需要注意的是，不需要Rc<T>是可变的，也不需要&RefCell<T>是可变的。

二叉树基本操作

二叉树的基本操作主要就是二叉树节点的插入、删除、变换以及二叉树节点的旋转、遍历等。所有更高级的二叉树操作都是由这几种基本操作组合而来的。

但是在实现所有二叉树的基本操作之前，还是先需要完成二叉树节点的创建操作。

1
2
3
4
5
6
7
8
9

impl<T> TreeNode<T> {
  pub fn raw_new(value: T) -> Self {
    TreeNode { value: Cow::Owned(value), left: None, right: None, parent: None }
  }

  pub fn new(value: T) -> TreeNodeRef<T> {
    Rc::new(RefCell::new(Self::raw_new(value)))
  }
}

访问节点

对于节点的访问，可以编写几个getter方法返回节点的引用。

注意不能直接返回节点值或者孩子节点本身，节点值和孩子节点的所有权不能移交。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl<'a, T> TreeNode<'a, T> {
  pub fn value(&self) -> Rc<T> {
    // Rc::from()方法是需要转移参数的所有权的，所以需要使用.clone()。
    Rc::from(self.value.as_ref().clone())
  }

  pub fn left(&self) -> Option<TreeNodeRef<'a, T>> {
    match self.left {
      Some(ref left) => Some(Rc::clone(left)),
      None => None
    }
  }
}
对于Cow<T>来说，使用&获取的引用是&Cow<T>，而使用AsRef特征的.as_ref()方法，获取到的是&T。大多数泛型类型中&和.as_ref()的操作都有这样的区别，使用时需要注意。

以上示例中，右孩子节点的获取也是一样的。孩子节点的获取原理是利用Rc<T>的引用，将孩子节点的引用复制一份，但是在复制之前需要首先对孩子节点可能存在的None值进行重新的包装。

插入节点

插入节点的操作主要是需要判断所插入的孩子节点位置是否是空的，如果孩子节点是空的，那么只需要直接挂载上去即可，如果已经存在了孩子节点，那么就需要替换这个节点。

以下以操作左孩子节点为例。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl<'a, T> TreeNode<'a, T> {
  pub fn attach_left_node(&mut self, value: T) -> () {
    match self.left {
      Some(ref mut left) => {
        left.replace(Self::raw_new(value));
      },
      None => {
        self.left = Self::new(value);
      }
    }
  }
}

删除节点

删除节点就非常容易了，原则上就是将需要删除的孩子节点设置为None，然后返回孩子节点的所有权。

1
2
3
4
5
6
7

impl<'a, T> TreeNode<'a, T> {
  pub fn remove_left_child(&mut self) -> Option<TreeNodeRef<T>> {
    // .take()会返回当前Option<T>中的内容，并将当前的Opion<T>类型值设置为Default::default()，
    // 也就是None。
    self.left.take()
  }
}

节点遍历

二叉树的遍历有前序、中序和后序三种，这里只使用中序遍历做示例。中序遍历的节点访问顺序是先访问左孩子节点，再访问根节点，然后再访问右孩子节点。节点的遍历一般都会有多种实现的方式，常见的有递归、递推、队列等，这里拣选递归方式来实现。

递归遍历方法是所有方法中代码量比较少的，也是实现比较简单的，但是递归方法消耗的系统资源会稍微多一些。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl<'a, T> TreeNode<'a, T> {
  pub fn traverse_inorder(&self) -> Vec<Rc<T>> {
    let mut result = Vec::new();
    if let Some(ref left) = self.left {
      result.extend((**left).borrow().traverse_inorder());
    }
    result.push(self.value());
    if let Some(ref right) = self.right {
      result.extend((**right).borrow().traverse_inorder());
    }
    result
  }
}

在这个示例中由于self.left是一个Option<Rc<RefCell<T>>>类型，所以需要使用if let Some()对其进行解构，解构赋值中的ref left则是将解构出的Rc<RefCell<T>>变换为&Rc<RefCell<T>>，可以保证解构判断语句不会转移self.left的所有权。

小结

其实从上面这些复杂的解引用操作和包装类型操作代码中可以看出来，这个二叉树的操作实际上并不适合构建成一个结构体的成员方法，反而使用函数式操作会更加高效一些，以下集中一套集合了上述功能的函数式实现。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

use std::{borrow::Cow, cell::RefCell, rc::Rc};

/// 二叉树节点结构，其中生命期标记是Cow<T>类型需要，Cow<T>的生命期只需要保证跟节点生命期一致即可。
#[derive(Debug, Clone)]
pub struct TreeNode<'a, T>
where
  T: Clone,
{
  value: Cow<'a, T>,
  left: Option<TreeNodeRef<'a, T>>,
  right: Option<TreeNodeRef<'a, T>>,
  parent: Option<TreeNodeRef<'a, T>>,
}

/// 用于表示可变节点的共享引用。
type TreeNodeRef<'a, T> = Rc<RefCell<TreeNode<'a, T>>>;

impl<'a, T> TreeNode<'a, T>
where
  T: Clone,
{
  /// 用来获取节点中保存的值，值采用Rc<T>包装以方便共享访问。
  pub fn value(&self) -> Rc<T> {
    Rc::from(self.value.as_ref().clone())
  }

  /// 用来获取可能存在的左孩子节点。
  pub fn left(&self) -> Option<TreeNodeRef<'a, T>> {
    match self.left {
      Some(ref left) => Some(Rc::clone(left)),
      None => None,
    }
  }

  /// 用来获取可能存在的右孩子节点。
  pub fn right(&self) -> Option<TreeNodeRef<'a, T>> {
    match self.right {
      Some(ref right) => Some(Rc::clone(right)),
      None => None,
    }
  }
}

/// 用于产生一个顶级节点，模块私有方法，不建议直接使用。
fn raw<'a, T>(value: T) -> TreeNode<'a, T>
where
  T: Clone,
{
  TreeNode {
    value: Cow::Owned(value),
    left: None,
    right: None,
    parent: None,
  }
}

/// 用于创建一个拥有父级节点的节点，模块私有方法，不建议直接使用。
fn raw_with_parent<'a, T>(parent: &TreeNodeRef<'a, T>, value: T) -> TreeNode<'a, T>
where
  T: Clone,
{
  TreeNode {
    value: Cow::Owned(value),
    left: None,
    right: None,
    parent: Some(Rc::clone(parent)),
  }
}

/// 创建一个二叉树的顶级节点。
pub fn new<'a, T>(value: T) -> TreeNodeRef<'a, T>
where
  T: Clone,
{
  Rc::new(RefCell::new(raw(value)))
}

/// 向指定节点附加左孩子节点。
pub fn attach_left_child<T>(parent: &TreeNodeRef<'_, T>, value: T)
where
  T: Clone,
{
  if let Some(ref left) = (*parent).borrow().left() {
    (*left).replace(raw_with_parent(left, value));
    return;
  }
  (*parent).borrow_mut().left = Some(new(value));
}

/// 向指定节点附加右孩子节点。
pub fn attach_right_child<T>(parent: &TreeNodeRef<'_, T>, value: T)
where
  T: Clone,
{
  if let Some(ref right) = (*parent).borrow().right() {
    (*right).replace(raw_with_parent(right, value));
    return;
  }
  (*parent).borrow_mut().right = Some(new(value));
}

/// 移除指定节点的左孩子节点。
pub fn remove_left_child<'a, T>(parent: &TreeNodeRef<'a, T>) -> Option<TreeNodeRef<'a, T>>
where
  T: Clone,
{
  (*parent).borrow_mut().left.take()
}

/// 移除指定节点的右孩子节点。
pub fn remove_right_child<'a, T>(parent: &TreeNodeRef<'a, T>) -> Option<TreeNodeRef<'a, T>>
where
  T: Clone,
{
  (*parent).borrow_mut().right.take()
}

/// 获取指定节点的值，以共享引用的方式包装返回。
pub fn value<'a, T>(node: &TreeNodeRef<'a, T>) -> Rc<T>
where
  T: Clone,
{
  (*node).borrow().value()
}

/// 获取指定节点可能存在的左孩子节点。
pub fn left<'a, T>(node: &TreeNodeRef<'a, T>) -> Option<TreeNodeRef<'a, T>>
where
  T: Clone,
{
  (*node).borrow().left()
}

/// 获取指定节点可能存在的右孩子节点。
pub fn right<'a, T>(node: &TreeNodeRef<'a, T>) -> Option<TreeNodeRef<'a, T>>
where
  T: Clone,
{
  (*node).borrow().right()
}

/// 以指定节点为顶级节点，中序遍历二叉树，形成一个各个节点值组成的列表。
pub fn traverse_indorder<'a, T>(node: &TreeNodeRef<'a, T>) -> Vec<Rc<T>>
where
  T: Clone,
{
  let mut result = Vec::new();

  if let Some(ref left) = (*node).borrow().left() {
    result.extend(traverse_indorder(left));
  }
  result.push(value(node));
  if let Some(ref right) = (*node).borrow().right() {
    result.extend(traverse_indorder(right));
  }

  result
}

使用这个实现操作二叉树就比较方便了，例如这个文件被封装为了模块bt.rs，二叉树的使用就看起来很清爽了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

mod bt;

fn main() {
  // 创建一个顶级节点。
  let root = bt::new(1);
  // 向顶级节点附加一个左孩子节点。
  bt::attach_left_child(&root, 2);
  // 向顶级节点附加一个右孩子节点。
  bt::attach_right_child(&root, 3);
  // 向顶级节点的左孩子节点附加一个左孩子节点。
  bt::attach_left_child(&bt::left(&root).unwrap(), 4);
  // 向顶级节点的右孩子节点附加一个左孩子节点。
  bt::attach_left_child(&bt::right(&root).unwrap(), 5);
  // 向顶级节点的右孩子节点附加一个右孩子节点。
  bt::attach_right_child(&bt::right(&root).unwrap(), 6);

  println!("{:?}", bt::traverse_indorder(&root));
}
索引标签
Rust
算法设计
数据结构
二叉树