1

I have been trying to write that ;

I will receive a certain number of inputs from a text file and it will continue until -1 -1 (first for student id and second for student grade)

For example;

121 40
456 50
445 60
123 70
677 80
546 90

My output will be the sorted list of student grades with their ids ( I did this. )

My program should also print the binary search tree in the following way (First number represents the student id, second number displays the grade and the number in parenthesis shows the parent node. L represents left child and R represents right child).

It means the output will be;

123 70
456 50 (70 L) 546 90 (70 R)
121 40 (50 L) 445 60 (50 R) 677 80 (90 L)

I wrote this code but there is something that I can not fix. The printParent() function should be fixed. It should print "\n" every level of tree.

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

struct node{
    struct node *left;
    int ID;
    int Grade;
    struct node *right;
};

struct node* newNode(int,int);
struct node* insertNode(struct node *node,int id,int grade);
void printTree(struct node *node);
void printParent(struct node*);

int main() {
    struct node *head = NULL;
    FILE *file = fopen("input.txt","r");
    int stdID,grade;
    while (!feof(file)) {
        fscanf(file,"%d %d",&stdID,&grade);
        if (stdID && grade == -1){
            break;}
        else
            head = insertNode(head,stdID,grade);
    }
    printTree(head);

    printf("\n");

    printf("%d %d\n",head->ID,head->Grade);

    printParent(head);


    printf("\n");

    fclose(file);
    return 0;
}
struct node* newNode(int id,int grade){
    struct node *newnode = malloc(sizeof(struct node));
    newnode->ID = id;
    newnode->Grade = grade;
    newnode->left = newnode->right = NULL;
    return newnode;
}
struct node* insertNode(struct node *node,int id,int grade){
    if (node == NULL)
        return newNode(id,grade);
    if ( grade < node->Grade)
        node->left = insertNode(node->left,id,grade);
    else if ( grade >= node->Grade)
        node->right = insertNode(node->right,id,grade);
    return node;
}
void printTree(struct node *node){

    if (node == NULL)
        return;
    printTree(node->left);
    printf("%d %d\n", node->ID,node->Grade);
    printTree(node->right);
}
void printParent(struct node *node){

    struct node *temp = node;

    if (temp == NULL)
        return;
    if (temp->left != NULL){
        printf("%d %d (%d L) ",temp->left->ID,temp->left->Grade,temp->Grade);
    }
    if (temp->right != NULL){
        printf("%d %d (%d R) ",temp->right->ID,temp->right->Grade,temp->Grade);
    }
    printParent(temp->left);
    printParent(temp->right);
}
  • You've not shown your code for the code that you need help with — `printLevelOrder()`. We don't write code for you; we'll help you fix what you've got. – Jonathan Leffler Nov 30 '17 at 16:08
  • I did not use printLevelOrder() it doesn't matter. printParent function should be fixed. –  Nov 30 '17 at 16:09
  • OK. I think you'll need to do the work that's involved in `printLevelOrder()` inside `printParent()` in order to know when you've dealt with all the entries in a given level. So, you'll need to do the BFS (breadth-first search) of the tree, possibly recording current pointer, child pointer and level in the queue. – Jonathan Leffler Nov 30 '17 at 16:15
  • Hmm but queue causes me to make a lot of changes in the code. –  Nov 30 '17 at 16:22
  • Yes. But you originally had an unimplemented `printLevelOrder()` function which is going to need to do the queuing required for a BFS. And it seems that you want your `printParent()` code to produce an output in level-order, and the standard algorithm for that is a BFS which uses a queue. – Jonathan Leffler Nov 30 '17 at 16:26
  • I edited my code printLevelOrder() is no longer in it but thank you for the idea. –  Nov 30 '17 at 16:28
  • Note that [`while (!feof(file))` is always wrong](https://stackoverflow.com/questions/5431941/). – Jonathan Leffler Nov 30 '17 at 16:32
  • the only problem is to print a new line for each level in the tree in function printparent :) –  Nov 30 '17 at 16:34
  • OK; solve it another way. Have fun. You need to know when you've reached the end of a level. In a more general case (more levels in the tree), you have to know when you've reached the RH end of a level. You shouldn't be calling `printParent()` recursively from the current node until all the nodes to the right of the current node in the current level have been printed. Try adding another 12 entries to your data file. – Jonathan Leffler Nov 30 '17 at 16:38
  • Ok.Thanks , i will try all. –  Nov 30 '17 at 16:39
  • Note that the data file presented gives you a wholly unbalanced tree; it comes in an order such that the only the right pointers are non-null. That means that each node is also on its own level, with no other nodes at the same level. – Jonathan Leffler Nov 30 '17 at 17:11
  • Also, why do you print the parent node's grade rather than the parent node's student ID in the `printParent()` function. It's not wrong, just unexpected. – Jonathan Leffler Nov 30 '17 at 19:12
  • It has to be done this way unfortunately. –  Nov 30 '17 at 20:24

