On the first line, there will be a single number, N, showing the number of nodes

Question

On the first line, there will be a single number, N, showing the number of nodes in the tree. On the next N lines, the i h line contains the data and the left and right child of the i h node, for example if the 5 h of the N lines reads abc 4 6 it means that the node number 5 contains the string "abc", its left child is the node number 4 and its right child is the node number 6. If the node does not have a child, or both, it would be shown by a -1 in the input. In other words, a leaf containing the string "aa" would be written as aa -1 -1 in the input. The node numbers are 0-based and the 0 h node is the root of the tree. For example take a look at the tree below. The numbers below the nodes show the corresponding line of input for the nodes.

Explanation / Answer

//.h file code:

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

// A binary tree node
class Node : public std::enable_shared_from_this<Node>
{

public:
   wchar_t data = L'';
   std::shared_ptr<Node> left, right;

   Node(wchar_t item);
};

class BinaryTree : public std::enable_shared_from_this<BinaryTree>
{

public:
   static std::shared_ptr<Node> root;
   static int preIndex;

   virtual std::shared_ptr<Node> buildTree(std::vector<wchar_t> &in_Renamed, std::vector<wchar_t> &pre, int inStrt, int inEnd);

   /* UTILITY FUNCTIONS */
   virtual int search(std::vector<wchar_t> &arr, int strt, int end, wchar_t value);

   virtual void printInorder(const std::shared_ptr<Node> &node);

   // driver program to test above functions
   static void main(std::vector<std::wstring> &args);
};

//.cpp file code:

Node::Node(wchar_t item)
{
   data = item;
   left = right = nullptr;
}

std::shared_ptr<Node> BinaryTree::root;
int BinaryTree::preIndex = 0;

std::shared_ptr<Node> BinaryTree::buildTree(std::vector<wchar_t> &in_Renamed, std::vector<wchar_t> &pre, int inStrt, int inEnd)
{

   if (inStrt > inEnd)
   {
       return nullptr;
   }

   std::shared_ptr<Node> tNode = std::make_shared<Node>(pre[preIndex++]);

   /* If this node has no children then return */
   if (inStrt == inEnd)
   {
       return tNode;
   }

   int inIndex = search(in_Renamed, inStrt, inEnd, tNode->data);

   tNode->left = buildTree(in_Renamed, pre, inStrt, inIndex - 1);
   tNode->right = buildTree(in_Renamed, pre, inIndex + 1, inEnd);

   return tNode;
}

int BinaryTree::search(std::vector<wchar_t> &arr, int strt, int end, wchar_t value)
{
   int i;
   for (i = strt; i <= end; i++)
   {
       if (arr[i] == value)
       {
           return i;
       }

   }
   return i;
}

void BinaryTree::printInorder(const std::shared_ptr<Node> &node)
{
   if (node == nullptr)
   {
       return;
   }

   /* first recur on left child */
   printInorder(node->left);

   /* then print the data of node */
   std::wcout << node->data << std::wstring(L" ");

   /* now recur on right child */
   printInorder(node->right);
}

void BinaryTree::main(std::vector<std::wstring> &args)
{
   std::shared_ptr<BinaryTree> tree = std::make_shared<BinaryTree>();
   std::vector<wchar_t> in_Renamed = {L'G', L'H', L'D', L'E', L'B', L'I', L'F', L'C', L'A'};
   std::vector<wchar_t> pre = {L'G', L'D', L'H', L'B', L'E', L'A', L'C', L'I' L'F'};
   int len = in_Renamed.size();
   std::shared_ptr<Node> mynode = tree->buildTree(in_Renamed, pre, 0, len - 1);

   // building the tree by printing inorder traversal
   std::wcout << std::wstring(L"Inorder traversal of constructed tree is : ") << std::endl;
   tree->printInorder(mynode);
}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.