lundi 1 avril 2019

I need some practice methods I can implement on a pre-existing BST implementation

Very simply, I have an in class quiz that I have to do, using this preexisting code. We will have to implement a function of some sort. I was wondering, what kind of thing should I work on? I'm not very good at coding on the spot, and want to be as well prepped as possible.

The practice version had us do this function called Top5(), which printed out the highest 5 elements of the BST. So I finished that, and I made up my own version, lowest3(), which returns the 3rd lowest element in the BST. I was just wondering, is there anything else I can work on, of similar difficulty to this, and can I improve this? (simply, I don't want to confuse myself).

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()

These work, for the BSTs I was given, it is assumed that they would give us well formed examples, so no corner cases.

Aucun commentaire:

Enregistrer un commentaire