Question

C++ tree program (do NOT use STRUCT, use classes)

   Program 1 Implement a Binary 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

PROGRAM 1
#include<bits/stdc++.h>
using namespace std;
char tree[10];
int rootnode(char key){
   if(tree[0] != '\0')
      cout<<"Tree already had root";
   else
      tree[0] = key;
   return 0;
}
int leftchild(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 rightchild(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 traversetree(){
   cout << "\n";
   for(int i = 0; i < 10; i++){
      if(tree[i] != '\0')
         cout<<tree[i];
      else
         cout<<"-";
   }
   return 0;
}
int main(){
   rootnode('A');
   rightchild('C', 2);
   leftchild('D', 0);
   rightchild('E', 1);
   rightchild('F', 2);
   traversetree();
   return 0;
}

PROGRAM 2

#include <iostream>
using namespace std;

// Data structure to store a Binary Tree node
struct Node
{
   int data;
   Node *left, *right, *next;

   // constructor
   Node(int data)
   {
       this->data = data;
       this->left = this->right = this->next = nullptr;
   }
};

// Function to print a given linked list
void printList(Node* head)
{
   while (head)
   {
       cout << head->data << " -> ";
       head = head->next;
   }

   cout << "null" << '\n';
}

// Recursive function to find the first node in next level of the root node
Node* findNextNode(Node* root)
{
   // base case
   if (root == nullptr || root->next == nullptr)
       return nullptr;

   // if left child of root's next node exists, return it
   if (root->next->left)
       return root->next->left;

   // if right child of root's next node exists, return it
   if (root->next->right)
       return root->next->right;

   // if root's next node is a leaf node, recur for root's next node
   return findNextNode(root->next);
}

// Recursive function to link nodes present in each level of a binary tree
// in the form of a linked list
void linkNodes(Node* root)
{
   // base case
   if (root == nullptr)
       return;

   // ensure that the nodes of the current level is linked before the nodes
   // of the next level
   linkNodes(root->next);

   // update the next pointer of root's left child to root's right child
   // if right child doesn't exist, link it to first node in the next level
   if (root->left) {
       root->left->next = (root->right)? root->right: findNextNode(root);
   }

   // update the next pointer of root's right child to first node
   // in the next level
   if (root->right) {
       root->right->next = findNextNode(root);
   }

   // recur for left and right subtree
   linkNodes(root->left);
   linkNodes(root->right);
}

int main()
{
   /* Construct below Tree
       1
       / \
       2   3
   / \   \
   4 5   6
   \   /
       7   8
   */

   Node* root = new Node(1);
   root->left = new Node(2);
   root->right = new Node(3);
   root->left->left = new Node(4);
   root->left->right = new Node(5);
   root->right->right = new Node(6);
   root->left->left->right = new Node(7);
   root->right->right->left = new Node(8);

   // link nodes at the same level
   linkNodes(root);

   // print the nodes
   Node* node = root;
   while (node)
   {
       // print current level
       printList(node);

       // find leftmost node of the next level
       if (node->left)
           node = node->left;
       else if (node->right)
           node = node->right;
       else
           node = findNextNode(node);
   }

   return 0;
}

PROGRAM 3

#include <iostream>
#include <string>

using namespace std;

template<typename T=string, typename Tl=int, typename Tr=int>
struct Node {
// tree node
struct Node<T,Tl,Tr>* p_left;
struct Node<T,Tl,Tr>* p_right;
T top;
Tl left;
Tr right;
Node (struct Node<T,Tl,Tr>* pl=nullptr, struct Node<T,Tl,Tr>* pr=nullptr,
const T& t=T(),const Tl& tl=Tl(),const Tr& tr=Tr()):
p_left(pl), p_right(pr), top(t), left(tl), right(tr){}
};

using tnode = struct Node<>;

int main() {
tnode n1 (nullptr,nullptr,string("+"), 1, 2);
tnode n2 (&n1, nullptr,string("*"), 0,0);
}
UPDATE 2, add smart pointer.

#include <iostream>
#include <string>
#include <memory>

using namespace std;

template<typename T=string, typename Tc=int>
class Node {
public:
Node (shared_ptr<Node> pl=nullptr,
shared_ptr<Node> pr=nullptr,
const T& t=T(),
const Tc& tl=Tc(),
const Tc& tr=Tc()):
p_left(pl), p_right(pr), v_top(t), v_left(tl), v_right(tr){}

~Node() {
cout<<"Calling destructor"<<endl;
}
private:
shared_ptr<Node> p_left;
shared_ptr<Node> p_right;
T v_top;
Tc v_left,v_right;
};

using tNode = Node<>;
using spNode = shared_ptr<tNode>;

spNode create_tree() {
spNode n0 = make_shared<tNode>(nullptr,nullptr,string("*"), 7, 3);
spNode n1 = make_shared<tNode>(nullptr,n0,string("+"), 5, 6);
spNode n2 = make_shared<tNode>(n1, nullptr,string("+"), 3,4);
return n2;
}

int main() {
spNode n2 = create_tree();
}