DFS

Binary Search Tree (BST) data structure: left subtree nodes are less than root node right subtree nodes are greater than root node left and right subtree are also binary search tree empty node is also binary search tree insert new node: find the position insert left tree if val < current node insert right tree if val >= current node keep the binary search tree property repeat 1-4 Implement BST with Box<T> 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 Key Differences: ...

二叉搜索树(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 主要区别： ...