What\'s the problem with my Add function? Other functions seens working well, bu
ID: 665849 • Letter: W
Question
What's the problem with my Add function? Other functions seens working well, but there is problem in print array in binary search tree.
---------------------------------------------------------------------------------------------------------------
Main.c
---------------------------------------------------------------------------------------------------------------
#include
#include
#include "type.h"
#include "BST.h"
int main (int argc, const char * argv[])
{
int i;
int ary[20] = { 54, 78, 19, 86, 53, 44, 58, 79, 15, 11, 10, 43, 57, 44, 64, 49, 77, 78, 55, 84};
BST* t = newBST();
Task firstTask, secondTask, thirdTask, fourthTask;
firstTask.name = "blarg";
firstTask.priority = 11;
secondTask.name = "foo";
secondTask.priority = 34;
thirdTask.name = "bar";
thirdTask.priority = 23;
fourthTask.name = "scraz";
fourthTask.priority = 37;
addBST(t, thirdTask); printBST(t);
printf("contains(34) = %d ", containsBST(t, secondTask));
addBST(t, secondTask); printBST(t);
printf("contains(34) = %d ", containsBST(t, secondTask));
addBST(t, firstTask); printBST(t);
printf("contains(37) = %d ", containsBST(t, fourthTask));
addBST(t, fourthTask); printBST(t);
printf("contains(37) = %d ", containsBST(t, fourthTask));
removeBST(t, thirdTask); printBST(t);
removeBST(t, secondTask); printBST(t);
removeBST(t, fourthTask); printBST(t);
removeBST(t, firstTask); printBST(t);
for(i = 0; i < 20; ++i)
{
firstTask.priority = ary[i];
addBST(t, firstTask);
}
printBST(t);
printf(" ");
return 0;
}
---------------------------------------------------------------------------------------------------------------
BST.c
---------------------------------------------------------------------------------------------------------------
#include
#include
#include
#include "assert.h"
#include "type.h"
#include "BST.h"
/* ************************************************************************
Helper Functions
************************************************************************ */
/* This function allocates a node on the heap for use in the tree datastructure.
param: val value to store in the newly created node
post: the newly created node is allocated, initialized, and returned.
ret: a Node, allocated on the heap, storing the argument value
*/
Node* _createNode(TYPE val)
{
Node* newNode = (Node*) malloc(sizeof(Node));
assert(newNode!=0);
newNode->val = val;
newNode->left = newNode->right =0;
return newNode;
}
/* This function compares two tasks. Note that this function does NOT use
TYPE. This is because if we change TYPE, we will get a compile error on the
_compare function, making us remember to write a new one for that type.
param: left, right Items to be compared
ret: -1 if left < right
1 if left > right
0 otherwise
*/
int _compare(Task left, Task right)
{
if(left.priority < right.priority)
return -1;
else if(left.priority > right.priority)
return 1;
return 0;
}
/* ************************************************************************
Binary Search Tree Basic Functions
************************************************************************ */
/* This function can be used to initialize the data fields in the tree.
param: tree The tree to be initialized
post: tree's datafields are all initialized.
*/
void initBST(BST* tree)
{
tree->root = NULL;
tree->size = 0;
}
/* Allocate and initialize a binary search tree.
post: the newly created tree is allocated, initialized, and returned
ret: a newly created tree, allocated on the heap.
*/
BST* newBST()
{
BST* tree = (BST*)malloc(sizeof(BST));
assert(tree);
initBST(tree);
return tree;
}
/* Helper function used to free a subtree of the BST rooted at a particular node.
param: root Root of the subtree to be freed
pre: root is in the tree
post: all memory in the underlying tree structure is freed
*/
void _freeSubTreeBST(Node* root)
{
if(!root)
return;
_freeSubTreeBST(root->left);
_freeSubTreeBST(root->right);
free(root);
}
/* This function will free all the nodes in the argument tree. To be used with init.
param: tree Tree to have its nodes freed
post: tree has had its nodes freed
post: tree has had its datafields cleared
*/
void freeBST(BST* tree)
{
_freeSubTreeBST(tree->root);
tree->size = 0;
tree->root = 0;
}
/* This function will free all the nodes in the argument tree IN ADDITION to freeing the
datastructure pointer provided as well.
param: tree Tree to have its nodes freed and be freed
post: tree has had its nodes freed
post: tree has had its datafields cleared
post: tree has been freed
*/
void deleteBST(BST* tree)
{
freeBST(tree);
free(tree);
}
/* Helper function used to compute the height of a subtree rooted at a particular node.
param: root Root of the subtree to compute the height of
ret: The height of the subtree rooted at root
*/
int _heightOfSubTree(Node* root)
{
if(root==NULL)
{
return 0;
}
else
{
int leftDepth =_heightOfSubTree(root->left);
int rightDepth = _heightOfSubTree(root->right);
if (leftDepth > rightDepth)
{
return(leftDepth+1);
}
else
{
return(rightDepth+1);
}
}
}
/* This function computes the height of an argument BST
param: tree BST to have its height computed
ret: the height of the argument tree
*/
int heightBST(BST* tree)
{
return _heightOfSubTree(tree->root);
}
/* Helper function which stores a subtree rooted at root into the argument array.
param: root Root of the subtree to be stored in the array
param: index Index where the root should reside in the argument array
param: levelOrder Array where the tree is to be stored
post: levelOrder has the subtree rooted at root stored inside it.
*/
void _storeInArray(Node* root, int index, Node** levelOrder)
{
if (!root)
return;
levelOrder[index] = root;
_storeInArray(root->left, 2*index + 1, levelOrder);
_storeInArray(root->right, 2*index + 2, levelOrder);
}
/* Prints a BST to the console using a nice formatting.
param: tree Tree to be printed to the console
post: tree has been printed to the console
IMPORTANT NOTE! some input to this function pay cause exponential memory to be consumed
as a result of the tree in array storage scheme.
*/
void printBST(BST* tree)
{
int height = heightBST(tree);
int levelOrderSize = pow(2, height+1)-1;
int i, j, depth, lastDepth;
int leftSpace;
Node** levelOrder = (Node**)malloc(levelOrderSize*sizeof(Node*));
for(i = 0; i < levelOrderSize; ++i)
levelOrder[i] = NULL;
_storeInArray(tree->root, 0, levelOrder);
printf("***[ Size: %d Height: %d ]", tree->size, heightBST(tree));
lastDepth = -1;
leftSpace = 0;
for(i = 0; i <= height; ++i)
leftSpace = leftSpace * 2 + 1;
for(i = 0; i < levelOrderSize; ++i)
{
depth = log(i+1)/log(2);
if(lastDepth != depth)
{
leftSpace /= 2;
printf(" ");
for(j = 0; j < leftSpace; ++j)
printf(" ");
}
else
for(j = 0; j < leftSpace * 2 + 1; ++j)
printf(" ");
if(levelOrder[i])
printf("%d", levelOrder[i]->val.priority);
else
printf("??");
lastDepth = depth;
}
printf(" ");
free(levelOrder);
}
/* ************************************************************************
Bag Interface Functions (and Helpers)
************************************************************************ */
/* Add a node to the subtree rooted at the argument node
param: curr Root of the subtree where the node should be added.
param: val value to store in the new node when it is added
post: a node is allocated storing val, which has been added to the tree
ret: the node where we currently reside in the tree. Note that
this function is recursive, so as the function returns, we will
connect the tree together.
*/
Node* _addNodeToSubtree(Node* curr, TYPE val)
{
int c;
if(curr==0)
{
return _createNode(val);
}
else
{
c = _compare(val, curr->val);
if (c == 0 || c == -1)
{
curr->left = _addNodeToSubtree(curr->left,val);
}
else
{
curr->right= _addNodeToSubtree(curr->right,val);
}
}
return curr;
}
/* Adds a node to the BST
param: tree BST to have a node added to it
param: val value to store in the new node
post: a node, allocated on the heap, has been added to the BST storing val
*/
void addBST(BST* tree, TYPE val)
{
tree->root = _addNodeToSubtree(tree->root, val);
tree->size++;
}
/* Helper function which can be used to determine if a particular value is
present in the subtree rooted at the argument node.
param: curr Root of the subtree to search for the value
param: val value for which to search the the subtree
ret: 1 if the value is in the subtree, 0 otherwise
*/
int _containsSubTree(Node* curr, TYPE val)
{
while(curr!= NULL)
{
if(_compare(val,curr->val) ==0)
{
return 1;
}
else if(_compare(val,curr->val)==1)
{
curr = curr->right;
}
else if(_compare(val,curr->val)==-1)
{
curr= curr->left;
}
}
return 0;
}
/* This function can be used to determine if a particular value is present in the BST.
param: tree BST to search for the argument value
param: val Value to search for in the BST
ret: 1 if the value is in the BST, 0 otherwise
*/
int containsBST(BST* tree, TYPE val)
{
return _containsSubTree(tree->root, val);
}
/* This function is used to remove and deallocate the leftmost descendent of the argument node
param: curr The node whose leftmost descendent we wish to find
param: parent curr's parent, included to make the operation easier to perform
param: origAncestor the node on which the original leftmost call was given
post: the leftmost descendent of curr is removed from the tree and freed
ret: the value stored in the leftmost descendent of curr
*/
TYPE _removeLeftMost(Node* curr, Node* parent, Node* origAncestor)
{
TYPE removeThisVar;
struct Node *temp;
if(curr->left!=NULL)
{
_removeLeftMost(curr->left,curr,origAncestor);
return removeThisVar;
}
else
{
removeThisVar=curr->val;
origAncestor->val = removeThisVar;
if(origAncestor==parent)
{
temp= curr->right;
free(curr);
parent->right = temp;
}
else if(origAncestor!=parent)
{
temp= curr->right;
free(curr);
parent->left = temp;
}
else
{
free(curr);
parent->left=NULL;
}
return removeThisVar;
}
}
/* This function is used to remove a node from a subtree of the BST
param: curr The root of the subtree we are currently examining for the value
param: val The value to be removed from the subtree
post: a node containing val has been removed from the tree and freed
ret: the node where we currently reside in the tree.
Note that this function uses recursion to put the tree back together as stack
frames are removed.
*/
Node* _removeNodeFromSubtree(Node* curr, TYPE val)
{
struct Node *temp;
if(_compare(val, curr->val) == -1)
curr->left = _removeNodeFromSubtree(curr->left, val);
else if(_compare(val,curr->val)==1)
curr->right = _removeNodeFromSubtree(curr->right, val);
else
{
if (curr->right != NULL)
{
_removeLeftMost(curr->right, curr, curr);
return curr;
}
else
{
temp = curr->left;
free (curr);
return temp;
}
}
return curr;
}
/* This function is used to remove a node from the BST, if present.
param: tree The tree to search for the argument value
param: val the value to be removed from the tree.
post: if val is present in any of the nodes, it has been removed.
if not, nothing has happened
*/
void removeBST(BST* tree, TYPE val)
{
if(containsBST(tree, val))
{
tree->root = _removeNodeFromSubtree(tree->root, val);
tree->size--;
}
}
---------------------------------------------------------------------------------------------------------------
BST.h
---------------------------------------------------------------------------------------------------------------
#ifndef BINARY_SEARCH_TREE_INCLUDED
#define BINARY_SEARCH_TREE_INCLUDED 1
#include "type.h"
struct Node {
TYPE val;
struct Node* left;
struct Node* right;
};
typedef struct Node Node;
struct BinarySearchTree {
Node* root;
int size;
};
typedef struct BinarySearchTree BinarySearchTree;
typedef BinarySearchTree BST;
/* Basic Operations */
void initBST(BST* tree);
BST* newBST();
void freeBST(BST* tree);
void deleteBST(BST* tree);
int heightBST(BST* tree);
void printBST(BST* tree);
/* Bag Interface */
void addBST(BST* tree, TYPE val);
void removeBST(BST* tree, TYPE val);
int containsBST(BST* tree, TYPE val);
# endif
---------------------------------------------------------------------------------------------------------------
program run
---------------------------------------------------------------------------------------------------------------
Explanation / Answer
I think number of spaces between nodes must be calculated properly.
void printWhitespaces(int n){
for (int i = 0; i < n; i++)
printf(" ");
}
void print(Node** l, int level, int maxlevel){
int st = pow(2,level-1)-1;
int en = pow(2,level)-1;
int f = maxlevel - level;
int endgeLines = (int) Math.pow(2, (Math.max(f - 1, 0)));
int first_space = (int) Math.pow(2, (f)) - 1;
int between_space = (int) Math.pow(2, (f + 1)) - 1;
printWhitespaces(first_space);
for (int i = st; i <= st+en; i++){
if (l[i] == NULL)
printf("??");
else
printf("%d",l[i]);
printWhitespaces(between_space);
}
printf(" ");
}
void printBST(BST* tree){
int height = heightBST(tree);
int levelOrderSize = pow(2, height+1)-1;
Node** levelOrder = (Node**)malloc(levelOrderSize*sizeof(Node*));
for(i = 0; i < levelOrderSize; ++i)
levelOrder[i] = NULL;
_storeInArray(tree->root, 0, levelOrder);
printf("***[ Size: %d Height: %d ]", tree->size, heightBST(tree));
for (int i = 1; i < height; i++)
print(levelOrder,i,height);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.