遍历二叉搜索树
二叉搜索树(BST) 数据结构: 左子树节点的值都小于根节点的值 右子树节点的值都大于根节点的值 左右子树也分别为二叉搜索树 空节点为二叉搜索树 插入操作: 找到合适的位置, 小于当前节点插左树,大于等于当前节点插右树,空树直接插入, 保持二叉搜索树的性质, 重复1-3 基于Box<T>的二叉搜索树的实现 数据结构和Insert方法: 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 // Maybe I should use a reference count instead of a box pointer // for the bfs method. #[derive(Debug, PartialEq, Eq, Clone)] pub struct BinarySearchBoxNode { val: i32, left: Option<Box<Self>>, right: Option<Box<Self>>, } impl BinarySearchBoxNode { fn new(val: i32) -> Self { Self { val, left: None, right: None, } } fn insert(&mut self, val: i32) { if val < self.val { if let Some(left) = &mut self.left { left.insert(val); } else { self.left = Some(Box::new(Self::new(val))); } return; } if let Some(right) = &mut self.right { right.insert(val); } else { self.right = Some(Box::new(Self::new(val))); } } } BFS vs DFS 主要区别： ...