Reputation: 21
Binary Search Tree Nothing Getting Printed
I'm trying to create an unbalanced Binary Search Tree from a given input as a sequence of (unsorted) integers.
My approach has been to recursively find the right place for each individual node and then allocate memory for it and define the data for it.
But I'm unable to debug the program effectively as despite having scrutinized it properly,I can't seem to identify the problem. For an input as follows:
11
15 6 4 8 5 3 1 10 13 2 11
The Expected output should have been the post-order and in-order traversals,but strangely nothing is getting printed(Except for the newline I've given in between).
NOTE: This question is closely linked to the BST related question that I previously asked,but the approach is entirely different and so is the challenges I'm facing. Hence think twice before going for my neck and probably closing down the topic.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrmax 100
/***Pointer-based BST implementation, developed by Abhineet Saxena***/
/***The data-type declaration***/
typedef struct node{
int data;
struct node* parent;
struct node* leftChild;
struct node* rightChild;
}Node;
typedef struct tree
{
Node* root;
int size;
}BSTree;
/***Method prototypes***/
/*Method to create a tree*/
Node* createTree(int[],int,int);
void insert(Node*,int);
Node* createNode(int);
void inOrder(Node* root);
void postOrder(Node *root);
int main(void) {
BSTree* bs_tree;
bs_tree=malloc(sizeof(BSTree));
bs_tree->root=NULL;
bs_tree->size=0;
/****Taking the input****/
int num_elem,iterv;
scanf("%d\n",&num_elem);
int *arr=malloc(sizeof(int)*(num_elem));
for(iterv=0;iterv<num_elem;iterv++)
{
scanf("%d",&arr[iterv]);
}
bs_tree->root=createTree(arr,0,num_elem-1);
postOrder(bs_tree->root);
printf("\n");
inOrder(bs_tree->root);
return 0;
}
Node* createTree(int marr[],int left,int right)
{
int iterv;
Node* root;
root=NULL;
// Node** root_ptr;
//*root_ptr=root;
for(iterv=left;iterv<=right;iterv++)
{
insert(root,marr[iterv]);
}
return root;
}
Node* createNode(int key)
{
Node* tree_node;
tree_node=malloc(sizeof(Node));
//printf("Used malloc here for key: %d\n",key);
tree_node->data=key;
tree_node->leftChild=NULL;
tree_node->rightChild=NULL;
tree_node->parent=NULL;
return tree_node;
}
void insert(Node* root,int key)
{
if(root==NULL)
{
root=createNode(key);
//return root;
}
else if(root->leftChild!=NULL && root->rightChild!=NULL)
{
if(key<root->data)
insert(root->leftChild,key);
else
insert(root->rightChild,key);
}
else if(root->leftChild!=NULL && root->rightChild==NULL)
{
if(key>root->data)
{
Node* tnode=createNode(key);
root->rightChild=tnode;
tnode->parent=root;
return;
}
else if(key<root->data)
insert(root->leftChild,key);
}
else if(root->leftChild==NULL && root->rightChild!=NULL)
{
if(key<root->data)
{
Node* tnode=createNode(key);
root->leftChild=tnode;
tnode->parent=root;
return;
}
else if(key>root->data)
insert(root->rightChild,key);
}
else
{
if(key<root->data)
{
Node* tnode=createNode(key);
root->leftChild=tnode;
tnode->parent=root;
return;
}
else if(key>root->data)
{
Node* tnode=createNode(key);
root->rightChild=tnode;
tnode->parent=root;
return;
}
}
}
void inOrder(Node* bst_tree)
{
if(bst_tree!=NULL)
{
inOrder(bst_tree->leftChild);
printf("%d ",bst_tree->data);
inOrder(bst_tree->rightChild);
}
else
return;
}
void postOrder(Node* bst_tree)
{
if(bst_tree!=NULL)
{
postOrder(bst_tree->leftChild);
postOrder(bst_tree->rightChild);
printf("%d ",bst_tree->data);
}
else
return;
}
Upvotes: 0
Views: 44
Answers (2)
Reputation: 5388
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrmax 100
/***Pointer-based BST implementation, developed by Abhineet Saxena***/
/***The data-type declaration***/
typedef struct node{
int data;
struct node* parent;
struct node* leftChild;
struct node* rightChild;
}Node;
typedef struct tree
{
Node* root;
int size;
}BSTree;
/***Method prototypes***/
/*Method to create a tree*/
Node* createTree(int[],int);
void insert(Node*,int);
Node* createNode(int);
void inOrder(Node* root);
void postOrder(Node *root);
int main(void) {
BSTree* bs_tree;
bs_tree=(BSTree*)malloc(sizeof(BSTree));
bs_tree->root=NULL;
bs_tree->size=0;
/****Taking the input****/
int num_elem,iterv=0;
printf("Enter Number of Elements\n");
scanf("%d\n",&num_elem);
int *arr=(int*)malloc(sizeof(int)*num_elem);
for(;iterv<num_elem;iterv++){
printf("Enter keys\n");
scanf("%d",&arr[iterv]);
}
bs_tree->root=createTree(arr,num_elem-1);
postOrder(bs_tree->root);
printf("\n");
inOrder(bs_tree->root);
return 0;
}
Node* createTree(int marr[],int right){
Node* root =createNode(marr[0]);
int iterv=1;
for( ;iterv<=right;iterv++){
insert(root,marr[iterv]);
}
return root;
}
Node* createNode(int key){
Node* tree_node;
tree_node=(Node*)malloc(sizeof(Node));
tree_node->data=key;
tree_node->leftChild=NULL;
tree_node->rightChild=NULL;
tree_node->parent=NULL;
return tree_node;
}
void insert(Node* root,int key){
if(root->leftChild!=NULL && root->rightChild!=NULL){
if(key<root->data)
insert(root->leftChild,key);
else
insert(root->rightChild,key);
}
else if(root->leftChild!=NULL && root->rightChild==NULL){
if(key>root->data){
Node* tnode=createNode(key);
root->rightChild=tnode;
tnode->parent=root;
return;
}
else if(key<root->data)
insert(root->leftChild,key);
}
else if(root->leftChild==NULL && root->rightChild!=NULL){
if(key<root->data){
Node* tnode=createNode(key);
root->leftChild=tnode;
tnode->parent=root;
}
else if(key>root->data)
insert(root->rightChild,key);
}
else{
if(key<root->data){
Node* tnode=createNode(key);
root->leftChild=tnode;
tnode->parent=root;
return;
}
else if(key>root->data){
Node* tnode=createNode(key);
root->rightChild=tnode;
tnode->parent=root;
return;
}
}
}
void inOrder(Node* bst_tree){
if(bst_tree!=NULL){
inOrder(bst_tree->leftChild);
printf("%d ",bst_tree->data);
inOrder(bst_tree->rightChild);
}
else
return;
}
void postOrder(Node* bst_tree)
{
if(bst_tree!=NULL)
{
postOrder(bst_tree->leftChild);
postOrder(bst_tree->rightChild);
printf("%d ",bst_tree->data);
}
else
return;
}
//Check this code is working .
Upvotes: 0
Reputation: 4314
Your problem is this one: in createTree, you set root to NULL and then call
insert(root, marr[iterv]);
...and now magically expect root to be non-NULL after it. You need to change to this calling convention:
insert(&root, marr[iterv]);
...and change the signature of insert to void insert(Node**,int);
Then, in the insert function, instead of root you use *root, and instead of root->something you use (*root)->something. I tested your program with these changes and it works.
An additional nitpick: integer ranges should be left-inclusive and right-exclusive so you should call createTree in this way:
bs_tree->root=createTree(arr,0,num_elem);
and then have this loop:
for(iterv=left;iterv<right;iterv++)
Then the length of the range is right-left which is more convenient.
Upvotes: 1
Related Questions
- Binary search tree in C. Program not working.
- C Binary Search Tree Printing Values
- C - recursion not working in a Binary Search Tree
- How to fix error where a node in a tree is not being printed
- Binary Search Tree Difficulties
- C - Binary Search Tree - Print in Order Doesn't Print Anything (Double check my pointers)
- C - Searching for a number in a binary search tree
- Unable to print Binary Search Tree
- C: binary tree searching method
- binary search tree code not working