Мне нужны некоторые практические методы, которые я могу реализовать на уже существующей реализации BST - PullRequest
Новая
       13

Мне нужны некоторые практические методы, которые я могу реализовать на уже существующей реализации BST

1 голос
/ 01 апреля 2019

Очень просто, у меня есть тест в классе, который я должен сделать, используя этот ранее существующий код.Мы должны будем реализовать какую-то функцию.Мне было интересно, над какой функцией я должен работать?Я не очень хорош в кодировании на месте и хочу быть как можно более подготовленным.

В практической версии мы использовали эту функцию под названием Top5 (), которая распечатывала самые высокие 5 элементовBST.Итак, я закончил это и создал свою собственную версию lower3 (), которая возвращает третий самый низкий элемент в BST.Мне просто интересно, есть ли еще что-то, над чем я могу работать, такой же сложности, как это, и могу ли я улучшить это?(просто я не хочу запутывать себя). 

class BTnode {
public:
    int key;
    BTnode *left, *right, *parent;
    BTnode(int key, BTnode *left, BTnode *right, BTnode *parent) : 
    key(key), left(left), right(right), parent(parent) {};
    };


   // Desc: A binary search tree (root)
//  Inv: All keys in root->left <= root->key <= all keys in root->right
class BST {
private:
    // Desc: The root of the BST (NULL if empty)
    BTnode *root;


    // Desc: Helper function for .insert(key)
    BTnode *insertH(BTnode *root, int key);
// this is the data members.

void BST::top5H(BTnode* node, int* count) const{
if(node->right){
    top5H(node->right, count);
}
if(*count == 5){
    return;
}
cout << node->key << " ";
(*count)++;

if(node->left){
    top5H(node->left, count);
}
}
//try to find 5 highest.
void BST::top5() const {
int* count = new int(0);
top5H(root, count);
cout << endl;
free(count);
} // top5
// this is my implementation of top5().

void BST::lowest3H(BTnode* node, int* count, int* arr) const{
if(node->left){
    lowest3H(node->left, count, arr);
}
if(*count == 3){
    return;
}
cout << node->key << " ";
arr[*count] = node->key;
(*count)++;

if(node->right){
    lowest3H(node->right, count, arr);
}
}
//try to find 3rd lowest.
void BST::lowest3() const {
int * arr = NULL;
arr = new int[100];
int* count = new int(0);
int min;
int temp;
lowest3H(root, count, arr);
for(int i = 0; i < 3; i++){
    min = i;
    for(int j = i+1; j < 100; j++){
        if(arr[j] < arr[min]){
            min = j;
        }
    }
    temp = min;
    arr[min] = arr[i];
    arr[i] = arr[temp];
    cout << arr[i];
}

cout << endl << arr[2] << endl;
    free(count);
} 
//This is my implementation of lowest3()

Эти работы, для BST, которые мне дали, предполагают, что они дадут нам хорошо сформированные примеры, так что никаких угловых случаев.

...