Reputation: 1
Search a Binary Tree And Print Children of Value
So I have spent many sleepless nights the last two weeks trying to work on what I thought would be a simple program: I am trying to create a Binary Tree from a list of integers in a specific file. The numbers are inserted into a binary tree. I then prompt user for a value to search for to see if is a node. If it is then I print the left and right child of the searched value. I unfortunately can not for the life of me to get my code to work. Any help is greatly appreciated!
#define kFileName "../../Data.txt"
struct Node {
int number;
struct Node *left, *right;
};
extern struct Node *gRootNodePtr;
void BuildTree( void );
int GetNumberFromFile( int *numPtr, FILE *fp );
void InsertInTree( int num );
void AddNode( struct Node *newNodePtr, struct Node **curNodePtrPtr );
void SearchTree( int num, struct Node *nodePtr );
void PrintChild( struct Node *nodePtr );
void InsertInTree(int num) {
struct Node *nodePtr;
nodePtr = malloc(sizeof(struct Node));
if (nodePtr == NULL)
DoError("Could not allocate memory!\n");
nodePtr->number = num;
nodePtr->left = NULL;
nodePtr->right = NULL;
AddNode(nodePtr, &gRootNodePtr);
}
void AddNode(struct Node *newNodePtr, struct Node **curNodePtrPtr) {
if (*curNodePtrPtr == NULL)
*curNodePtrPtr = newNodePtr;
else if (newNodePtr->number < (*curNodePtrPtr)->number)
AddNode(newNodePtr, &((*curNodePtrPtr)->left));
else
AddNode(newNodePtr, &((*curNodePtrPtr)->right));
}
void SearchTree(int num, struct Node *nodePtr) {
if (nodePtr == NULL)
return;
printf("Enter number to be searched: ");
scanf("%d", &num);
SearchTree(num, nodePtr);
PrintChild(nodePtr->left);
printChild(nodePtr->right);
}
void PrintChild( struct Node *nodePtr) {
printf("%d ", nodePtr->number);
}
void BuildTree(void) {
int num;
FILE *fp;
if ((fp = fopen( kFileName, "r")) == NULL)
printf("Could not read numbers file!\n");
printf("Numbers: ");
while (GetNumberFromFile( &num, fp )) {
printf("%d, ", num);
InsertInTree(num);
}
printf("\n-------\n");
fclose(fp);
}
int GetNumberFromFile(int *numPtr, FILE *fp)
{
if (fscanf(fp, "%d\n", numPtr) == EOF)
return false;
else
return true;
}
int main(int argc, char* argv[]) {
gRootNodePtr = NULL;
int num=NULL;
BuildTree();
NodePtr SearchTree(num, gRootNodePtr);
return;
}
Upvotes: 0
Views: 2509
Answers (7)
Reputation: 373
This is my code for binary tree and all of its operations in php:
<?php
class Node { public $data; public $leftChild; public $rightChild;
public function __construct($data) { $this->data=$data; $this->leftChild=null; $this->rightChild=null; } public function disp_data() { echo $this->data; }
}//end class Node class BinaryTree { public $root; //public $s; public function __construct() { $this->root=null; //$this->s=file_get_contents('store');
} //function to display the tree public function display() { $this->display_tree($this->root);
} public function display_tree($local_root) {
if($local_root==null)
return;
$this->display_tree($local_root->leftChild);
echo $local_root->data."
";
$this->display_tree($local_root->rightChild);
}
// function to insert a new node
public function insert($key)
{
$newnode=new Node($key);
if($this->root==null)
{
$this->root=$newnode;
return;
}
else
{
$parent=$this->root;
$current=$this->root;
while(true)
{
$parent=$current;
//$this->find_order($key,$current->data);
if($key==($this->find_order($key,$current->data)))
{
$current=$current->leftChild;
if($current==null)
{
$parent->leftChild=$newnode;
return;
}//end if2
}//end if1
else
{
$current=$current->rightChild;
if($current==null)
{
$parent->rightChild=$newnode;
return;
} //end if1
} //end else
}//end while loop
}//end else
} //end insert function
//function to search a particular Node public function find($key) { $current=$this->root; while($current->data!=$key) { if($key==$this->find_order($key,$current->data)) { $current=$current->leftChild; } else { $current=$current->rightChild; } if($current==null) return(null);
}
return($current->data);
}// end the function to search public function delete1($key) { $current=$this->root; $parent=$this->root;
$isLeftChild=true;
while($current->data!=$key)
{
$parent=$current;
if($key==($this->find_order($key,$current->data)))
{
$current=$current->leftChild;
$isLeftChild=true;
}
else
{
$current=$current->rightChild;
$isLeftChild=false;
}
if($current==null)
return(null);
}//end while loop
echo "<br/><br/>Node to delete:".$current->data;
//to delete a leaf node
if($current->leftChild==null&&$current->rightChild==null)
{
if($current==$this->root)
$this->root=null;
else if($isLeftChild==true)
{
$parent->leftChild=null;
}
else
{
$parent->rightChild=null;
}
return($current);
}//end if1
//to delete a node having a leftChild
else if($current->rightChild==null)
{
if($current==$this->root)
$this->root=$current->leftChild;
else if($isLeftChild==true)
{
$parent->leftChild=$current->leftChild;
}
else
{
$parent->rightChild=$current->leftChild;
}
return($current);
}//end else if1
//to delete a node having a rightChild
else if($current->leftChild==null)
{
if($current==$this->root)
$this->root=$current->rightChild;
else if($isLeftChild==true)
{
$parent->leftChild=$current->rightChild;
}
else
{
$parent->rightChild=$current->rightChild;
}
return($current);
}
//to delete a node having both childs
else
{
$successor=$this->get_successor($current);
if($current==$this->root)
{
$this->root=$successor;
}
else if($isLeftChild==true)
{
$parent->leftChild=$successor;
}
else
{
$parent->rightChild=$successor;
}
$successor->leftChild=$current->leftChild;
return($current);
}
}//end the function to delete a node //Function to find the successor node public function get_successor($delNode) { $succParent=$delNode; $successor=$delNode; $temp=$delNode->rightChild; while($temp!=null) { $succParent=$successor; $successor=$temp; $temp=$temp->leftChild; } if($successor!=$delNode->rightChild) { $succParent->leftChild=$successor->rightChild; $successor->rightChild=$delNode->rightChild; } return($successor); } //function to find the order of two strings public function find_order($str1,$str2) { $str1=strtolower($str1); $str2=strtolower($str2); $i=0; $j=0;
$p1=$str1[i];
$p2=$str2[j];
while(true)
{
if(ord($p1)
return($str1);
}
else
{
if(ord($p1)==ord($p2))
{
$p1=$str1[++$i];
$p2=$str2[++$j];
continue;
}
return($str2);
}
}//end while
} //end function find string order
public function is_empty() { if($this->root==null) return(true); else return(false); } }//end class BinaryTree ?>
Upvotes: 0
Reputation: 28693
I got your code compiled. It even does something. I tried not to touch it too much. Just to make it something , because there are no binary trees in your code and it is not clear what it is intended for. See the code below below. But before that: 1. You are not building a binary tree, you are building a linked list. Maybe, you need double-linked list of sorted numbers? If yes, the code I posted here doesn't sort it property, FYI. 2. Maybe, you are posting stack-overflow harmful code here specially, but you should care about user inputs, pointers and everything else (there were good answers from another user on this). 3. Finally, what do you want to do exactly?
Code
#include <stdio.h>
#include <malloc/malloc.h>
#define kFileName "Data.txt"
struct Node {
int number;
struct Node *left, *right;
};
struct Node *gRootNodePtr;
void BuildTree( void );
int GetNumberFromFile( int *numPtr, FILE *fp );
void InsertInTree( int num );
void AddNode( struct Node *newNodePtr, struct Node **curNodePtrPtr );
void SearchTree( int num, struct Node *nodePtr );
void PrintChild( struct Node *nodePtr );
void InsertInTree( int num ) {
struct Node *nodePtr;
nodePtr = (struct Node *) malloc( sizeof( struct Node ) );
if ( nodePtr == NULL ) {
printf("Could not allocate memory!\n" );
return;
}
nodePtr->number = num;
nodePtr->left = NULL;
nodePtr->right = NULL;
AddNode( nodePtr, &gRootNodePtr );
}
void AddNode( struct Node *newNodePtr, struct Node **curNodePtrPtr ) {
if ( *curNodePtrPtr == NULL )
*curNodePtrPtr = newNodePtr;
else if ( newNodePtr->number < (*curNodePtrPtr)->number )
AddNode( newNodePtr, &( (*curNodePtrPtr)->left ) );
else
AddNode( newNodePtr, &( (*curNodePtrPtr)->right ) );
}
void search(struct Node * nodePtr) {
int num;
printf("Enter number to be searched: ");
scanf("%d", &num);
SearchTree(num, nodePtr);
}
void SearchTree(int num, struct Node *nodePtr ) {
if ( nodePtr == NULL )
return;
if(num == nodePtr->number) {
if(nodePtr->left != NULL) PrintChild(nodePtr->left);
PrintChild(nodePtr);
if(nodePtr->right != NULL) PrintChild(nodePtr->right);
printf("\n");
return;
} else if(num > nodePtr->number) {
SearchTree(num, nodePtr->right);
} else {
SearchTree(num, nodePtr->left);
}
}
void PrintChild( struct Node *nodePtr ) {
printf( "%d ", nodePtr->number );
}
void BuildTree( void )
{
int num;
FILE *fp;
if ( ( fp = fopen( "Data.txt", "r" ) ) == NULL )
printf( "Could not read numbers file!\n" );
printf( "Numbers: " );
while ( GetNumberFromFile( &num, fp ) )
{
printf( "%d, ", num );
InsertInTree( num );
}
printf( "\n-------\n" );
fclose( fp );
}
int GetNumberFromFile( int *numPtr, FILE *fp )
{
if ( fscanf( fp, "%d\n", numPtr ) == EOF )
return false;
else
return true;
}
int main(int argc, char* argv[])
{
gRootNodePtr = NULL;
BuildTree();
search(gRootNodePtr);
return;
}
Upvotes: 0
Reputation: 26586
Without delving into your code, here's how one usually does a search on a BST recursively:
(Pseudocode)
visit(node,value):
if node is null: // empty tree
return
if node->key==value: // found one
// do whatever it is you want to do with it
if node->key<=value: // less than or equal keys are to the left
visit(node->left,value)
else: // greater keys are to the right
visit(node->right,value)
Upvotes: 0
Reputation: 490128
Here's one that's enough different that it isn't just giving you the answer directly, but similar enough that it might provide some help and/or inspiration. Just for grins, this demonstrates both recursive and iterative tree traversal.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
struct node *left;
struct node *right;
char *string;
} node;
node *root; /* automatically initialized to NULL */
node *make_node(char const *string) {
node *ret = malloc(sizeof(node));
if (ret == NULL)
return NULL;
ret->string = malloc(strlen(string) + 1);
if (ret->string == NULL) {
free(ret);
return NULL;
}
strcpy(ret->string, string);
ret->left = NULL;
ret->right = NULL;
return ret;
}
void del_node(node *node) {
free(node->string);
free(node);
}
int insert(const char *string, node **root) {
if (*root == NULL)
*root = make_node(string);
else {
node *iter = *root;
for(;;) {
int cmp = strcmp(string, iter->string);
if ( 0 == cmp)
/* duplicate string - ignore it. */
return 0;
else if (1 == cmp) {
if (NULL == iter->right ) {
iter->right = make_node(string);
break;
}
else iter=iter->right;
}
else if ( NULL == iter->left ) {
iter->left = make_node(string);
break;
}
else
iter = iter->left;
}
}
return 1;
}
void print(node *root) {
if (root->left != NULL )
print(root->left);
fputs(root->string, stdout);
if ( root->right != NULL )
print(root->right);
}
int main() {
char line[100];
while (fgets(line, 100, stdin))
insert(line, &root);
print(root);
return 0;
}
Upvotes: 1
Reputation: 28839
You're not saying exactly how it doesn't work, but it's pretty clear that you shouldn't prompt for the value to search for from within your recursive SearchTree routine.
Other than that, it looks like you're fairly close. Try something like this:
void SearchTree( int num, struct Node *nodePtr ) {
if ( nodePtr == NULL )
return;
if (NodePtr->Number == num)
{
PrintChild( nodePtr->left );
PrintChild( nodePtr->right );
}
else
{
SearchTree(num, nodePtr->left );
SearchTree(num, nodePtr->right );
}
}
Upvotes: 0
Reputation: 6957
The SearchTree error may stem from its usage in main(). What's NodePtr doing there? SearchTree is declared void. Also, your integer from pointer may be due to your usage of NULL, which can be (void*)0. Use
int num = 0;
Upvotes: 0
Reputation: 108938
Go in little steps.
Create a new function PrintLeaves. With the needed changes, modify your main to
int main() {
InsertInTree(42);
PrintLeaves();
return 0;
}
and tweak it until you get the 42 printed.
Then add a few more random InsertInTree ... and tweak ...
Upvotes: 0
Related Questions
- Searching for a number inside a tree
- How to write a recursive function to search for a key in a binary tree using in-order traversal in C?
- Searching recursive data structure in C
- Tree + Recursion
- Search recursively in binary tree in C
- Binary Search Tree Nothing Getting Printed
- C - Searching for a number in a binary search tree
- binary tree recursively search c code [not Binary Search Tree]
- C: binary tree searching method
- Recursion for binary search trees