Note: use the github provided TOC for navigaing.
#include <iostream>
#include <array>
#include <span>
#include <string>
using namespace std;
class queue{
int *arr;
int f,r,cs,ms;
public:
queue(int ds=5){
arr = new int[ds];
cs = 0;
ms=ds;
f=0;
r=ms-1;
}
bool full(){
return cs==ms;
}
bool empty(){
return cs==0;
}
void push(int data){
if(!full()){
r = (r+1)%ms;
arr[r] = data;
cs++;
}
}
void pop(){
if(!empty()){
f = (f+1)%ms;
cs--;
}
}
int front(){
if(!empty()){
return arr[f];
}
}
~queue(){
if(arr!=NULL){
delete [] arr;
arr=NULL;
}
}
};
int main(){
queue q(100);
for(int i=0;i<6;i++){
q.push(i);
}
q.pop();
q.pop();
q.push(34);
while(!q.empty()){
cout<<q.front()<<", ";
q.pop();
}
}
#include<list> // doubly Linkedlist
class queue{
int cs;
list<int> l;
private:
queue(){
cs = 0;
}
bool is_empty(){
return cs==0;
}
void push(int data){
l.push_back(data);
cs++;
}
void pop(){
if(!is_empty()){
l.pop_front();
cs--;
}
}
int front(){
l.front();
}
};
int main(){
queue q;
for(int i=0;i<6;i++){
q.push(i);
}
// q.pop();
// q.pop();
// q.push(34);
while(!q.is_empty()){
cout<<q.front()<<", ";
q.pop();
}
}
ordering process in amazon, first order gets served first.
int main(){
queue<int> q;
for(int i=0;i<6;i++){
q.push(i);
}
q.pop();
q.pop();
q.push(34);
while(!q.is_empty()){
cout<<q.front()<<", ";
q.pop();
}
}
Its binary tree, because it can have max two children for every parent node. one is called left child and right child. non linear data structure/ hirerchical data structure. e.g: file structure in a computer.
class Node{
public:
int data;
Node * left;
Node * right;
Node(int d){
data = d;
left = right = NULL;
}
};
top down approach, algorithm is like,
// return type is node* as it will return address of the root node
node* buildTree(){
int d; //d means data
cin>>d;
if(d==-1){ // if the user encounters -1 then it will return NULL
return NULL;
}
node * root = new node(d); // creating the node 1st
root->left = buildTree(); // here you are assigning the user input to
// left sub tree
root->right = buildTree(); // same as right
return root;
}
if any node is NULL, then return, else 1st print the root data then recursively call left subtree and right subtree to print the data.
void print_bt(node* root){
if(root == NULL){ //if any node is NULL, then return
return;
}
//otherwise root/data->left->right
cout<<root->data; // 1st print the root data
print_bt(root->left); //recursively call left subtree and right subtree
print_bt(root->right); // to print the data.
}
Tree Traversal:
it is a process where we visit each node of a tree one times in some order.
here visiting means reading the data of the node.There are two type of tree traversal,
Code is as same as Preorder
just ordering of the print is changed.
void printIn(node*root){
if(root==NULL){
return;
}
//Otherwise Left -> data/Root-> Right
printIn(root->left);
cout<<root->data<<" ";
printIn(root->right);
}
void printPost(node*root){
if(root==NULL){
return;
}
//otherwise left->right->data/root
printPost(root->left);
printPost(root->right);
cout<<root->data<<" ";
}
int height(node*root){
if(root==NULL){
return 0;
}
int ls = height(root->left);
int rs = height(root->right);
return max(ls,rs)+1;
}
print_kth_level()
to print each level.
void print_kth_level(noe*root,int k){
if(root==NULL){
return;
}
if(k=1){
cout<<root->data<<" ";
return;
}
print_kth_level(root->left,k-1);
print_kth_level(root->right,k-1);
return;
}
void print_all_level(node*root){
int H = height(root);
for(int i=1;i<=H;i++){
print_all_level(root,i);
cout<<endl;
}
return;
}
this is how it works:
void bfs(node* root){
queue<node*> q;
q.push(root);
while(!q.empty()){
node* f = q.front();
cout<<f->data<<", ";
q.pop();
if(f->left){ // if f->left is not NULL
q.push(f->left);
}
if(f->right){
q.push(f->right);
}
}
return;
}
```cpp
#include
class node{ public: int data; nodeleft; noderight;
node(int d){ // constructer
data = d;
left = NULL;
right = NULL;
} };
node* buildTree(){ int d; cin»d;
if(d==-1){
return NULL;
}
node * root = new node(d);
root->left = buildTree();
root->right = buildTree();
return root; } void print(node *root){
if(root==NULL){
return;
}
//Otherwise, print root first followed by subtrees(children)
cout<<root->data<<" ";
print(root->left);
print(root->right); }
void printIn(node*root){ if(root==NULL){ return; } //Otherwise Left Root Right printIn(root->left); cout«root->data«” “; printIn(root->right); }
void printPost(noderoot){ if(root==NULL){ return; } printPost(root->left); printPost(root->right); cout«root->data«” “; } int height(noderoot){ if(root==NULL){ return 0; } int ls = height(root->left); int rs = height(root->right); return max(ls,rs)+1; } void print_kth_level(noeroot,int k){ if(root==NULL){ return; } if(k=1){ cout«root->data«” “; return; } print_kth_level(root->left,k-1); print_kth_level(root->right,k-1); return; } void print_all_level(noderoot){ int H = height(root); for(int i=1;i<=H;i++){ print_all_level(root,i); cout«endl; } return; } int main(){ node* root = buildTree(); print(root); cout«endl;
printIn(root);
cout<<endl;
printPost(root);
cout<<height(root);
print_kth_level(root,3);
print_all_level(root);
return 0; } ```