1 Answers1

2

As noted in the comments, I think you need to be doing a breadth-first search (BFS), keeping track of levels so that you can output a newline when you transition between levels.

Here is code that does the job reasonably robustly. It uses a FIFO queue to record which nodes need processing. The queue is moderately robust, but it stops abruptly if asked to add an element for which there isn't room. Fixing that is doable, but modestly fiddly (dynamic memory allocation, but the hard part is handling the correct copying when the queue array grows but the indexes into the queue are not at the start, which would usually be the case).

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

struct node
{
    struct node *left;
    int ID;
    int Grade;
    struct node *right;
};

struct node *newNode(int, int);
struct node *insertNode(struct node *node, int id, int grade);
void printTree(struct node *node);
void printParent(struct node *);

int main(int argc, char **argv)
{
    const char *name = "input.txt";
    if (argc == 2)
        name = argv[1];
    struct node *head = NULL;
    FILE *file = fopen(name, "r");
    if (file == 0)
    {
        fprintf(stderr, "%s: failed to open file %s for reading\n", argv[0], name);
        return 1;
    }
    printf("File: %s\n", name);
    int stdID, grade;
    while (fscanf(file, "%d %d", &stdID, &grade) == 2)
    {
        if (stdID == -1 && grade == -1)
            break;
        printf("Read: %d %d\n", stdID, grade);
        head = insertNode(head, stdID, grade);
        //printf("Tree:\n");
        //printTree(head);
    }
    fclose(file);

    printf("Completed tree:\n");
    printTree(head);
    printf("\n");

    printf("%3d %3d\n", head->ID, head->Grade);
    printf("Parent tree:\n");
    printParent(head);
    printf("\n");

    return 0;
}

struct node *newNode(int id, int grade)
{
    struct node *newnode = malloc(sizeof(struct node));
    newnode->ID = id;
    newnode->Grade = grade;
    newnode->left = newnode->right = NULL;
    return newnode;
}

struct node *insertNode(struct node *node, int id, int grade)
{
    if (node == NULL)
        return newNode(id, grade);
    if (grade < node->Grade)
        node->left = insertNode(node->left, id, grade);
    else if (grade >= node->Grade)
        node->right = insertNode(node->right, id, grade);
    return node;
}

void printTree(struct node *node)
{
    if (node == NULL)
        return;
    printTree(node->left);
    printf("%3d %3d (0x%.12" PRIXPTR ": 0x%.12" PRIXPTR " - 0x%.12" PRIXPTR ")\n",
           node->ID, node->Grade,
           (uintptr_t)node, (uintptr_t)node->left, (uintptr_t)node->right);
    printTree(node->right);
}

/* Structures to manage BFS - breadth-first search */

struct bfs_node
{
    struct node *parent;
    struct node *child;
    char side[4];           /* "L" or "R" plus padding */
    int level;
};

enum { MAX_QUEUE_SIZE = 100 };
struct bfs_queue
{
    struct bfs_node q[MAX_QUEUE_SIZE];
    size_t q_head;
    size_t q_tail;
};

static void bfs_add(struct bfs_queue *q, struct node *parent, struct node *child, int level, char side)
{
    assert(q != 0 && parent != 0 && child != 0);
    assert(parent->left == child || parent->right == child);
    assert(side == 'L' || side == 'R');
    assert(q->q_head < MAX_QUEUE_SIZE && q->q_tail < MAX_QUEUE_SIZE);
    size_t next = (q->q_head + 1) % MAX_QUEUE_SIZE;
    if (next == q->q_tail)
    {
        fprintf(stderr, "Queue is full\n");
        exit(EXIT_FAILURE);
    }
    q->q[q->q_head] = (struct bfs_node){ .parent = parent, .child = child,
                                         .level = level, .side = { side, '\0' } };
    q->q_head = next;
}

