RECURSIVE FUNCTION FOR TREE TRAVERSAL AND FIBONACCI
Code:
#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child, and a pointer to right
child */
struct Node {
int data;
struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* Given a binary tree, print its nodes according to the "bottom-up" postorder
traversal. */
void printPostorder(struct Node* node) {
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
cout << node->data << " ";
}
/* Given a binary tree, print its nodes in inorder */
void printInorder(struct Node* node) {
if (node == NULL)
return;
// first recur on left child
printInorder(node->left);
// then print the data of node
cout << node->data << " ";
// now recur on right child
printInorder(node->right);
}
/* Given a binary tree, print its nodes in preorder */
void printPreorder(struct Node* node) {
if (node == NULL)
return;
// first print data of node
cout << node->data << " ";
// then recur on left subtree
printPreorder(node->left);
// now recur on right subtree
printPreorder(node->right);
}
/* Driver program to test above functions */
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
Output:
ITERATION FUNCTION FOR TREE TRAVERSAL AND FIBONACCI
Code:
#include <bits/stdc++.h>
using namespace std;
// Tree Node structure
struct Node {
int data;
Node* left, * right;
Node(int data) {
this->data = data;
this->left = this->right = NULL;
}
};
// Iterative function to do Preorder traversal of the tree
void preorderIterative(Node* root) {
if (root == NULL)
return;
stack<Node*> st;
Node* curr = root;
// run till stack is not empty or current is not NULL
while (!st.empty() || curr != NULL) {
// Print left children while exist and keep pushing right into the stack.
while (curr != NULL) {
cout << curr->data << " ";
// If the right child exists, push it into the stack
if (curr->right)
st.push(curr->right);
// Move to the left child
curr = curr->left;
}
// We reach when curr is NULL, so we pop a right child from the stack
if (!st.empty()) {
curr = st.top();
st.pop();
}
}
}
// Driver Code
int main() {
// Constructing the tree
Node* root = new Node(10);
root->left = new Node(20);
root->right = new Node(30);
root->left->left = new Node(40);
root->left->left->left = new Node(70);
root->left->right = new Node(50);
root->right->left = new Node(60);
root->left->left->right = new Node(80);
// Performing preorder traversal
preorderIterative(root);
return 0;
}
Output:
MERGE SORT
Code:
#include<iostream>
using namespace std;
void swapping(int &a, int &b) {
// Swap the contents of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
// Display the elements of the array
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
// Size of left and right sub-arrays
nl = m - l + 1;
nr = r - m;
int larr[nl], rarr[nr]; // Temporary arrays for left and right sub-arrays
// Fill left and right sub-arrays
for(i = 0; i < nl; i++)
larr[i] = array[l + i];
for(j = 0; j < nr; j++)
rarr[j] = array[m + 1 + j];
i = 0; j = 0; k = l;
// Merge temp arrays back into the real array
while(i < nl && j < nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
} else {
array[k] = rarr[j];
j++;
}
k++;
}
// If there are any remaining elements in the left array
while(i < nl) {
array[k] = larr[i];
i++;
k++;
}
// If there are any remaining elements in the right array
while(j < nr) {
array[k] = rarr[j];
j++;
k++;
}
}
void mergeSort(int *array, int l, int r) {
// Divide the array into two halves and sort them
if(l < r) {
int m = l + (r - l) / 2;
// Recursively sort the first half
mergeSort(array, l, m);
// Recursively sort the second half
mergeSort(array, m + 1, r);
// Merge the two sorted halves
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; // Create an array with the given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
// Call mergeSort to sort the array
mergeSort(arr, 0, n - 1);
cout << "Array after Sorting: ";
display(arr, n);
return 0;
}
Output:
QUICK SORT
Code:
#include <iostream>
using namespace std;
// Partition function to place the pivot in its correct position
int partition(int arr[], int start, int end) {
int pivot = arr[start]; // Choosing the first element as pivot
int count = 0;
// Counting how many elements are smaller than or equal to the pivot
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot) {
count++;
}
}
// Place the pivot in its correct position
int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);
// Sorting the left and right parts of the pivot
int i = start, j = end;
while (i < pivotIndex && j > pivotIndex) {
while (arr[i] <= pivot) { i++; }
while (arr[j] > pivot) { j--; }
if (i < pivotIndex && j > pivotIndex) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
return pivotIndex; // Return the index of the pivot element
}
// QuickSort function
void quickSort(int arr[], int start, int end) {
if (start >= end) return; // Base case
// Partitioning the array and getting the pivot index
int p = partition(arr, start, end);
// Recursively sorting the left and right parts of the pivot
quickSort(arr, start, p - 1); // Sorting the left part
quickSort(arr, p + 1, end); // Sorting the right part
}
int main() {
int arr[] = { 9, 3, 4, 2, 1, 8 }; // Sample array
int n = 6;
// Calling quickSort to sort the array
quickSort(arr, 0, n - 1);
// Printing the sorted array
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output:
