遍历二叉搜索树

二叉搜索树(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

主要区别：

数据结构：BFS 使用队列，DFS 使用堆栈（或递归）。
遍历顺序：BFS 逐层访问节点，DFS 首先深入。
内存使用：对于宽树，BFS 可能使用更多内存，DFS 可能使用更少。
路径查找：BFS 在无权图中查找最短路径，DFS 不保证这一点。
应用：BFS 用于查找最近的节点，DFS 用于路径存在性或树克隆。

广度优先遍历(breadth first search)

breadth first search

BFS特性

逐层遍历树。
使用队列数据结构。
在无权图中查找最短路径。
对于大型树，需要更多内存，因为它存储了同一层的所有节点。
适用于查找最近的节点。

需要一个双向队列,不停的从后插入,从前删除,每次弹出一个节点,将其左右子节点入队.

根节点入队
出队一个节点，将其左右子节点入队
重复2，直到队列为空

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
use std::collections::VecDeque;

impl BinarySearchBoxNode {
    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        // maybe I should use a reference count instead of a box pointer
        queue.push_back(Box::new(self.clone())); 
        while let Some(v) = queue.pop_front() {
            result.push(v.val);
            if let Some(left) = v.left {
                queue.push_back(left)
            }
            if let Some(right) = v.right {
                queue.push_back(right);
            }
        }
        result
    }
}

深度优先遍历(depth first search)

DFS特性

在回溯之前尽可能深地遍历树。
使用堆栈（通过递归隐式使用）。
可以递归或迭代实现。
对于深度树，需要的内存比 BFS 少。
不保证找到最短路径。
适用于检查路径是否存在。

前序遍历(preorder)

先序遍历:

首先访问(处理)当前节点。然后递归遍历左子树。最后递归遍历右子树。

顺序: 节点 -> 左 -> 右

使用案例:

创建树的副本。
获取前缀表达式。

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

impl BinarySearchBoxNode {
    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }
    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_preorder_recursive(result);
        }
    }
}

顺序遍历 (inorder)

中序遍历:

首先递归遍历左子树。然后,访问(处理)当前节点。最后,递归遍历右子树。

顺序: 左 -> 节点 -> 右

使用案例:

在二叉搜索树(BST)中,中序遍历可以得到有序的节点。
获取中缀表达式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl BinarySearchBoxNode {
    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }
    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.dfs_inorder_recursive(result);
        }
    }
}

后序遍历 (postorder)

后序遍历:

首先递归遍历左子树。然后递归遍历右子树。最后访问(处理)当前节点。

顺序: 左 -> 右 -> 节点

使用案例:

删除树。
获取后缀表达式。
评估表达式树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl BinarySearchBoxNode {
    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }
    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }

基于Rc<Refcell<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
 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
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct BinarySearchNode {
    val: i32,
    left: Option<Rc<RefCell<Self>>>,
    right: Option<Rc<RefCell<Self>>>,
}

impl BinarySearchTree for BinarySearchNode {
    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.borrow_mut().insert(val);
            } else {
                self.left = Some(Rc::new(RefCell::new(Self::new(val))));
            }
            return;
        }
        if let Some(right) = &mut self.right {
            right.borrow_mut().insert(val);
        } else {
            self.right = Some(Rc::new(RefCell::new(Self::new(val))));
        }
    }

    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(Rc::new(RefCell::new(Self {
            val: self.val,
            left: self.left.clone(),
            right: self.right.clone(),
        })));

        while let Some(node) = queue.pop_front() {
            result.push(node.borrow().val);

            if let Some(left) = &node.borrow().left {
                queue.push_back(left.clone());
            }
            if let Some(right) = &node.borrow().right {
                queue.push_back(right.clone());
            }
        }

        result
    }

    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }

    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.borrow().dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_preorder_recursive(result);
        }
    }

    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }

    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.borrow().dfs_inorder_recursive(result);
        }
    }

    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }

    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }
}

测试snippet

  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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

pub trait BinarySearchTree {
    fn new(val: i32) -> Self;
    fn insert(&mut self, val: i32);
    fn bfs(&self) -> Vec<i32>;
    fn dfs_preorder(&self) -> Vec<i32>;
    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>);
    fn dfs_inorder(&self) -> Vec<i32>;
    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>);
    fn dfs_postorder(&self) -> Vec<i32>;
    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>);
}

// 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 BinarySearchTree for 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)));
        }
    }

    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(Box::new(self.clone())); // maybe I should use a reference count instead of a box pointer
        while let Some(v) = queue.pop_front() {
            result.push(v.val);
            if let Some(left) = v.left {
                queue.push_back(left)
            }
            if let Some(right) = v.right {
                queue.push_back(right);
            }
        }
        result
    }
    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }
    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_preorder_recursive(result);
        }
    }
    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }
    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.dfs_inorder_recursive(result);
        }
    }
    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }
    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }
}