static inline void bfs_init(struct bfs_queue *q)
{
    assert(q != 0);
    q->q_head = q->q_tail = 0;
}

static inline int bfs_empty(const struct bfs_queue *q)
{
    assert(q != 0);
    return (q->q_head == q->q_tail);
}

static struct bfs_node *bfs_remove(struct bfs_queue *q)
{
    if (q->q_tail == q->q_head)
    {
        fprintf(stderr, "cannot remove anything from an empty queue\n");
        exit(EXIT_FAILURE);
    }
    assert(q->q_head < MAX_QUEUE_SIZE && q->q_tail < MAX_QUEUE_SIZE);
    size_t curr = q->q_tail;
    q->q_tail = (q->q_tail + 1) % MAX_QUEUE_SIZE;
    return &q->q[curr];
}

void printParent(struct node *node)
{
    if (node == 0)
    {
        printf("Empty tree\n");
        return;
    }

    int level = 0;
    struct bfs_queue q;
    bfs_init(&q);

    if (node->left)
        bfs_add(&q, node, node->left, level + 1, 'L');
    if (node->right)
        bfs_add(&q, node, node->right, level + 1, 'R');

    printf("Level %d: %3d %3d", level, node->ID, node->Grade);

    while (!bfs_empty(&q))
    {
        struct bfs_node *data = bfs_remove(&q);
        assert(data != 0);
        if (data->level != level)
        {
            assert(data->level == level + 1);
            putchar('\n');
            level = data->level;
            printf("Level %d:", level);
        }
        struct node *child = data->child;
        assert(child != 0);
        if (child->left)
            bfs_add(&q, child, child->left, level + 1, 'L');
        if (child->right)
            bfs_add(&q, child, child->right, level + 1, 'R');
        //printf(" %3d %3d (%3d %s)", child->ID, child->Grade, data->parent->ID, data->side);
        printf(" %3d %3d (%3d %s)", child->ID, child->Grade, data->parent->Grade, data->side);
    }
    putchar('\n');
}

Note the code that reads data has been modified considerably, avoiding the feof() function, and also accepting command line file name rather than just a fixed file name — but defaulting to the original file name. It also reports errors if it fails to open the file. While reading, it reports the data it read. For debugging, printing the tree after each line can be helpful until you have it working OK. (The code was OK as posted.) I added the addresses to the printout; it helps identify/validate the tree structure.

On the given input file with the grades in order, you end up with a lop-sided tree with 6 levels (0..5):

File: input.original
Read: 121 40
Read: 456 50
Read: 445 60
Read: 123 70
Read: 677 80
Read: 546 90
Completed tree:
121  40 (0x7FCCD3C00340: 0x000000000000 - 0x7FCCD3C02780)
456  50 (0x7FCCD3C02780: 0x000000000000 - 0x7FCCD3C027A0)
445  60 (0x7FCCD3C027A0: 0x000000000000 - 0x7FCCD3C027C0)
123  70 (0x7FCCD3C027C0: 0x000000000000 - 0x7FCCD3C027E0)
677  80 (0x7FCCD3C027E0: 0x000000000000 - 0x7FCCD3C02800)
546  90 (0x7FCCD3C02800: 0x000000000000 - 0x000000000000)

121  40
Parent tree:
Level 0: 121  40
Level 1: 456  50 ( 40 R)
Level 2: 445  60 ( 50 R)
Level 3: 123  70 ( 60 R)
Level 4: 677  80 ( 70 R)
Level 5: 546  90 ( 80 R)

To get the output requested, you need a different input file:

123 70
456 50
546 90
121 40
445 60
677 80

This yields:

File: input.req
Read: 123 70
Read: 456 50
Read: 546 90
Read: 121 40
Read: 445 60
Read: 677 80
Completed tree:
121  40 (0x7F99B94027C0: 0x000000000000 - 0x000000000000)
456  50 (0x7F99B9402780: 0x7F99B94027C0 - 0x7F99B94027E0)
445  60 (0x7F99B94027E0: 0x000000000000 - 0x000000000000)
123  70 (0x7F99B9400340: 0x7F99B9402780 - 0x7F99B94027A0)
677  80 (0x7F99B9402800: 0x000000000000 - 0x000000000000)
546  90 (0x7F99B94027A0: 0x7F99B9402800 - 0x000000000000)

