I am new to c, but for a project I am implementing a binary tree. here is my code for the functions:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BSTnode{
int key;
int subtree_size;
struct BSTnode* left;
struct BSTnode* right;
} TreeNode;
TreeNode* newNode(int value){
TreeNode *node = malloc(sizeof(TreeNode));
node->key = value;
node->left = NULL;
node->right = NULL;
node->subtree_size = 1;
return node;
}
TreeNode* insert(TreeNode* root, TreeNode* to_insert){
if(root == NULL){
root = newNode(to_insert->key);
}
else if(to_insert->key> root->key){
if(root->right == NULL){
root->right = to_insert;
return root;
}
else{
root->right = insert(root->right, to_insert);
}
}
else if(to_insert->key< root->key){
if(root->left == NULL){
root->left = to_insert;
return root;
}
root->left = insert(root->left, to_insert);
}
root->subtree_size = 1 + (root->left? root->left->subtree_size: 0) + (root->right? root->right->subtree_size: 0);
return root;
}
int find(TreeNode* root, int value){
if(root == NULL || root->key == value){
return root->key;
}
else if(value > root->key){
return find(root->right, value);
}
else{
return find(root->left, value);
}
}
In my main function, I am reading from a file that contaqins a number on each line that I have to insert into the BST. Each line starts with a letter followed by the number seperated by the space.
int main (int argc, char* argv[]){
FILE* input;
input = fopen(argv[1], "r");
char oper;
int num;
TreeNode* root = NULL;
while(fscanf(input, "%c", &oper) != EOF){
if(oper == 'i'){
fscanf(input, " %d\n", &num);
TreeNode* to_insert = newNode(num);
insert(root, to_insert);
//printf("operation: %c, num: %d\n", oper, num);
}
if(oper == 'r'){
//do some other thing
}
}
if(root == NULL){
printf("yes\n");
}
printf("size: %d\n", root->subtree_size);
printf("left size: %d\n", root->left->subtree_size);
printf("right size: %d\n", root->right->subtree_size);
fclose(input);
}
Running the code prints "yes" then it gives me a seg fault. I have seen another post about a similar problem and the solution was to change the insert function to take in a double pointer for root. Does that work here? Id so, what would it look like? I am not really good with double pointers.
Edit 1: assume fscanf()
and the input file are properly used and opened.
Edit2: the input file would look like this:
i 10
i 20
i 30
i 40
i 50
i 60
i 70
i 80
i 90
i 99
i 15
i 14
i 12
i 25
i 28
i 95
i 35
i 38
i 11
i 23
i 22
Your problem:
Your insert()
function returns root
. But you never assign the return value to anything, at least not in your main()
:
TreeNode* root = NULL;
while(fscanf(input, "%c", &oper) != EOF){
// ...
insert(root, to_insert);
Your root
always stays NULL
.
How I found out:
gcc -Wall -Wextra -g testme.c -o testme
gdb -tui --args ./testme input.txt
break main
run
And then "n" for next (step over) and "s" for step (step in). Either learn to use gdb from there, or familiarize yourself with a different debugger of your choosing. Doing software development without a debugger is hard. Don't try it.
My fix:
I abhor double pointers. Luckily, there's a simple fix to your problem. In insert()
, for the first node received, don't newNode()
, just take the node you're given:
if(root == NULL){
root = to_insert;
}
And in main()
, assign the return value to root:
TreeNode* to_insert = newNode(num);
root = insert(root, to_insert);
Yet to do:
Note that your program leaks all the memory it allocated.
You need to check root
for NULL
before accessing root->left
and root->right
(in case you didn't read any data), and you need to check either of those for NULL
again before accessing their respective ...->subtree_size
(in case you, as with your example data, have no data at all in one subtree).