#[derive(Debug, PartialEq, Eq)]
pub struct BinarySearchNode {
    val: i32,
    left: Option<Rc<RefCell<Self>>>,
    right: Option<Rc<RefCell<Self>>>,
}

impl BinarySearchTree for BinarySearchNode {
    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.borrow_mut().insert(val);
            } else {
                self.left = Some(Rc::new(RefCell::new(Self::new(val))));
            }
            return;
        }
        if let Some(right) = &mut self.right {
            right.borrow_mut().insert(val);
        } else {
            self.right = Some(Rc::new(RefCell::new(Self::new(val))));
        }
    }

    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(Rc::new(RefCell::new(Self {
            val: self.val,
            left: self.left.clone(),
            right: self.right.clone(),
        })));

        while let Some(node) = queue.pop_front() {
            result.push(node.borrow().val);

            if let Some(left) = &node.borrow().left {
                queue.push_back(left.clone());
            }
            if let Some(right) = &node.borrow().right {
                queue.push_back(right.clone());
            }
        }

        result
    }

    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }

    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.borrow().dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_preorder_recursive(result);
        }
    }

    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }

    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.borrow().dfs_inorder_recursive(result);
        }
    }

    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }

    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    fn create_binary_tree<T: BinarySearchTree>() -> T {
        let mut root = T::new(5);
        root.insert(3);
        root.insert(7);
        root.insert(2);
        root.insert(4);
        root.insert(6);
        root.insert(8);
        root
    }

    #[test]
    fn test_insert_and_bfs() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.bfs(), vec![5, 3, 7, 2, 4, 6, 8]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.bfs(), vec![5, 3, 7, 2, 4, 6, 8]);
    }

    #[test]
    fn test_dfs_preorder() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.dfs_preorder(), vec![5, 3, 2, 4, 7, 6, 8]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.dfs_preorder(), vec![5, 3, 2, 4, 7, 6, 8]);
    }

    #[test]
    fn test_dfs_inorder() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.dfs_inorder(), vec![2, 3, 4, 5, 6, 7, 8]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.dfs_inorder(), vec![2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_dfs_postorder() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.dfs_postorder(), vec![2, 4, 3, 6, 8, 7, 5]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.dfs_postorder(), vec![2, 4, 3, 6, 8, 7, 5]);
    }

    #[test]
    fn test_single_node() {
        let root = BinarySearchNode::new(10);
        assert_eq!(root.bfs(), vec![10]);
        assert_eq!(root.dfs_preorder(), vec![10]);
        assert_eq!(root.dfs_inorder(), vec![10]);
        assert_eq!(root.dfs_postorder(), vec![10]);
        let root = BinarySearchBoxNode::new(10);
        assert_eq!(root.bfs(), vec![10]);
        assert_eq!(root.dfs_preorder(), vec![10]);
        assert_eq!(root.dfs_inorder(), vec![10]);
        assert_eq!(root.dfs_postorder(), vec![10]);
    }
}

二叉搜索树上的BFS和DFS的复杂度分析

特性	BFS (广度优先搜索)	DFS (深度优先搜索)
时间复杂度	O(n)	O(n)
空间复杂度	O(w)	O(h)
解释	- BFS访问所有节点一次，因此为O(n)。 - 空间复杂度由树的最大宽度(w)决定，因为它将当前级别的节点存储在队列中。	- DFS访问所有节点一次，因此为O(n)。 - 空间复杂度由树的最大高度(h)决定，因为它将节点存储在调用堆栈中。
备注	- 在平衡二叉搜索树中，w大约为n/2，h为log(n)。 - 在倾斜二叉搜索树中，w可以为n，h可以为n。

二叉搜索树(BST)#

基于Box<T>的二叉搜索树的实现#

BFS vs DFS#

广度优先遍历(breadth first search)#

BFS特性#

深度优先遍历(depth first search)#

DFS特性#

前序遍历(preorder)#

顺序遍历 (inorder)#

后序遍历 (postorder)#

基于Rc<Refcell<T> >的二叉搜索树的实现#

测试snippet#

二叉搜索树上的BFS和DFS的复杂度分析#

二叉搜索树(BST)

基于Box<T>的二叉搜索树的实现

BFS vs DFS

广度优先遍历(breadth first search)

BFS特性

深度优先遍历(depth first search)

DFS特性

前序遍历(preorder)

顺序遍历 (inorder)

后序遍历 (postorder)

基于Rc<Refcell<T> >的二叉搜索树的实现

测试snippet

二叉搜索树上的BFS和DFS的复杂度分析