Question

C++(screenshot output please) Part 2 - Tree programs

Program 1 Implement a tree using an array

Program 2 Implement a tree using linked list - pointer Binary Tree

Program 3 - Convert program 1 to a template

Answer 1

Answer-

Program 1 Implement a tree using an array-

// C++ implementation of tree using array
// numbering starting from 0 to n-1.
#include<bits/stdc++.h>
using namespace std;
char tree[10];
int root(char key)
{
   if(tree[0] != '\0')
       cout << "Tree already had root";
   else
       tree[0] = key;
   return 0;
}

int set_left(char key, int parent)
{
   if(tree[parent] == '\0')
       cout << "\nCan't set child at"
           << (parent * 2) + 1
           << " , no parent found";
   else
       tree[(parent * 2) + 1] = key;
   return 0;
}

int set_right(char key, int parent)
{
   if(tree[parent] == '\0')
       cout << "\nCan't set child at"
           << (parent * 2) + 2
           << " , no parent found";
   else
       tree[(parent * 2) + 2] = key;
   return 0;
}

int print_tree()
{
   cout << "\n";
   for(int i = 0; i < 10; i++)
   {
       if(tree[i] != '\0')
           cout << tree[i];
       else
           cout << "-";
   }
   return 0;
}

int main()
{
   root('A');
   //insert_left('B',0);
   set_right('C', 0);
   set_left('D', 1);
   set_right('E', 1);
   set_right('F', 2);
   print_tree();
   return 0;
}

Program 2 Implement a tree using linked list - pointer Binary Tree-

#include <iostream>
using namespace std;

struct nod {
nod *l, *r;
int d;
}*r = NULL, *p = NULL, *np = NULL, *q;

void create() {
int v,c = 0;
while (c < 6) {
if (r == NULL) {
r = new nod;
cout<<"enter value of root node\n";
cin>>r->d;
r->r = NULL;
r->l = NULL;
} else {
p = r;
cout<<"enter value of node\n";
cin>>v;
while(true) {
if (v< p->d) {
if (p->l == NULL) {
p->l = new nod;
p = p->l;
p->d = v;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left\n";
break;
} else if (p->l != NULL) {
p = p->l;
}
} else if (v >p->d) {
if (p->r == NULL) {
p->r = new nod;
p = p->r;
p->d = v;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right\n";
break;
} else if (p->r != NULL) {
p = p->r;
}
}
}
}
c++;
}
}

void inorder(nod *p) {
if (p != NULL) {
inorder(p->l);
cout<<p->d<<endl;
inorder(p->r);
}
}

void preorder(nod *p) {
if (p != NULL) {
cout<<p->d<<endl;
preorder(p->l);
preorder(p->r);
}
}

void postorder(nod *p) {
if (p != NULL) {
postorder(p->l);
postorder(p->r);
cout<<p->d<<endl;
}
}

int main() {
create();
cout<<" traversal in inorder\n";
inorder(r);
cout<<" traversal in preorder\n";
preorder(r);
cout<<" traversal in postorder\n";
postorder(r);
}

Program 3 - Convert program 1 to a template-

// C++ implementation of tree using array
// numbering starting from 0 to n-1.
#include<bits/stdc++.h>
using namespace std;
template<typename To, typename From>
To convert_to(From from) { return To::unimplemented_conversion; }
char tree[10];

int root(char key)
{
   if(tree[0] != '\0')
       cout << "Tree already had root";
   else
       tree[0] = key;
   return 0;
}

int set_left(char key, int parent)
{
   if(tree[parent] == '\0')
       cout << "\nCan't set child at"
           << (parent * 2) + 1
           << " , no parent found";
   else
       tree[(parent * 2) + 1] = key;
   return 0;
}

int set_right(char key, int parent)
{
   if(tree[parent] == '\0')
       cout << "\nCan't set child at"
           << (parent * 2) + 2
           << " , no parent found";
   else
       tree[(parent * 2) + 2] = key;
   return 0;
}

int print_tree()
{
   cout << "\n";
   for(int i = 0; i < 10; i++)
   {
       if(tree[i] != '\0')
           cout << tree[i];
       else
           cout << "-";
   }
   return 0;
}

int main()
{
   root('A');
   //insert_left('B',0);
   set_right('C', 0);
   set_left('D', 1);
   set_right('E', 1);
   set_right('F', 2);
   print_tree();
   return 0;
}