D. Lamkin D. Lamkin - 8 months ago 58
C Question

Printing Binary Search Tree with numbered nodes

I want to do an InOrder traversal of a BST and print the nodes. I can print the tree just fine but I can't get the numbering right.

Here is all the code if anyone wants to compile and give it a shot. Thank you!

#include <time.h>
#include <stdlib.h>
#include <stdio.h>



struct Node_h {
int start_addr;
int size;

struct Node_h* left;
struct Node_h* right;
};

struct Node_h* newHoleNode(int st, int size) {
struct Node_h* tmp = (struct Node_h*)malloc(sizeof(struct Node_h));
tmp->start_addr = st;
tmp->size = size;
tmp->left = NULL;
tmp->right = NULL;
return tmp;
}

int compare(struct Node_h* lhs, struct Node_h* rhs) {
if(lhs->size != rhs->size)
return (lhs->size < rhs->size) ? -1 : 1;
else if(lhs->start_addr == rhs->start_addr)
return 0;
else
return (lhs->start_addr < rhs->start_addr) ? -1 : 1;
}

struct Node_h* insertHole(struct Node_h* cur, struct Node_h* add) {
/* If the tree is empty, return a new node */
if (cur == NULL)
return add;

/* Otherwise, recur down the tree */
if (compare(add, cur) == -1) {
cur->left = insertHole(cur->left, add);
}
else if(compare(add, cur) == 1) {
cur->right = insertHole(cur->right, add);
}

/* return the (unchanged) node pointer */
return cur;
}

int printHoles(struct Node_h* cur, int num) {
if(cur == NULL) {
return 0;
}
int t = 1 + num;
t += printHoles(cur->left, num);
printf("Hole %d: start location = %d, size = %d\n", t, cur->start_addr, cur->size);
t += printHoles(cur->right, t);
return t;
}

int main(int argc, char const *argv[]) {
srand(time(NULL)); // should only be called once
int pid = 0;
struct Node_h* root = NULL;
for (int i = 0; i < 1000; ++i) {
int size = rand() % 10000;
root = insertHole(root, newHoleNode(pid++, size));
}
printHoles(root, 0);
return 0;
}


The numbering is always either massive random +/- numbers or something like that. Help!

Hole 1: start location = 168, size = 12

Hole 2: start location = 665, size = 12

Hole 4: start location = 506, size = 14

Hole 5: start location = 908, size = 30

Hole 11: start location = 498, size = 31

Hole 13: start location = 340, size = 38

Hole 14: start location = 378, size = 44

Hole 29: start location = 303, size = 54

Hole 30: start location = 948, size = 58

Hole 60: start location = 503, size = 70

Answer Source
// num is the number of nodes printed so far
// return the number of nodes printed so far
int printHoles(struct Node_h* cur, int num) {
    if(NULL == cur) {
        // last printed not changed
        return num;
    }
    num = printHoles(cur->left, num);
    printf("%d. size = %d\n", num + 1, cur->size);
    num = printHoles(cur->right, num + 1);
    return num;
}

We can use num to track the number of nodes printed so far. Without using t this should be clearer and correct.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download