Code : Binary Search Tree C++

In summary, the znode structure contains data and a pointer to another znode structure that describes the left and right subtrees of the node. The insert function inserts a new node into the tree, while the zremove_min function deletes the lowest-valued node from the tree.
  • #1
Hamonic
1
0
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
struct znode // binary search tree node
{
int data; // data type is integer
struct znode * left; // left subtree
struct znode * right; // right subtree
};

struct znode * root = NULL; // root node, initially NULL

void print_tree_inorder(struct znode* tree) // print tree in inorder (left -> parent -> right)
{
if (tree == NULL)
printf("Tree is empty!\n");
else
{
if (tree->left != NULL)
print_tree_inorder(tree->left);
printf("%d ", tree->data);
if (tree->right != NULL)
print_tree_inorder(tree->right);
};
}

struct znode* insert(int insert_data, struct znode* tree) // node insert
{
if (tree == NULL) // if null, make new node
{
tree = (struct znode *)malloc(sizeof(struct znode));
tree->data = insert_data;
tree->left = NULL;
tree->right = NULL;
}
else if (insert_data < tree->data) // insert data in left subtree
tree->left = insert(insert_data, tree->left);
else if (insert_data > tree->data)
tree->right = insert(insert_data, tree->right); // insert data in right subtree
else
printf("Insert Error : item duplicated!\n"); // when the item already exists

return tree;
}

struct znode* zremove_min(struct znode* tree) // delete minimum-valued node
{
struct znode* temp = tree;

if (tree == NULL)
printf("remove Minimum Error : null tree!\n");
else if (tree->left != NULL)
tree->left = zremove_min(tree->left); // traverse to left and left again
else
{
tree = tree->right; // attach right subtree(or NULL) to parent
free(temp); // and remove the old parent
}

return tree;
}

struct znode* zremove(int remove_data, struct znode* tree) // delete node
{
struct znode* temp = tree;

if (tree == NULL)
printf("remove Error : item not found!\n");
else if (remove_data < tree->data) // delete data in left subtree
tree->left = zremove(remove_data, tree->left);
else if (remove_data > tree->data)
tree->right = zremove(remove_data, tree->right); // delete data in right subtree
else if (tree->left != NULL && tree->right != NULL)
// if this has both left and rihgt subtree
{
temp = temp->right;
while (temp->left != NULL)
temp = temp->left; // find the minimum data of right subtree
tree->data = temp->data; // and set it to the parent
tree->right = zremove_min(tree->right); // and remove it in right subtree
}
else
{
tree = (tree->left != NULL) ? tree->left : tree->right;
// attach one of two children to parent (tree or NULL)
free(temp); // free the old parent
}

return tree;
}

int main()
{
FILE* fp;
char buffer[11];

fp = fopen("index.txt", "r");
while (fgets(buffer, 10, fp) != NULL) // read one line from index.txt
{
printf("\ninsert %d : ", atoi(buffer));
root = insert(atoi(buffer), root); // insert it
print_tree_inorder(root); // and print the current tree shape
}
fclose(fp);

fp = fopen("index.txt", "r"); // close and reopen
while (fgets(buffer, 10, fp) != NULL)
{
printf("\ndelete %d : ", atoi(buffer));
root = zremove(atoi(buffer), root); // delete a node
print_tree_inorder(root); // and print
}
fclose(fp);

getch();
};
};

Compiling 0001.CPP:
Error 0001.CPP 16: Declaration syntax error in function main()
Warning 0001.CPP 119: 'root' is assigned a value that is never used in function main()



Help Me !


Edit and modifier
 
Technology news on Phys.org
  • #2
In the future, please embed your code in code tags so that we can see the structure of your code.

kind of like this:
Code:
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
struct znode                        // binary search tree node
{
       int data;                        // data type is integer
       struct znode * left;                        // left subtree
       struct znode * right;                        // right subtree
};
...
int main()
{
};
};
Why are you declaring main at the very top and wrapping all functions inside of main? You cannot embed a function within a function in C++.

For a start, get rid of that initial "void main(){". I also suggest you switch to using C++ I/O rather than C I/O and C++ new/delete rather than malloc.
 
  • #3
main() is never void; it returns an int. Always. That is the C and C++ standard.

Plus, if this isn't an assignment, consider the standard library function bsearch().

The STL aslo has a binary search.
 
Last edited:
  • #4
The OP has problems much more basic than "void main" versus "int main". That that "void main" is pedantically incorrect is secondary to the fact that it is completely incorrect. The biggest problem, embedding one function definition inside another, is much worse than going against the standard. Many compilers will compile a program that declares main as void. I don't know any C compiler that will compile code in which a function is defined internal to some outer function (and if some compiler does do that the language is no longer C/C++).

Besides, the OP does define a function "int main" (internal to the erroneous "void main" declaration).
 
  • #5
I agree, DH, the OP's code has lots of problems. However start with what you learn on day one. Then go ahead from there.

That one thing "pedantic" thing speaks volumes about how wrell the OP is learning or being taught to code. I didn't get past the void main().

So in that sense I REALLY disagree with you. IMO, the OP may need to go back to Hello World. I think the the OP missed day one in class.. Your correcting what he posted will not help much, except maybe to get his coding assignment done. Wrong. There is nothing more basic than int main(). Period the end. YMMV.
 
  • #6
Void main functions are actually pretty common on Windows machines. Loosen your grip a little jim.

The real problem here is that the OP is trying to put functions inside one another, when they should be peers.

- Warren
 
  • #7
bu kod c++ değil c aga
 
  • #8
chroot said:
Void main functions are actually pretty common on Windows machines. Loosen your grip a little jim.

The real problem here is that the OP is trying to put functions inside one another, when they should be peers.

- Warren
Amen to that Warren and D H.
 

What is a binary search tree?

A binary search tree is a data structure in computer science that is used to store and organize data in a hierarchical manner. It is a type of binary tree where each node has at most two child nodes, and the values of all the nodes in the left subtree are smaller than the value of the parent node, while the values in the right subtree are greater than the parent node.

How do you insert data into a binary search tree in C++?

To insert data into a binary search tree in C++, you first need to create a new node with the data you want to insert. Then, starting at the root node, you compare the value of the new node with the value of the current node. If the value is smaller, you go to the left subtree, and if it is larger, you go to the right subtree. You continue this process until you reach an empty spot, where you can insert the new node.

What is the time complexity of searching in a binary search tree?

The time complexity of searching in a binary search tree is O(log n), where n is the number of nodes in the tree. This is because at each step, you are able to eliminate half of the remaining nodes in the tree, making the search more efficient than a linear search.

How do you delete a node from a binary search tree in C++?

To delete a node from a binary search tree in C++, you first need to find the node that you want to delete. Then, you need to handle three cases: 1. If the node has no children, simply delete the node.2. If the node has one child, replace the node with its child.3. If the node has two children, find the successor (the smallest value in the right subtree), replace the node with the successor, and delete the successor from its original position.

What is the difference between a binary search tree and a binary heap?

A binary search tree is a data structure used for storing and organizing data in a hierarchical manner, while a binary heap is a data structure used for implementing a priority queue. The main difference between the two is that a binary search tree maintains the property of a parent node having a smaller value than its children, while a binary heap does not have any specific ordering between parent and child nodes. Additionally, binary heaps are usually implemented as arrays, while binary search trees are implemented as linked lists.

Similar threads

  • Programming and Computer Science
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Programming and Computer Science
Replies
3
Views
3K
  • Programming and Computer Science
Replies
14
Views
3K
  • Programming and Computer Science
Replies
20
Views
4K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
11
Views
3K
Back
Top