123  70
Parent tree:
Level 0: 123  70
Level 1: 456  50 ( 70 L) 546  90 ( 70 R)
Level 2: 121  40 ( 50 L) 445  60 ( 50 R) 677  80 ( 90 L)

Given the input file:

305 8
772 51
140 83
877 53
499 74
183 3
240 21
810 49
159 68
977 36
385 3
252 35
163 76
283 12
740 46
829 42
526 51
401 64
726 65
226 3
902 75

(generated using random numbers between 100 and 999 for the ID, and between 0 and 100 for the grade), the output is:

File: input-21.txt
Read: 305 8
Read: 772 51
Read: 140 83
Read: 877 53
Read: 499 74
Read: 183 3
Read: 240 21
Read: 810 49
Read: 159 68
Read: 977 36
Read: 385 3
Read: 252 35
Read: 163 76
Read: 283 12
Read: 740 46
Read: 829 42
Read: 526 51
Read: 401 64
Read: 726 65
Read: 226 3
Read: 902 75
Completed tree:
183   3 (0x7FE3795000A0: 0x000000000000 - 0x7FE379500140)
385   3 (0x7FE379500140: 0x000000000000 - 0x7FE379500260)
226   3 (0x7FE379500260: 0x000000000000 - 0x000000000000)
305   8 (0x7FE379500000: 0x7FE3795000A0 - 0x7FE379500020)
283  12 (0x7FE3795001A0: 0x000000000000 - 0x000000000000)
240  21 (0x7FE3795000C0: 0x7FE3795001A0 - 0x7FE3795000E0)
252  35 (0x7FE379500160: 0x000000000000 - 0x000000000000)
977  36 (0x7FE379500120: 0x7FE379500160 - 0x7FE3795001C0)
829  42 (0x7FE3795001E0: 0x000000000000 - 0x000000000000)
740  46 (0x7FE3795001C0: 0x7FE3795001E0 - 0x000000000000)
810  49 (0x7FE3795000E0: 0x7FE379500120 - 0x000000000000)
772  51 (0x7FE379500020: 0x7FE3795000C0 - 0x7FE379500040)
526  51 (0x7FE379500200: 0x000000000000 - 0x000000000000)
877  53 (0x7FE379500060: 0x7FE379500200 - 0x7FE379500080)
401  64 (0x7FE379500220: 0x000000000000 - 0x7FE379500240)
726  65 (0x7FE379500240: 0x000000000000 - 0x000000000000)
159  68 (0x7FE379500100: 0x7FE379500220 - 0x000000000000)
499  74 (0x7FE379500080: 0x7FE379500100 - 0x7FE379500180)
902  75 (0x7FE379500280: 0x000000000000 - 0x000000000000)
163  76 (0x7FE379500180: 0x7FE379500280 - 0x000000000000)
140  83 (0x7FE379500040: 0x7FE379500060 - 0x000000000000)

305   8
Parent tree:
Level 0: 305   8
Level 1: 183   3 (  8 L) 772  51 (  8 R)
Level 2: 385   3 (  3 R) 240  21 ( 51 L) 140  83 ( 51 R)
Level 3: 226   3 (  3 R) 283  12 ( 21 L) 810  49 ( 21 R) 877  53 ( 83 L)
Level 4: 977  36 ( 49 L) 526  51 ( 53 L) 499  74 ( 53 R)
Level 5: 252  35 ( 36 L) 740  46 ( 36 R) 159  68 ( 74 L) 163  76 ( 74 R)
Level 6: 829  42 ( 46 L) 401  64 ( 68 L) 902  75 ( 76 L)
Level 7: 726  65 ( 64 R)

I experimented with 200 grade records with no problem. There were 19 levels in the tree for that data, and the level with the most records had 28 records in it. It wasn't stressing the queue size, but it should have wrapped around the queue end at least once.

I'd probably add command line options to control whether to report on data as it is added, and whether to print the addresses when printing the tree, and such like. I'd also add code to free the tree, and then be ready to loop over more than one file if given many file names, or process standard input if given no files. However, that's stepping a bit outside the immediate problem.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278