All are here

RobertDeMilo

Dec 12th, 2023

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 7.55 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
};
Node* GetNewNode(int data)
{
Node* newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = nullptr;
return newNode;
}
//void Insert(Node** root, int data)
//{
// if (*root == nullptr)
// {
// *root = GetNewNode(data);
// }
//}
Node* Insert(Node* root, int data)
{
if (root == nullptr)
{
root = GetNewNode(data);
}
else if (data <= root->data)
{
root->left = Insert(root->left, data);
}
else
{
root->right = Insert(root->right, data);
}
return root;
}
bool Search(Node* root, int data)
{
if (root == nullptr)
{
return false;
}
else if (root->data == data)
{
return true;
}
else if (data <= root->data)
{
return Search(root->left, data);
}
else
{
return Search(root->right, data);
}
}
////////////////////////////////////////////////////////////////////2
int FindMin(Node* root)
{
if (root == nullptr)
{
cout << "Error: Tree is empty\n";
return -1;
}
while (root->left != nullptr)
{
root = root->left;
}
return root->data;
/*Node* current = root;
while (current->left != nullptr)
{
current = current->left;
}
return current->data;*/
}
int FindMinRec(Node* root)
{
if (root == nullptr)
{
cout << "Error: Tree is empty\n";
return -1;
}
else if (root->left == nullptr)
{
return root->data;
}
return FindMinRec(root->left);
}
////////////////////////////////////////////////////////////////////3
int FindHeight(Node* root)
{
if (root == nullptr)
{
return -1;
}
return std::max(FindHeight(root->left), FindHeight(root->right)) + 1;
}
////////////////////////////////////////////////////////////////////4
void LevelOrder(Node* root)
{
if (root == nullptr)
{
return;
}
queue<Node*> Q;
Q.push(root);
while (!Q.empty())
{
Node* current = Q.front();
cout << current->data << " ";
if (current->left != nullptr)
{
Q.push(current->left);
}
if (current->right != nullptr)
{
Q.push(current->right);
}
Q.pop();
}
}
////////////////////////////////////////////////////////////////////5
void Preorder(Node* root)
{
if (root == nullptr)
{
return;
}
cout << root->data << " ";
Preorder(root->left);
Preorder(root->right);
}
void Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
Inorder(root->left);
cout << root->data << " ";
Inorder(root->right);
}
void Postorder(Node* root)
{
if (root == nullptr)
{
return;
}
Postorder(root->left);
Postorder(root->right);
cout << root->data << " ";
}
////////////////////////////////////////////////////////////////////6
bool IsSubTreeLesser(Node* root, int value)
{
if (root == nullptr)
{
return true;
}
if (root->data <= value
&& IsSubTreeLesser(root->left, value)
&& IsSubTreeLesser(root->right, value))
{
return true;
}
else
{
return false;
}
}
bool IsSubTreeGreater(Node* root, int value)
{
if (root == nullptr)
{
return true;
}
if (root->data > value
&& IsSubTreeGreater(root->left, value)
&& IsSubTreeGreater(root->right, value))
{
return true;
}
else
{
return false;
}
}
bool IsBinarySearchTree(Node* root)
{
if (root == nullptr)
{
return true;
}
if (IsSubTreeLesser(root->left, root->data)
&& IsSubTreeGreater(root->right, root->data)
&& IsBinarySearchTree(root->left)
&& IsBinarySearchTree(root->right))
{
return true;
}
else
{
return false;
}
}
//bool IsBstUtil(Node* root, int minValue, int maxValue)
//{
// if (root == nullptr)
// {
// return true;
// }
// if (root->data < minValue && root-> data > maxValue
// && IsBstUtil(root->left, minValue, root->data)
// && IsBstUtil(root->right, root->data, maxValue))
// {
// return true;
// }
// else
// {
// return false;
// }
//}
//bool IsBinarySearchTree(Node* root)
//{
// return IsBstUtil(root, INT_MIN, INT_MAX);
//}
////////////////////////////////////////////////////////////////////7
Node* FindMIN(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
else if (root->left == nullptr)
{
return root;
}
return FindMIN(root->left);
}
Node* Delete(Node* root, int data)
{
if (root == nullptr)
{
return root;
}
else if (data < root->data)
{
root->left = Delete(root->left, data);
}
else if (data > root->data)
{
root->right = Delete(root->right, data);
}
else
{ // case 1: No child
if (root->left == nullptr && root->right == nullptr)
{
delete root;
root = nullptr;
//return root;
}
// case 2: One child
else if (root->left == nullptr)
{
Node* temp = root;
root = root->right;
delete temp;
//return root;
}
else if (root->right == nullptr)
{
Node* temp = root;
root = root->left;
delete temp;
//return root;
}
// case 3: Two children
else
{
Node* temp = FindMIN(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}
////////////////////////////////////////////////////////////////////8
Node* Findmin(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
while (root->left != nullptr)
{
root = root->left;
}
return root;
}
Node* GetSuccessor(Node* root, int data)
{
Node* current = Find(root, data);//Search?
if (current == nullptr)
{
return nullptr;
}
if (current->right != nullptr)
{
return Findmin(current->right);
}
else
{
Node* succesor = nullptr;
Node* ancestor = root;
while (ancestor != current)
{
if (current->data < ancestor->data)
{
succesor = ancestor;
ancestor = ancestor->left;
}
else
{
ancestor = ancestor->right;
}
}
return succesor;
}
}
int main()
{
Node* root = nullptr;
/*Insert(&root, 15);
Insert(&root, 10);
Insert(&root, 20);*/
root = Insert(root, 15);
root = Insert(root, 10);
root = Insert(root, 20);
root = Insert(root, 25);
root = Insert(root, 8);
root = Insert(root, 12);
int number;
cout << "Enter number be searched\n";
cin >> number;
if (Search(root, number) == true)
{
cout << "Found\n";
}
else
{
cout << "Not Found\n";
}
return 0;
}

Add Comment

Please, Sign In to add comment