bst-rs

Rust 中的递归和迭代二叉搜索树实现

目录

• 个人目标
• 关于
• 快速入门
• 许可证
• 贡献
• 灵感

关于

本软件包包含递归和迭代二叉搜索树实现。包括所有常见操作以及常见的遍历迭代器。

二叉搜索树中的所有元素都必须实现 Ord 特性。

值得注意的是，RecursiveBST 更有可能 blow the stack. 关于为什么是这样，请参阅 Rust 中尾部调用优化的故事。

个人目标

我制作这个库是为了学习并巩固如 所有权、借用、泛型 和 生命周期 等概念。我不能保证实现特别高效，或者如果它们是，那并不是我首要考虑的。

话虽如此，还有一些领域我希望能改进或包含

• 编写惯用代码。
• 有效地使用 macro_rules! 来减少大量重复代码。
• 实现一个 pretty_print() 函数来以美观的方式显示二叉搜索树。
• 实现迭代节点清理的 Drop 特性。
• 在堆上预分配节点空间以减少插入的不效率。

如果有人愿意这样做，我将非常乐意接受（并鼓励）贡献。请参阅 CONTRIBUTING!)

快速入门

use bst_rs::{BinarySearchTree, IterativeBST, RecursiveBST};

// Create new empty binary search trees
let mut iterative_bst = IterativeBST::new();
assert!(iterative_bst.is_empty());

let mut recursive_bst = RecursiveBST::new();
assert!(recursive_bst.is_empty());

// Insert elements (no duplicates are allowed)
iterative_bst.insert(10);
iterative_bst.insert(10);   // Element is not inserted
iterative_bst.insert(5);
iterative_bst.insert(2);
iterative_bst.insert(15);
iterative_bst.insert(25);
assert_eq!(iterative_bst.size(), 5);

recursive_bst.insert(10);
recursive_bst.insert(10);   // Element is not inserted
recursive_bst.insert(5);
recursive_bst.insert(2);
recursive_bst.insert(15);
recursive_bst.insert(25);
assert_eq!(recursive_bst.size(), 5);

// Check if element exists
assert!(iterative_bst.contains(&5));    // true
assert!(!iterative_bst.contains(&0));   // false

assert!(recursive_bst.contains(&5));    // true
assert!(!recursive_bst.contains(&0));   // false

// Remove elements
iterative_bst.remove(&10);
iterative_bst.remove(&50); // No change to tree as element does not exist
assert_eq!(iterative_bst.size(), 4);

recursive_bst.remove(&10);
recursive_bst.remove(&50); // No change to tree as element does not exist
assert_eq!(recursive_bst.size(), 4);

// Get height of tree
assert_eq!(iterative_bst.height(), Some(2));
assert_eq!(recursive_bst.height(), Some(2));

// Get minimum element of tree
assert_eq!(iterative_bst.min(), Some(&2));
assert_eq!(recursive_bst.min(), Some(&2));

// Get maximum element of tree
assert_eq!(iterative_bst.max(), Some(&25));
assert_eq!(recursive_bst.max(), Some(&25));

// Retrieve reference to element in tree
assert_eq!(iterative_bst.retrieve(&5), Some(&5));
assert_eq!(iterative_bst.retrieve(&100), None); // Element does not exist so None is returned
assert_eq!(recursive_bst.retrieve(&5), Some(&5));
assert_eq!(recursive_bst.retrieve(&100), None); // Element does not exist so None is returned

// View pre-order, in-order, post-order and level-order traversals
assert_eq!(iterative_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
assert_eq!(iterative_bst.in_order_vec(), vec![&2, &5, &15, &25]);
assert_eq!(iterative_bst.post_order_vec(), vec![&2, &5, &25, &15]);
assert_eq!(iterative_bst.level_order_vec(), vec![&15, &5, &25, &2]);

assert_eq!(recursive_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
assert_eq!(recursive_bst.in_order_vec(), vec![&2, &5, &15, &25]);
assert_eq!(recursive_bst.post_order_vec(), vec![&2, &5, &25, &15]);
assert_eq!(recursive_bst.level_order_vec(), vec![&15, &5, &25, &2]);

// Compare equality/in-equality of trees
assert_eq!(iterative_bst.asc_order_vec(), recursive_bst.asc_order_vec());
assert_ne!(iterative_bst, IterativeBST::new());
assert_ne!(recursive_bst, RecursiveBST::new());

许可证

MIT 许可证

贡献

在贡献之前，请阅读 CONTRIBUTING.md！（感谢！）

灵感

书籍 Learn Rust With Entirely Too Many Linked Lists 启发我尝试在语言中实现二叉搜索树。我同时也想创建我的第一个库供其他crate使用。