Untitled
unknown
c_cpp
2 years ago
4.6 kB
27
Indexable
#include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct BST_Node_Struct { double data; struct BST_Node_Struct *left; struct BST_Node_Struct *right; } BST_Node; BST_Node *new_BST_Node(double key) { BST_Node *new_node = NULL; new_node = (BST_Node *)calloc(1, sizeof(BST_Node)); new_node->data = key; new_node->left = NULL; new_node->right = NULL; return new_node; } BST_Node *BST_insert(BST_Node *root, BST_Node *new_node) { if (root == NULL) return new_node; if (fabs(root->data - new_node->data) < 1e-15) printf("Duplicate node requested %f, it was ignored\n", root->data); else if (root->data > new_node->data) root->left = BST_insert(root->left, new_node); else if (root->data < new_node->data) root->right = BST_insert(root->right, new_node); return root; } double sumNlevels_helper(BST_Node *root, int level, int cur_level) { if (root == NULL) { return 0.0; } // if (cur_level > level) { // do we need this? it depends // return 0.0; // } if (cur_level == level) { return root->data; } // still need work -- USE RECURSION return root->data + sumNlevels_helper(root->left, level, cur_level + 1) + sumNlevels_helper(root->right, level, cur_level + 1); } /* Works on a BST that contains floating point values. Computes and returns the sum of all entries in the BST that occupy nodes between the root and level K (where root is at level 0, so if K is 3, it adds up any entries in nodes within the first 4 levels of the tree). */ double sum_Nlevels(BST_Node *root, int level) { // if (level < 0) return 0.0; // return sumNlevels_helper(root, level, 0); if (root == NULL) { return 0.0; } if (level < 0) { return 0.0; } if (level == 0) { return root->data; } // level > 0 return root->data + sum_Nlevels(root->left, level - 1) + sum_Nlevels(root->right, level - 1); } int main() { // TREE: // 50 LEVEL 0 // 45 85 LEVEL 1 // 38 49 72 92 LEVEL 2 // 10 40 69 LEVEL 3 // 12 LEVEL 4 BST_Node *n = new_BST_Node(50.0); n = BST_insert(n, n); BST_Node *a = new_BST_Node(45.0); n = BST_insert(n, a); a = new_BST_Node(49.0); n = BST_insert(n, a); a = new_BST_Node(85.0); n = BST_insert(n, a); a = new_BST_Node(38.0); n = BST_insert(n, a); a = new_BST_Node(40.0); n = BST_insert(n, a); a = new_BST_Node(10.0); n = BST_insert(n, a); a = new_BST_Node(12.0); n = BST_insert(n, a); a = new_BST_Node(72.0); n = BST_insert(n, a); a = new_BST_Node(92.0); n = BST_insert(n, a); a = new_BST_Node(69.0); n = BST_insert(n, a); double sumK = sum_Nlevels(n, 0); printf("actual=%f, expected=50\n", sumK); sumK = sum_Nlevels(n, 1); printf("actual=%f, expected=180\n", sumK); sumK = sum_Nlevels(n, 2); printf("actual=%f, expected=431\n", sumK); sumK = sum_Nlevels(n, 3); printf("actual=%f, expected=550\n", sumK); sumK = sum_Nlevels(n, 4); printf("actual=%f, expected=562\n", sumK); sumK = sum_Nlevels(n, 5); // bad input? don't want to crash though! printf("actual=%f, expected=562\n", sumK); sumK = sum_Nlevels(n, -1); // bad input? don't want to crash though! printf("actual=%f, expected=0.0\n", sumK); // Suppose we pass on some BST to this function and find out that it doesn't return the correct sum. // How do we trace it to figure out where this happens? // However this is done (either with their preferred debug tool, or with print statements), they need to have access to: // The sequence order for each call in the recursion (recursion depth, level, or whatever you want to call this) // - Which subproblem the recursion is working on // - Any partial information the function has to work with (argument passed into the function, if any) // - The actual data this recursive call will work with (e.g. if it's adding, what is it adding at this level? // is it looking in the right place?) // - Any values returned from recursive calls made at this level // - And the value it's going to return to the parent call return 0; }
Editor is loading...