This is what I\'m supposed to do: (Sorry this is so long, but it\'s really not h
ID: 3621833 • Letter: T
Question
This is what I'm supposed to do: (Sorry this is so long, but it's really not hard for someone experienced in C programming. My program is almost finished, I just need help with a few bug fixed.. PLEASE HELP!)
Objective:
Write a C program that takes as input a list of integers (in random order), stores the integers in a binary tree, and uses a recursive algorithm to search the tree for a particular value.
Background:
Although binary trees can be represented with arrays, we would still have to deal with some memory issues ( ie: we might need enough contiguous memory for an extremely large tree, what if the tree is dynamic? what if some nodes only have 1 child?).
A more efficient way of handling binary trees could be with the use of dynamically allocated structures for the nodes, which are linked together with pointers. For example, we could have the following:
typedef struct node Node;
typedef Node* NodePtr;
typedef Node* Tree;
struct node
{
int value;
NodePtr Left;
NodePtr Right;
};
The above structure also works nicely for recursive functions, especially when adding data to a tree, searching for data in a tree, and (most important) freeing a tree.
Specifications: PLEASE USE THE SAME FUNCTION NAMES AS BELOW TO SAVE ME CONFUSION :)
1. The program will read data from an input file "Data.txt" and store the data in a tree. (Note: Build a complete tree.)
2. The program will prompt the user for a value to search for in the tree.
3. The program will use a pre-order traversal to search for the given value. (Which sort function is best for a tree?)
4. If the value is found, the program will announce that to the user and will tell the user the value of the left and right child of the given number. If the value is not found, program will politely report the situation.
5. The program will have an abstract data type (ADT) for the tree, and will include (as a minimum) the following functions for the ADT:
a. void InsertInTree(int value, Tree T)
b. NodePtr SearchTree(int value, Tree T)
c. void DeleteTree(Tree T)
7. The program will follow good programming practices.
a. It will check for failures opening the files and will provide a graceful exit if a failure exists.
b. The program will have appropriate programmer-defined functions so that the main function
provides a highlight of the program.
This is what I have so far: I keep getting erros when trying to cimpile, also, I don't know how to make it display the left and right nodes after it finds the node I'm seraching for.
This is my tree.h file:
typedef struct node Node;
typedef Node*NodePtr;
typedef Node*Tree;
struct node
{
int value;
NodePtr Left;
NodePtr Right;
};
int ReadData(FILE*Data);
void InsertInTree(Tree tree, int item);
NodePtr SearchTree(NodePtr proot,int x);
void DeleteTree(NodePtr proot);
/*void prerder(nodeptr proot);
void inorder(nodeptr proot);
void posorder(nodeptr proot);*/
This is my tree.c file:
int ReadData(FILE*Data)
{
int x;
if(feof(Data))
return (-2);
fscanf(Data, "%d", &x);
printf("%d ",x);
return (x);
};
void InsertInTree(Tree tree, int item)
{
if( tree == NULL )
{
tree = (NodePtr)malloc(sizeof(struct node));
if( tree == 0 )
{
printf("Fatal error! ");
exit(1);
}
else
{
tree->value = item;
tree->Left = tree->Right = 0;
}
}
else if( item < tree->value )
InsertInTree( tree->Left, item);
else if(item => tree->value )
InsertInTree( tree->Right, item );
};
NodePtr SearchTree(int x)
{
NodePtr p;
p = &Tree;
if(p != NULL)
{
if(x < Tree -> data)
p = SearchTree(Tree -> Left,x);
else if(x > Tree -> data)
p = SearchTree(Tree -> Right,x);
}
return(p);
};
void DeleteTree(NodePtr proot)
{
if(proot!=NULL)
{
DeleteTree(proot->Left);
DeleteTree(proot->Right);
free(proot);
}
};
/*void prerder(nodeptr proot)
{
if(proot!=NULL)
{
printf("%3d",proot->data);
preorder(proot->Left);
preorder(proot->Right);
}
}
void inorder(nodeptr proot)
{
if(proot!=NULL)
{
inorder(proot->Left);
printf("%3d",proot->data);
inorder(proot->Right);
}
}
void posorder(nodeptr proot)
{
if(proot!=NULL)
{
posorder(proot->Left);
posorder(proot->Right);
printf("%3d",proot->data);
}
}
*/
This is my Proj4.c file:
#include
#include
#include "tree.h"
#include "tree.c"
using namespace std;
main()
{
int y, num;
FILE *Data;
y = ReadData(Data);
Data = fopen("Data.txt","r");
if(Data == NULL)
printf(" Input file data1 did not open, please check it. ");
exit(1);
while(1)
{
y = ReadData(Data);
if(y == -2)
break;
else
InsertInTree(y);
}
while(1)
{
NodePtr Ptr;
printf("What number would you like to find? (Press -2 to exit program) ");
scanf("%d", &num);
if (num == -2)
break;
else
{
Ptr = SearchTree(num);
if (Ptr ==NULL)
{
printf("The number you entered was not found. ");
}
else
{
printf("The number %d was found in the tree.", num);
}
}
}
DeleteTree(&Tree);