In computer science, a binary tree is a k-ary,
k=2 tree data structure in which each node has at most two children,
which are referred to as the left child and the right child.Here we have demonstared the binary tree, binary search tree and max heap.
In binary search tree the left child is smaller than the parent and right child is greater than the parent.It is also applicable for all subtrees.
In the other hand in max heap both the children are smaller than their parent and it is a complete binary tree.It is also applicable for all subtress.
//SEARCH A NODE IN BINARY TREE
#include<bits/stdc++.h>
using namespace std;
// Binary tree node
struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Function to traverse the tree in preorder
// and check if the given node exists in it
bool ifNodeExists(struct Node* node, int key)
{
if (node == NULL)
return false;
if (node->data == key)
return true;
/* then recur on left subtree */
bool res1 = ifNodeExists(node->left, key);
// node found, no need to look further
if(res1) return true;
/* node is not found in left,
so recur on right subtree */
bool res2 = ifNodeExists(node->right, key);
return res2;
}
// Driver Code
int main()
{
struct Node* root = new Node(0);
root->left = new Node(1);
root->left->left = new Node(3);
root->left->left->left = new Node(7);
root->left->right = new Node(4);
root->left->right->left = new Node(8);
root->left->right->right = new Node(9);
root->right = new Node(2);
root->right->left = new Node(5);
root->right->right = new Node(6);
int key = 4;
if (ifNodeExists(root, key))
cout << "YES";
else
cout << "NO";
return 0;
}
// C++ program to demonstrate the use of priority_queue
#include<bits/stdc++.h>
using namespace std;
// driver code
int main()
{
int arr[6] = { 10, 2, 4, 8, 6, 9 };
// defining priority queue
priority_queue pq;
// printing array
cout << "Array: ";
for (auto i : arr) {
cout << i << ' ';
}
cout << endl;
// pushing array sequentially one by one
for (int i = 0; i < 6; i++) {
pq.push(arr[i]);
}
// printing priority queue
cout << "Priority Queue: ";
while (!pq.empty()) {
cout << pq.top() << ' ';
pq.pop();
}
return 0;
}
//SEARCH IN BINARY SEARCH TREE
#include<bits/stdc++.h>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node* newNode(int item)
{
struct node* temp
= new struct node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to insert
// a new node with given key in BST
struct node* insert(struct node* node, int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
// Return the (unchanged) node pointer
return node;
}
// Utility function to search a key in a BST
struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}
int main()
{
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Key to be found
int key = 6;
// Searching in a BST
if (search(root, key) == NULL)
cout << key << " not found" << endl;
else
cout << key << " found" << endl;
key = 60;
// Searching in a BST
if (search(root, key) == NULL)
cout << key << " not found" << endl;
else
cout << key << " found" << endl;
return 0;
}