Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
210-Coursework/BinarySearchTree.cpp
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
111 lines (111 sloc)
2.52 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
class BinTreeNode | |
{ | |
public: | |
BinTreeNode(int value) | |
{ | |
this->value = value; | |
this->left = NULL; | |
this->right = NULL; | |
} | |
int value; | |
BinTreeNode* left; | |
BinTreeNode* right; | |
}; | |
BinTreeNode* tree_insert(BinTreeNode* tree, int item) | |
{ | |
if (tree == NULL) | |
tree = new BinTreeNode(item); | |
else if (item < tree->value) | |
if (tree->left == NULL) | |
tree->left = new BinTreeNode(item); | |
else | |
tree_insert(tree->left, item); | |
else if (tree->right == NULL) | |
tree->right = new BinTreeNode(item); | |
else | |
tree_insert(tree->right, item); | |
return tree; | |
} | |
void postorder(BinTreeNode* tree) | |
{ | |
if (tree->left != NULL) | |
postorder(tree->left); | |
if (tree->right != NULL) | |
postorder(tree->right); | |
std::cout << tree->value << std::endl; | |
} | |
void in_order(BinTreeNode* tree) | |
{ | |
if (tree->left != NULL) | |
in_order(tree->left); | |
std::cout << tree->value << std::endl; | |
if (tree->right != NULL) | |
in_order(tree->right); | |
} | |
BinTreeNode* FindMin(BinTreeNode* tree) | |
{ | |
if(tree == NULL) | |
{ | |
std::cout<<"Error: Tree is empty\n"; | |
} | |
while(tree->left != NULL) | |
{ | |
tree = tree->left; | |
} | |
return tree; | |
} | |
BinTreeNode* tree_delete(BinTreeNode* tree, int item) | |
{ | |
if(tree==NULL) return tree; | |
else if(item < tree->value) | |
tree->left=tree_delete(tree->left,item); | |
else if(item > tree->value) | |
tree->right=tree_delete(tree->right,item); | |
else | |
{ | |
if(tree->left == NULL && tree->right == NULL) | |
{ | |
delete tree; | |
tree = NULL; | |
return tree; | |
} | |
else if(tree->left == NULL) | |
{ | |
BinTreeNode* temp= tree; | |
tree = tree->right; | |
delete temp; | |
return tree; | |
} | |
else if(tree->right == NULL) | |
{ | |
BinTreeNode* temp= tree; | |
tree = tree->left; | |
delete temp; | |
return tree; | |
} | |
else | |
{ | |
BinTreeNode* temp = FindMin(tree->right); | |
tree->value = temp->value; | |
tree->right=tree_delete(tree->right,temp->value); | |
} | |
} | |
return tree; | |
} | |
int main(int argc, char *argv[]) | |
{ | |
BinTreeNode* t = tree_insert(0, 6); | |
tree_insert(t, 10); | |
tree_insert(t, 5); | |
tree_insert(t, 2); | |
tree_insert(t, 3); | |
tree_insert(t, 4); | |
tree_insert(t, 11); | |
in_order(t); | |
tree_delete(t,2); | |
in_order(t); | |
tree_delete(t,6); | |
in_order(t); | |
return 0; | |
} |