- 二叉树
- 前中后序遍历
- 最大宽度
- 判断完全、平衡、搜索、满二叉树
- Rust的HashMap特性
反序列化
前序遍历的字符串为:”1_2_4_N_N_5_N_N_3_6_N_N_7_N_N”, 创建一棵二叉树
type TreeLink = Option<Rc<RefCell<TreeNode>>>;
fn create_bitree_cursive(node_values: &mut VecDeque<&str>) -> TreeLink {
let val = node_values.pop_front().unwrap();
if val == "N" {
return None;
}
let mut node: TreeNode = TreeNode::new(val.parse::<i32>().unwrap());
node.borrow_mut().left = create_bitree_cursive(node_values);
node.borrow_mut().right = create_bitree_cursive(node_values);
Some(Rc::new(RefCell::new(node)))
}
/* 前序遍历的方式创建二叉树 */
fn create_bitree(s: &str) -> TreeLink {
let mut node_values: VecDeque<&str> = s.split('_').collect();
create_bitree_cursive(&mut node_values)
}
二叉树
- 递归序
- 递归过程中每个节点都会顺序的出入3次
- 前序
- 先进入头,再进左子树,再进右子树
- 中序
- 先左、再中、再右
- 后序
- 先左、再右、再头
- 先右、再左、再头
前序遍历
递归方式
fn preorder_cursive(root: TreeLink, res: &mut Vec<i32>) {
if root.is_none() {
return;
}
if let Some(node) = root {
res.push(node.borrow().elem);
preorder_cursive(node.borrow().left.clone(), res);
preorder_cursive(node.borrow().right.clone(), res);
}
}
fn preorder_traversal(root: TreeLink) {
let mut res: Vec<i32> = Vec::new();
preorder_cursive(root, &mut res);
println!("res: {:?}", res);
}
非递归方式
- 算法
- 每次栈弹出一个节点
- 打印这个节点
- 先右、再左节点入栈
- 循环
-
实现代码
fn preorder_traversal2(root: &TreeLink) -> Vec<i32> { if root.is_none() { return vec![]; } let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![]; let mut res: Vec<i32> = vec![]; stack.push(root.clone().unwrap()); while let Some(cur) = stack.pop() { res.push(cur.borrow().elem); if let Some(node) = cur.borrow().right.clone() { stack.push(node); } if let Some(node) = cur.borrow().left.clone() { stack.push(node) } } res }
中序遍历
- 算法
- 每棵左子树进栈
- 依次弹出
- 再将弹出的节点的右侧左子树进栈
-
代码实现
fn inorder_uncursive(root: &TreeLink) -> Vec<i32> { let mut res: Vec<i32> = vec![]; if root.is_none() { return res; } let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![]; let mut head = root.clone(); while !stack.is_empty() || head.is_some() { if let Some(node) = head { stack.push(node.clone()); head = node.borrow().left.clone(); } else { if let Some(node) = stack.pop() { res.push(node.borrow().elem); head = node.borrow().right.clone(); } } } res }
后序遍历
- 算法流程
- 头节点入栈
- 栈弹出节点
- 先左再右/先右再左
- 循环
-
先左后右的代码实现
fn posorder1_uncursive(root: &TreeLink) -> Vec<i32> { let mut res: Vec<i32> = vec![]; if root.is_none() { return res; } // 这里使用TreeLink的类型,代码更简单,但算法不直观 let mut stack: Vec<TreeLink> = vec![]; let mut support: Vec<TreeLink> = vec![]; stack.push(root.clone()); while !stack.is_empty() { if let Some(Some(node)) = stack.pop() { support.push(Some(node.clone())); stack.push(node.borrow().left.clone()); stack.push(node.borrow().right.clone()); } } while !support.is_empty() { if let Some(Some(node)) = support.pop() { res.push(node.borrow().elem) } } res }
-
先右后左的代码实现
fn posorder_uncursive2(root: &TreeLink) -> Vec<i32> { let mut res: Vec<i32> = vec![]; if root.is_none() { return res; } // 这里用Rc<RefCell<>>类型,代码繁琐 let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![]; let mut support: Vec<Rc<RefCell<TreeNode>>> = vec![]; stack.push(root.clone().unwrap()); while !stack.is_empty() { if let Some(node) = stack.pop() { support.push(node.clone()); if let Some(left_node) = node.borrow().right.clone() { stack.push(left_node); } if let Some(right_node) = node.borrow().left.clone() { stack.push(right_node); } } } while let Some(node) = support.pop() { res.push(node.borrow().elem) } res }
宽度优先遍历
- 算法
- 用队列
- 先进头节点
- 弹出节点就打印
- 再把它的节点先左后右入队
- 循环
-
算法实现
fn width_traversial(root: &TreeLink) -> Vec<i32> { let mut res: Vec<i32> = vec![]; let mut queue: VecDeque<TreeLink> = VecDeque::new(); queue.push_back(root.clone()); while !queue.is_empty() { if let Some(Some(node)) = queue.pop_front() { res.push(node.borrow().elem); queue.push_back(node.borrow().left.clone()); queue.push_back(node.borrow().right.clone()); } } res }
求二叉树的最大宽度
用HashMap
-
数据结构
type TreeLink = Option<Box<TreeNode>>; #[derive(Debug, Hash, PartialEq, Eq)] struct TreeNode { elem: i32, left: TreeLink, right: TreeLink, }
- 由于
RefCell<T>
不能实现Hash特性 - 所以使用了
Box<T>
的方案
- 由于
- 算法
- 初始状态
- 当前统计的层cur_level = 1
- 最大宽度 max_level_nodes = 0
- 当前层宽度 cur_level_nodes = 0
HashMap<节点, 此节点对应的层>
- 队列
queue<节点>
- 将root节点入队列
- 将root节点和它对应的层1入
HashMap.insert(root, 1)
- 队列弹出节点
- 从HashMap中取得此节点对应的层
- 如果当前层 == 节点对应层
- 当前层宽度加上1
- 如果当前层 != 节点对应层
- 说明节点已经到下层
- 当前层+=1
- 统计最大宽度
- 当前层宽度 = 1
- 把节点的左、右非空节点入队列
- 把节点的左、右非空节点对应的层入HashMap
- 初始状态
-
算法实现
fn max_width_hash(root: &TreeLink) -> i32 { let mut map: HashMap<Option<&Box<TreeNode>>, usize> = HashMap::new(); let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new(); let mut cur_level: usize = 1; let mut cur_level_nodes = 0; let mut max_level_nodes: i32 = 0; queue.push_back(root.as_ref()); map.insert(root.as_ref(), 1); while let Some(link) = queue.pop_front() { let node_level = *map.get(&link).unwrap(); if let Some(cur) = link { if node_level == cur_level { cur_level_nodes += 1; } else { max_level_nodes = max(max_level_nodes, cur_level_nodes); cur_level_nodes = 1; cur_level += 1; } if cur.left.is_some() { map.insert(cur.left.as_ref(), cur_level + 1); queue.push_back(cur.left.as_ref()); } if cur.right.is_some() { map.insert(cur.right.as_ref(), cur_level + 1); queue.push_back(cur.right.as_ref()); } } } max(max_level_nodes, cur_level_nodes) }
不用HashMap
- 算法
- 队列弹出节点
- 当前节点是不是本层最后一个节点
- 不是:增加本层节点数
- 是:更新最大宽度,更新下一层最后一个节点
-
算法实现
fn max_width_unhash(root: &TreeLink) -> i32 { let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new(); let mut max_level_nodes = 0; let mut cur_level_nodes = 0; let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap(); let mut next_end: &Box<TreeNode> = root.as_ref().unwrap(); queue.push_back(root.as_ref()); while let Some(Some(node)) = queue.pop_front() { cur_level_nodes += 1; if node.left.is_some() { queue.push_back(node.left.as_ref()); next_end = node.left.as_ref().unwrap(); } if node.right.is_some() { queue.push_back(node.right.as_ref()); next_end = node.right.as_ref().unwrap(); } if node == cur_end { max_level_nodes = max(max_level_nodes, cur_level_nodes); cur_level_nodes = 0; cur_end = next_end; } } max_level_nodes }
二叉树的属性判断
判断是否是搜索二叉树
- 搜索二叉树
- 左节点 < root
- 右节点 > root
- 算法流程
- 中序遍历一定是升序
-
递归算法实现
fn check_bts(root: Option<&Box<TreeNode>>) -> BtsInfo { if let Some(node) = root { let left = check_bts(node.left.as_ref()); if !left.isbts || left.max_val >= node.elem { return BtsInfo::new(false); } let right = check_bts(node.right.as_ref()); if !right.isbts || node.elem >= right.min_val { return BtsInfo::new(false); } else { let mut info = BtsInfo::new(true); info.min_val = min(node.elem, left.min_val); info.max_val = max(node.elem, right.max_val); return info; } } else { BtsInfo::new(true) } } fn is_bts(root: &TreeLink) -> bool { let info = check_bts(root.as_ref()); info.isbts }
判断是否是完全二叉树
- 完全二叉树
- 完整齐全的二叉树
- 每一层都是全的
- 最后一层也是先有左子再有右子
- 算法流程
- 宽度优先遍历
- 若出现无左有右则不是
- 满足上面条件的情况下
- 若出现左右子不全
- 则后面的节点必须为叶子节点
-
算法实现
fn is_cbt_uncursive(root: &TreeLink) -> bool { let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new(); queue.push_back(root.as_ref()); let mut must_leaf: bool = false; while let Some(Some(node)) = queue.pop_front() { if node.left.is_none() && node.right.is_some() { return false; } if node.left.is_some() && node.right.is_none() { must_leaf = true; } if must_leaf && !is_leaf(node) { return false; } queue.push_back(node.left.as_ref()); queue.push_back(node.right.as_ref()); } true }
判断是否是满二叉树
- 满二叉树
- 树的最大深度deep和节点数N有关系:deep = 2^N - 1
-
递归算法实现
fn fbts_cursive(root: Option<&Box<TreeNode>>) -> FbtsInfo { if let Some(node) = root { let left = fbts_cursive(node.left.as_ref()); let right = fbts_cursive(node.right.as_ref()); FbtsInfo { nodes: left.nodes + right.nodes + 1, deep: max(left.deep, right.deep) + 1, } } else { FbtsInfo { nodes: 0, deep: 0 } } } fn is_fbts_cursive(root: &TreeLink) -> bool { if root.is_none() { return true; } let info = fbts_cursive(root.as_ref()); info.nodes == (1 << info.deep) - 1 }
-
非递归算法实现
fn is_fbts_uncursive(root: &TreeLink) -> bool { let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new(); let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap(); let mut next_end: &Box<TreeNode> = root.as_ref().unwrap(); let mut deep: u32 = 0; let mut total_nodes: i32 = 0; queue.push_back(root.as_ref()); while let Some(Some(node)) = queue.pop_front() { total_nodes += 1; if node.left.is_some() { queue.push_back(node.left.as_ref()); next_end = node.left.as_ref().unwrap(); } if node.right.is_some() { queue.push_back(node.right.as_ref()); next_end = node.right.as_ref().unwrap(); } if node == cur_end { cur_end = next_end; deep += 1; } } total_nodes == (1 << deep) - 1 }
判断是否是平衡二叉树
- 平衡二叉树
- 左、右子树都是平衡的
- 左子树与右子树的高度差不超过1
-
算法实现
struct BlInfo { is_balance: bool, deep: i32, } fn balance_cursive(root: Option<&Box<TreeNode>>) -> BlInfo { if let Some(node) = root { let left = balance_cursive(node.left.as_ref()); let right = balance_cursive(node.right.as_ref()); BlInfo { deep: max(left.deep, right.deep) + 1, is_balance: left.is_balance && right.is_balance && (left.deep - right.deep).abs() < 2, } } else { BlInfo { deep: 0, is_balance: true, } } } fn is_balance(root: &TreeLink) -> bool { let info = balance_cursive(root.as_ref()); info.is_balance }
寻找最近的公共祖先节点
- 算法1
- 将二叉树中每个结点的祖先节点都放到HashMap中
- 针对node1收集从它到根节点的父节点
- 针对node2查看它的父节点是否有node1父节点的共同节点
-
算法1实现
fn find_lca<'a>( root: &'a TreeLink, node1: TreeNodeLink, node2: TreeNodeLink, ) -> Option<&'a Box<TreeNode>> { let mut lca: TreeNodeLink = None; let mut fmap: HashMap<TreeNodeLink, TreeNodeLink> = HashMap::new(); let mut set: HashSet<TreeNodeLink> = HashSet::new(); fmap.insert(root.as_ref(), root.as_ref()); // 创建所有节点的父节点集合{子节点:父节点} get_fmap(root.as_ref(), &mut fmap); // 将所有node1的父节点收集到set中 let mut node = node1; while let Some(&Some(father)) = fmap.get(&node) { if father != root.as_ref().unwrap() { set.insert(Some(father.clone())); node = Some(father); } else { break; } } // 检查node2的所有父节点是不是在set中,是则找到共同最低父节点 node = node2; while let Some(&Some(father)) = fmap.get(&node) { if father == root.as_ref().unwrap() { break; } if !set.contains(&Some(father)) { node = Some(father); } else { lca = Some(father); break; } } lca }
-
算法2递归实现
fn find_lca_cursive<'a>( root: TreeNodeLink<'a>, node1: TreeNodeLink<'a>, node2: TreeNodeLink<'a>, ) -> TreeNodeLink<'a> { if root.is_none() || root == node1 || root == node2 { return root; } if let Some(node) = root { // 左子树有节点、右子树有节点 let left = find_lca_cursive(node.left.as_ref(), node1, node2); let right = find_lca_cursive(node.right.as_ref(), node1, node2); match (left, right) { (Some(_), Some(_)) => return root, (Some(l), _) => return Some(l), (None, Some(r)) => return Some(r), (None, None) => return None, } } None }
寻找一个节点的后继节点
- 后继节点
- 中序遍历中,排在一个节点后面的节点是后继节点
- 排在一个节点的前面节点是前趋节点
- 中序遍历: DBEAFCG->Null
-
如果节点的结构如下,能否缩短找后继节点的复杂度
class Node { int elem; Node left; Node right; Node parent; }
- 算法流程
- 如果节点x有右树
- x的后继是右树的最左叶节点
- 如果节点x无右树
- 向上看是否是父节点的左孩子
- 不是继续向上找
- 是则后继就是这个父节点
- 整棵树最后一个节点特殊
- 如果节点x有右树
-
算法伪代码实现
// 找最左侧节点 fn left_leaf(root: TreeNodeLink) -> TreeNodeLink { if let Some(node) = root { while node.left.is_some() { node = node.left.as_ref().unwrap(); } Some(node) } else { None } } fn node_successor(head: TreeNodeLink) -> TreeNodeLink { if let Some(node) = head { // 如果节点有右子树,后继节点为右子树最左侧节点 if node.right.is_some() { return left_leaf(node.right.as_ref()); } // 如果没有右子树,当前节点是父节点的右孩子,继续向上找 let mut parent = node.parent; while parent.is_some && parent.left != node { node = parent; parent = node.parent; } // 当parent是空时,说明node是整棵树最右侧结点,没有后继节点 return parent; } else { None } }
将长条纸对折N次,打印凹凸顺序
折纸就是一棵二叉树,所有凸节点的左节点为凸,右节点为凹
- 算法
- 中序遍历
-
算法实现
fn print_cursive(curlevel: i32, level: i32, down: bool) { if curlevel > level { return; } print_cursive(curlevel + 1, level, true); if down { print!("凹"); } else { print!("凸"); } print_cursive(curlevel + 1, level, false) } // 对折n次 fn print_all_folds(n: i32) { print_cursive(1, n, true); }
HashMap
要求键值实现Eq和Hash特性,尽管这经常可以通过使用#[derive(PartialEq, Eq, Hash)]
实现。如果你自己实现了这些,重要的是以下属性成立:
k1 == k2 => hash(k1) == hash(k2)
换句话说,如果两个键相等,它们的哈希值也必须相等
自定义的key类型需要Eq和Hash特性,Eq又需要PartialEq
ParitalEq和Eq
Eq完成的是相等和不相等的判断,ParitalEq可以实现A和B是否相等的判断,但不能与自己比较,因为NaN != NaN
;而Eq则是表示可以和自己进行相等判断(有点类似异或交换的感觉,通过异或交换a、b的前提是他们在不同的内存空间中,否则就会失效)
通过#[driver(ParitalEq, Eq)]
系统会自动实现相等性,它是把结构体中所有字段如果相等,则判定相等
Hash 特性
pub trait Hash {
fn hash<H>(&self, state: &mut H)
where H: Hasher;
fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher,
{ ... }
}
一个可散列的类型:
实现Hash的类型能够用Hasher的一个实例进行散列。
如何实现Hash特性
系统自动实现
如果所有字段都实现了Hash,你可以用#[derive(Hash)]
来派生Hash。产生的哈希值将是在每个字段上调用哈希值的组合。
#[derive(Hash)]
struct Rustacean {
name: String,
country: String,
}
实现自己的Hash特性
use std::hash::{Hash, Hasher};
struct Person {
id: u32,
name: String,
phone: u64,
}
impl Hash for Person {
// 将state此值提供给给定的散列器 Hasher
fn hash<H: Hasher>(&self, state: &mut H) {
self.id.hash(state);
self.phone.hash(state);
}
}
fn hash<H>(&self, state: &mut H)
- 将state此值提供给给定的散列计算器Hasher
-
使用
use std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; let mut hasher = DefaultHasher::new(); 7920.hash(&mut hasher); println!("Hash is {:x}!", hasher.finish());
fn hash_slice<H>(data: &[Self], state: &mut H)
- 将Self这种类型的切片输入给定的散列器
- 这个方法是作为一种便利,但它的实现也明确地没有被指定。
- 它并不保证等同于对hash的重复调用,Hash的实现应该记住这一点
- 如果切片在PartialEq的实现中没有被当作一个整体单元,就应该自己调用hash。
- 例如
- 一个VecDeque的实现可能会天真地调用as_slices
- 然后在每个slice上进行hash_slice
- 但这是错误的
- 因为这两个slice可以通过调用make_contiguous来改变Key的值
- 而不会影响PartialEq的结果
- 由于这些切片没有被当作单一的单位
- 而是一个更大的deque的一部分
- 所以这个方法不能使用
-
使用
let mut hasher = DefaultHasher::new(); let numbers = [6, 28, 496, 8128]; Hash::hash_slice(&numbers, &mut hasher); println!("Hash is {:x}!", hasher.finish());
其中Hasher也是一个特性,它是一个用于散列任意字节流的特性。Hasher的实例通常代表在散列数据时改变的状态。
Hasher提供了一个相当基本的接口,用于检索生成的哈希值(用finish
),以及将整数和字节切片写进实例(用write
和write_u8
等)。大多数情况下,Hasher实例是与Hash特性一起使用的。
Hasher主要有两个方法:
pub trait Hasher {
// 返回到目前为止所写数据的哈希值
fn finish(&self) -> u64;
// 将一些数据写入哈希器
fn write(&mut self, bytes: &[u8]);
}
Hasher Hash计算器的使用方法:
let mut hasher = DefaultHasher::new();
hasher.write_u32(1989);
hasher.write_u8(11);
hasher.write_u8(9);
hasher.write(b"Huh?");
println!("Hash is {:x}!", hasher.finish());
Cell
共享的可变容器。 rust内存安全基于以下规则:给定对象T,只能有以下之一:
- 对对象有几个不可变的引用(&T)(也被称为别名)。
- 对象有一个可变引用(&mut T)(也称为可变性)。
这是由Rust编译器强制执行的。然而,在有些情况下,这个规则不够灵活。有时需要对一个对象有多个引用,但又要对其进行突变。
可共享的可变容器的存在是为了允许以可控的方式进行修改,甚至在存在别名的情况下。Cell
Cell
Cell类型有两种风格。Cell
- 对于实现Copy的类型,get方法检索当前的内部值
- 对于实现Default的类型,take方法用Default::default()替换当前的内部值并返回替换后的值
- 对于所有的类型,替换方法替换当前的内部值并返回替换后的值,into_inner方法消耗Cell
并返回内部值。此外,set方法替换了内部值,放弃了被替换的值
RefCell
更常见的继承可变性,即一个人必须有唯一的访问权才能变异一个值,这是一个关键的语言元素,使Rust能够强烈地推理指针别名,静态地防止崩溃的错误。正因为如此,继承的可变性是首选,而内部可变性是最后的手段。由于Celll类型可以在不允许的地方进行变异,所以在某些情况下,内部变异可能是合适的,甚至是必须使用的,比如说
- 在不可变的东西的 “内部 “引入可变性
- 逻辑上不可变的方法的实现细节。
- 克隆的变异实现
在不可变的东西内部引入了可变性
许多共享的智能指针类型,包括Rc
那么,在共享指针类型内放置一个RefCell
use std::cell::{RefCell, RefMut};
use std::collections::HashMap;
use std::rc::Rc;
fn main() {
let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
// 创建一个新块来限制动态借用的范围
{
let mut map: RefMut<_> = shared_map.borrow_mut();
map.insert("africa", 92388);
map.insert("kyoto", 11837);
map.insert("piccadilly", 11826);
map.insert("marbles", 38);
}
// 如果前面没有新建代码块,这里就会出问题
// 这就是使用`RefCell'的主要危害
let total: i32 = shared_map.borrow().values().sum();
println!("{}", total);
}
逻辑不可变方法的实现细节
偶尔,我们可能不希望在API中暴露出 “引擎盖 “下正在发生的变异。这可能是因为逻辑上的操作是不可变的,但是例如缓存迫使实现方法执行突变;或者是因为你必须使用突变来实现一个最初定义为取自&self的特征方法。