This is what I\'m supposed to do: (Sorry this is so long, but it\'s really not h

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);

Explanation / Answer

Here is the code I came up with. Minor errors do exist...the file read won't work for some reason I can't figure out, but the basics are there. Also, since there is no promise that they will only search for good numbers, you should put in a check to make sure the number is there. Here is the main.cpp: #include #include #include #include #include #include #include "tree.h" using namespace std; /* @author: Kayleigh Duncan @instuctor: Sarah Gothard @date: 6/6/09 */ void printAll( binaryTree& t ) { //cout data > x){ searchTree(seeker->left, x); } else if(seeker->data right, x); } else if(seeker->data == x){ return seeker; } } // insert // // Purpose: insert a node containing x into the search tree, if it does not already exists // // Precondition: properly initialized search tree exist and is referenced by the internal pointer root // Postcondition: if the value x is not in the tree, a node containing x is insert as a new leaf of the search tree // void binaryTree::insert( int x ) { InsertInTree(root, x); } /** insert inserts a new treeNode. If there are no other nodes, the node inserted is the parent. If the value being inserted is less than the parent's value, then the value is inserted to the left. Otherwise, it is inserted to the right. */ void binaryTree::InsertInTree(treeNode*& parent, const int &d){ if (parent == NULL){ parent = new treeNode(d); } else if (d data){ InsertInTree(parent->left, d); } else InsertInTree(parent->right, d); } // preorder // // Purpose: to display the tree nodes inorder // e.g. Tree Contents (preorder): 20 10 30 // e.g. Tree Contents (preorder): empty // // Precondition: the tree is properly initialized // Postcondition: none // // void binaryTree:: preorder() const { preorder(root); cout

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.