Reputation:
How to print level-order binary search tree with parent node
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);
}
Upvotes: 1
Views: 846
Answers (1)
Reputation: 753535
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.
Upvotes: 2
Related Questions
- Printing tree by levels?
- C Binary Search Tree Printing Values
- Print Simple Binary Search Tree in C
- Print level and nodes from a binary search tree
- Binary Search Tree print in order
- Binary tree, print out which level I am on
- Printing Binary Search Tree with numbered nodes
- Print binary tree in level order using only one extra pointer per node
- How to print level order tree (not binary) in C?
- In a tree data structure, display tree nodes level by level