二叉树
使用Option<Box<T>>
实现。Box是智能指针,分配在堆上,专门用于这种“无限”大小的数据类型。LeetCode上采用Option<Rc<RefCell<T>>>
实现,非常臃肿。。
#[derive(PartialEq)]
enum TreeDir{
LEFT, RIGHT
}
#[derive(Default)]
struct TreeNode{
val:i32,
left:Option<Box<TreeNode>>, //Box是智能指针,分配在堆上,专门用于这种“无限”大小的数据类型
right:Option<Box<TreeNode>>,
}
impl TreeNode {
pub fn new () -> Self{ //新建树
Self { val: 0, left: None, right: None }
}
pub fn new_val (num:i32) -> Self{ //新建树并设定值
Self { val: num, left: None, right: None }
}
pub fn insert_tree (&mut self, node:TreeNode, dir:TreeDir){ //插入树
if dir == TreeDir::LEFT{
self.left = Some(Box::new(node));
}else{
self.right = Some(Box::new(node));
}
}
pub fn remove_tree (&mut self, dir:TreeDir){
match dir{
//直接设为None即可,智能指针会自动释放空间。
TreeDir::LEFT => {self.left = None;},
TreeDir::RIGHT => {self.right = None;},
}
}
pub fn traverse_preorder(&self){ //前序遍历
println!("{}", self.val);
if let Some(ref left) = self.left {
left.traverse_preorder();
}
if let Some(ref right) = self.right {
right.traverse_preorder();
}
}
}
fn main() {
let mut t = TreeNode::new();
t.insert_tree(TreeNode::new_val(10), TreeDir::LEFT);
if let Some(ref mut t_left) = t.left{
t_left.insert_tree(TreeNode::new_val(20), TreeDir::RIGHT);
}
t.traverse_preorder();
let p = t.left.as_ref().unwrap().right.as_ref().unwrap();
println!("释放前:{}", p.val);
t.remove_tree(TreeDir::LEFT);
t.insert_tree(TreeNode::new_val(12), TreeDir::RIGHT);
// println!("释放后:{}", p.val); //无法输出 p.val, 编译器报错
}
字典树
使用HashMap<char, TrieNode>
实现。
use std::collections::HashMap;
#[derive(Default, Debug)]
struct TrieNode {
is_end_of_word: bool,
children: HashMap<char, TrieNode>,
}
#[derive(Default, Debug)]
pub struct Trie {
root: TrieNode,
}
impl Trie {
pub fn new() -> Self {
Trie {
root: TrieNode::default(),
}
}
pub fn insert(&mut self, word: &str) {
let mut current_node = &mut self.root;
for c in word.chars() {
current_node = current_node.children.entry(c).or_default();
}
current_node.is_end_of_word = true;
}
pub fn contains(&self, word: &str) -> bool {
let mut current_node = &self.root;
for c in word.chars() {
match current_node.children.get(&c) {
Some(node) => current_node = node,
None => return false,
}
}
current_node.is_end_of_word
}
}
fn main() {
let mut trie = Trie::new();
trie.insert("hello");
trie.insert("hi");
trie.insert("hey");
trie.insert("world");
//println!("{trie:#?}");
println!("hiiii? {}", trie.contains("hiiii"));
}
如果把开头几行换成这个更快:
use std::collections::HashMap;
use fxhash::FxBuildHasher;
type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;
#[derive(Default)]
struct TrieNode {
is_end_of_word: bool,
children: FxHashMap<char, TrieNode>,
}
因为它采用了更简单的哈希函数。