24th December 2022
The implementation of how to use PreOrder and PostOrder Traversals alongwith InOrder to generate a Tree.
#include <bits/stdc++.h>
#define fastio std::ios_base ::sync_with_stdio(false);std::cin.tie(NULL);std::cout.tie(NULL);std::cout << std::fixed << std::setprecision(25);
using namespace std;
template<typename T>
struct node{
T value;
struct node* left;
struct node* right;
};
struct node<int>* make_node(int val){
struct node<int>* node=(struct node<int>*)malloc(sizeof(struct node<int>));
if(node==NULL){
return NULL;
}
node->value=val;
node->left=NULL;
node->right=NULL;
return node;
}
int find_root(vector<int> in,int val){
int n=in.size();
for(int i=0;i<n;i++){
if(in[i]==val){
return i;
}
}
return -1;
}
struct node<int>* pre_to_in(vector<int> pre,vector<int> in,int l,int r){
static int ptr=0;
if(l>r){
return NULL;
}
int data=pre[ptr];
ptr++;
int ind=find_root(in,data);
struct node<int>* n1=make_node(data);
if(l==r){
return n1;
}
n1->left=pre_to_in(pre,in,l,ind-1);
n1->right=pre_to_in(pre,in,ind+1,r);
return n1;
}
void preOrd(struct node<int>* root){
if(root!=NULL){
cout<<root->value<<" ";
preOrd(root->left);
preOrd(root->right);
}
}
void inOrd(struct node<int>* root){
if(root!=NULL){
inOrd(root->left);
cout<<root->value<<" ";
inOrd(root->right);
}
}
struct node<int>* pos_and_in(vector<int> pos,vector<int> in,int l,int r){
static int it=r;
int data=pos[r];
it--;
if(l>r){
return NULL;
}
int ind=find_root(in,data);
struct node<int>* node=make_node(data);
if(l==r){
return node;
}
node->right=pos_and_in(pos,in,l,ind-1);
node->left=pos_and_in(pos,in,ind+1,r);
return node;
}
struct node<int>* pre_to_inorder(vector<int> pre,vector<int> in,int l,int r){
static int it=0;
if(l>r){
return NULL;
}
int data=pre[it];
it++;
int pos=find_root(in,data);
struct node<int>* nod=make_node(data);
if(l==r){
return nod;
}
nod->left=pre_to_inorder(pre,in,l,pos-1);
nod->right=pre_to_inorder(pre,in,pos+1,r);
return nod;
}
void posOrd(struct node<int>* root){
if(root!=NULL){
posOrd(root->left);
posOrd(root->right);
cout<<root->value<<" ";
}
}
int32_t main() {
fastio
vector<int> pre={
12, 23, 13, 100, 40, 50, 7
},ino={
13, 23, 100, 12, 50, 40, 7
},pos{
13,100,23,50,7,40,12
};
// struct node<int>* n1=pos_and_in(pre,ino,0,6);
// posOrd(n1);
// cout<<endl;
// preOrd(n1);
// cout<<endl;
// inOrd(n1);
// cout<<endl;
struct node<int>* n1=make_node(12);
struct node<int>* n2=make_node(23);
struct node<int>* n3=make_node(40);
n1->left=n2;
n1->right=n3;
struct node<int>* n4=make_node(7);
struct node<int>* n7=make_node(50);
n3->left=n4;
n3->right=n7;
struct node<int>* n5=make_node(100);
struct node<int>* n6=make_node(13);
n2->left=n6;
n2->right=n5;
posOrd(n1);
cout<<endl;
preOrd(n1);
cout<<endl;
inOrd(n1);
cout<<endl;
// struct node<int>* n1=make_node(100);
// if(n1==NULL){
// return -1;
// }
// cout<<n1->value<<endl;
// struct node<int>* n1=(struct node<int>*)malloc(sizeof(struct node<int>));
// n1->value=100;
// n1->left=NULL;
// n1->right=NULL;
cout<<"Hola Todo El Mundo!\n";
// return (int)'d';
return -5;
}
Comments
Post a Comment