| 251 | |
| 252 | #[test] |
| 253 | fn t_insert() { |
| 254 | use crate::tree::binary::traverse::{InOrderVisitor, PreOrderVisitor}; |
| 255 | use crate::tree::binary::Tree; |
| 256 | |
| 257 | /* |
| 258 | [15, 14, 11, 2, 1, 7, 5, 4, 8] |
| 259 | |
| 260 | 7 |
| 261 | / \ |
| 262 | 2 14 |
| 263 | / \ / \ |
| 264 | 1 5 11 15 |
| 265 | / / |
| 266 | 4 8 |
| 267 | |
| 268 | */ |
| 269 | let mut tree = Tree::default(); |
| 270 | for v in vec![15, 14, 11, 2, 1, 7, 5, 4, 8] { |
| 271 | tree.root = insert(tree.root, v, v); |
| 272 | } |
| 273 | unsafe { |
| 274 | assert_eq!( |
| 275 | vec![7, 2, 1, 5, 4, 14, 11, 8, 15], |
| 276 | PreOrderVisitor::recursive(&tree) |
| 277 | ); |
| 278 | assert_eq!( |
| 279 | vec![1, 2, 4, 5, 7, 8, 11, 14, 15], |
| 280 | InOrderVisitor::recursive(&tree) |
| 281 | ); |
| 282 | } |
| 283 | |
| 284 | /* |
| 285 | [1, 2, 3, 4, 5, 6, 7, 8] |
| 286 | |
| 287 | 4 |
| 288 | / \ |
| 289 | 2 6 |
| 290 | / \ / \ |
| 291 | 1 3 5 7 |
| 292 | \ |
| 293 | 8 |
| 294 | */ |
| 295 | let mut tree = Tree::default(); |
| 296 | for v in 1..9 { |
| 297 | tree.root = insert(tree.root, v, v); |
| 298 | } |
| 299 | unsafe { |
| 300 | assert_eq!( |
| 301 | vec![4, 2, 1, 3, 6, 5, 7, 8], |
| 302 | PreOrderVisitor::recursive(&tree) |
| 303 | ); |
| 304 | assert_eq!( |
| 305 | vec![1, 2, 3, 4, 5, 6, 7, 8], |
| 306 | InOrderVisitor::recursive(&tree) |
| 307 | ); |
| 308 | } |
| 309 | } |
| 310 | |