A generic binary search tree implementation. Here you can find more information about the algorithm: Scaler - Binary Search tree.
More...
#include <cassert>
#include <functional>
#include <iostream>
#include <memory>
#include <vector>
A generic binary search tree implementation. Here you can find more information about the algorithm: Scaler - Binary Search tree.
- See also
- binary_search_tree.cpp
◆ main()
556 {
565}
static void test_get_elements_inorder()
Function for testing get_elements_inorder().
Definition binary_search_tree2.cpp:498
static void test_contains()
Function for testing contains().
Definition binary_search_tree2.cpp:429
static void test_insert()
Function for testing insert().
Definition binary_search_tree2.cpp:358
static void test_get_elements_postorder()
Function for testing get_elements_postorder().
Definition binary_search_tree2.cpp:540
static void test_find_max()
Function for testing find_max().
Definition binary_search_tree2.cpp:475
static void test_get_elements_preorder()
Function for testing get_elements_preorder().
Definition binary_search_tree2.cpp:519
static void test_remove()
Function for testing remove().
Definition binary_search_tree2.cpp:392
static void test_find_min()
Function for testing find_min().
Definition binary_search_tree2.cpp:452
◆ test_contains()
static void test_contains |
( |
| ) |
|
|
static |
Function for testing contains().
- Returns
void
429 {
431
437
443
445}
The Binary Search Tree class.
Definition binary_search_tree2.cpp:20
bool insert(std::unique_ptr< bst_node > &node, T new_value)
Recursive function to insert a value into the BST.
Definition binary_search_tree2.cpp:90
bool contains(std::unique_ptr< bst_node > &node, T value)
Recursive function to check if a value is in the BST.
Definition binary_search_tree2.cpp:177
◆ test_find_max()
static void test_find_max |
( |
| ) |
|
|
static |
Function for testing find_max().
- Returns
void
475 {
477
481
486
488 assert(max == 6);
489
491}
bool find_max(std::unique_ptr< bst_node > &node, T &ret_value)
Recursive function to find the maximum value in the BST.
Definition binary_search_tree2.cpp:53
◆ test_find_min()
static void test_find_min |
( |
| ) |
|
|
static |
Function for testing find_min().
- Returns
void
452 {
454
458
463
465 assert(min == 3);
466
468}
bool find_min(std::unique_ptr< bst_node > &node, T &ret_value)
Recursive function to find the minimum value in the BST.
Definition binary_search_tree2.cpp:71
◆ test_get_elements_inorder()
static void test_get_elements_inorder |
( |
| ) |
|
|
static |
Function for testing get_elements_inorder().
- Returns
void
498 {
499 std::cout <<
"Testing BST get_elements_inorder...";
500
506
509 assert(actual == expected);
510
512}
std::vector< T > get_elements_inorder()
Get all values of the BST in in-order order.
Definition binary_search_tree2.cpp:321
◆ test_get_elements_postorder()
static void test_get_elements_postorder |
( |
| ) |
|
|
static |
Function for testing get_elements_postorder().
- Returns
void
540 {
541 std::cout <<
"Testing BST get_elements_postorder...";
542
548
551 assert(actual == expected);
552
554}
std::vector< T > get_elements_postorder()
Get all values of the BST in post-order order.
Definition binary_search_tree2.cpp:345
◆ test_get_elements_preorder()
static void test_get_elements_preorder |
( |
| ) |
|
|
static |
Function for testing get_elements_preorder().
- Returns
void
519 {
520 std::cout <<
"Testing BST get_elements_preorder...";
521
527
530 assert(actual == expected);
531
533}
std::vector< T > get_elements_preorder()
Get all values of the BST in pre-order order.
Definition binary_search_tree2.cpp:333
◆ test_insert()
static void test_insert |
( |
| ) |
|
|
static |
Function for testing insert().
- Returns
void
358 {
360
362 bool res = tree.
insert(5);
364 assert(res);
367 assert(max == 5);
368 assert(min == 5);
369 assert(tree.
size() == 1);
370
376 assert(max == 6);
377 assert(min == 3);
378 assert(tree.
size() == 4);
379
380 bool fail_res = tree.
insert(4);
381 assert(!fail_res);
382 assert(tree.
size() == 4);
383
385}
std::size_t size()
Get the number of values in the BST.
Definition binary_search_tree2.cpp:314
◆ test_remove()
static void test_remove |
( |
| ) |
|
|
static |
Function for testing remove().
- Returns
void
392 {
394
400
401 bool res = tree.
remove(5);
403 assert(res);
406 assert(max == 6);
407 assert(min == 3);
408 assert(tree.
size() == 3);
410
414 assert(tree.
size() == 0);
416
417 bool fail_res = tree.
remove(5);
418 assert(!fail_res);
419 assert(tree.
size() == 0);
420
422}
bool remove(std::unique_ptr< bst_node > &parent, std::unique_ptr< bst_node > &node, T rm_value)
Recursive function to remove a value from the BST.
Definition binary_search_tree2.cpp:125