my current program print out the max height of binary search tree is working wel
ID: 665852 • Letter: M
Question
my current program print out the max height of binary search tree is working well, but when I take "+1" from function , it shows error. I want to show only height of subtree. What's problem when I take 1 from function?
---------------------------------------------------------------------------------------------------------------
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
---------------------------------------------------------------------------------------------------------------
What's problem with +1?
Explanation / Answer
The following are the problems with +1:
Core Dump
At the end of the output, you had got a core dump error.
A core dump is a file of a computer’s documented memory of when (the Point In Time PIT) a program or computer crashed. THis will record the exact millisecond during when the system crashed. The file consists of the recorded status of the working memory at an explicit time, usually close to when the system crashed or when the program ended abnormally. Analysing the core dump file will shed lights on what part of the code causing the memory errors and a possible solution.
When you compare the last 2 lines of the output ( given below):
7fff6fd7e000-7fff6fd7f000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Abort (core dumped)
The last 2 lines had the two system calls: vsdo and vsyscall
System calls get loaded at kernel boot-time.There is an array called interrupt descriptor table. It is an array made up of system calls produced at the time of booting - more likely to be executed at the boot sector. This table or vector is more or less like a pointer to the actual routines like function calls, methods etc. A Similar example would be sahred memory (shm) and semaphores (sem).
Consider a small program given below as an example:
getTimeOfDay() is a small routine that will get the time stamp of the day. This routine will involve few system calls that could cause core dump if not handled properly. Once you understand this example, the same concept can be applied to your larger program of BST (Binary Search Tree):
#include <stdlib.h>
#include <sys/syscall.h>
#include <sys/time.h> // to handle time related functions
void main(void)
{
struct ValueOfTime vot;
/* wrapp up the glibc */
gettimeofday(&vot, NULL);
/* Explicit syscall */
syscall(SYS_gettimeofday, &vot, NULL);
return 0;
}
The sequence of steps involved in executing the system call: getTimeOfDay:
In olden days, at the time when Red Hat Linux was still new, calling or invoking a syscall was a luxurious process as it costed so much memory and firm ware resources. Because at that time it was implemented as an interrupt. ( Similar to Interrupt 27H in DOS (Disk operating System). Interrupt 27H is higher priority interrupt. At the time of calling the syscall interface through the "int 0x80" instruction, the CPU would get indexed and then the OS would call the function gettimeofday(). The CPU would be forced to save state ( more likely in a stack PUSH operation) of execution just immediately before the system call gets executed by interrupting the system. Once the interrupt is completed the stack is popped and the state gets restored so that the OS execution can continue from where it was broken and branched out from.
Linux has 2 primary memory segments - division.They are User-space and kernel-space (userland, kernelland). The system call can put a hole in the segment that acts as a protective layer between the user and kernel memory spaces.
consider the following code snippet and try to replace the corresponding parts of your code with the following code:
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST {
int data;
struct BST *leftSubTree, *RightSubTree;
} vertex;
void insert(vertex *, vertex *);
void InOrderTraverse(vertex *);
void PreOrderTraverse(vertex *);
void PostOrderTraverse(vertex *);
vertex *search(vertex *, int, vertex **);
void main() {
int option;
char ans = 'N';
int key;
vertex *new_vertex, *root, *tmp, *guardian;
vertex *get_vertex();
root = NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do {
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your option :");
scanf("%d", &option);
switch (option) {
case 1:
do {
new_vertex = get_vertex();
printf(" Enter The Element ");
scanf("%d", &new_vertex->data);
if (root == NULL) /* Tree is not Created */
root = new_vertex;
else
insert(root, new_vertex);
printf(" Want To enter More Elements?(y/n)");
ans = getch();
} while (ans == 'y');
break;
case 2:
printf(" Enter Element to be searched :");
scanf("%d", &key);
tmp = search(root, key, &guardian);
printf(" guardian of vertex %d is %d", tmp->data, guardian->data);
break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf(" The InOrderTraverse display : ");
InOrderTraverse(root);
printf(" The PreOrderTraverse display : ");
PreOrderTraverse(root);
printf(" The PostOrderTraverse display : ");
PostOrderTraverse(root);
}
break;
}
} while (option != 4);
}
/*
Get new vertex
*/
vertex *get_vertex() {
vertex *temp;
temp = (vertex *) malloc(sizeof(vertex));
temp->leftSubTree = NULL;
temp->RightSubTree = NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(vertex *root, vertex *new_vertex) {
if (new_vertex->data < root->data) {
if (root->leftSubTree == NULL)
root->leftSubTree = new_vertex;
else
insert(root->leftSubTree, new_vertex);
}
if (new_vertex->data > root->data) {
if (root->RightSubTree == NULL)
root->RightSubTree = new_vertex;
else
insert(root->RightSubTree, new_vertex);
}
}
/*
This function is for searching the vertex from
binary Search Tree
*/
vertex *search(vertex *root, int key, vertex **guardian) {
vertex *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf(" The %d Element is Present", temp->data);
return temp;
}
*guardian = temp;
if (temp->data > key)
temp = temp->leftSubTree;
else
temp = temp->RightSubTree;
}
return NULL;
}
/*
This function displays the tree in InOrderTraverse fashion
*/
void InOrderTraverse(vertex *temp) {
if (temp != NULL) {
InOrderTraverse(temp->leftSubTree);
printf("%d", temp->data);
InOrderTraverse(temp->RightSubTree);
}
}
/*
This function displays the tree in PreOrderTraverse fashion
*/
void PreOrderTraverse(vertex *temp) {
if (temp != NULL) {
printf("%d", temp->data);
PreOrderTraverse(temp->leftSubTree);
PreOrderTraverse(temp->RightSubTree);
}
}
/*
This function displays the tree in PostOrderTraverse fashion
*/
void PostOrderTraverse(vertex *temp) {
if (temp != NULL) {
PostOrderTraverse(temp->leftSubTree);
PostOrderTraverse(temp->RightSubTree);
printf("%d", temp->data);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.