title: How to Convert a Char Array to a Binary Tree using C++
body: <p>I have an assignment to convert a postfix expression from a txt document to a binary tree and then evaluate the expression. The base class was done for me, so I'm not going to include it in my code snippets. I am using  and getline() to read the file line-by-line and assign each to a string variable to then pass to my derived class. The part I'm struggling with, however, is converting that string to a char array (as the assignment requires we do this) and then using that array to determine where to add each index value on the tree. I think the issue is that the text document is using numbers greater than 9 (for example: 35) and I don't know how to account for that in my code, so I keep getting segmentation fault errors. Anyway, I will post some code below and any help, explanations, or references would be much appreciated.</p>
  <p>Main function:</p>
  <pre><code>int main() 
  {
    ifstream inFile;
    ofstream outFile;
    string pfx;
    binaryExpressionTree tree;
  
    inFile.open(&quot;RpnData.txt&quot;);
    outFile.open(&quot;RpnDataOut.txt&quot;);
  
    do
    {
      tree.destroyTree();
      
      getline(inFile, pfx);
  
      tree.buildExpressionTree(pfx);
  
      outFile &lt;&lt; tree.evaluateExpressionTree() &lt;&lt; endl;
    }
    while (inFile);
  
  }
  </code></pre>
  <p>The header file for my class:</p>
  <pre><code>#ifndef EXPRESSIONTREE_H
  #define EXPRESSIONTREE_H
  
  #include &quot;binaryTree.h&quot; 
  
  class binaryExpressionTree : public binaryTreeType&lt;string&gt;
  {
  public:
    void buildExpressionTree(string);
    //Function to build the binary expression tree using a postfix string as a parameter
    //Precondition: Must read a string as a parameter
    //Postcondition: Will convert the string to a binary tree
    
    double evaluateExpressionTree();
    //Function to evaluate the expression tree
    //Postcondition: Recursively calls the private function to evaluate the expression tree
  
    bool search(const string&amp;) const;
    //Function to search for a string in the tree
    //Precondition: Must have the address of a string to search for
    //Postcondition: Returns true if string is found in the tree and false otherwise
  
    void insert(const string&amp;);
    //Function to insert a string at the end of a branch on the tree
    //Precondition: Must have the address of a string to insert
    //Postcondition: Inserts the string at the end of a branch
  
    void deleteNode(const string&amp;);
    //Function to delete one node (containing the string provided as a parameter) of the tree
    //Precondition: Must have the address of a string to delete
    //Postcondition: Deletes the string from the tree
  
  private:
    double evaluateExpressionTree(nodeType&lt;string&gt;*);
    //Private function to evaluate the expression tree
    //Precondition: Must have a pointer to a nodeType on the tree
    //Postcondition: Returns the value of the postfix expression
  };
  
  #endif
  </code></pre>
  <p>The code that produces the issue:</p>
  <pre><code>void binaryExpressionTree::buildExpressionTree(string pfxExpression)
  {
    stack&lt;nodeType&lt;string&gt;*&gt; *tree;
    
    char* expression = new char[pfxExpression.length() +1];
    strcpy(expression, pfxExpression.c_str());
  
    for (int i = 0; i &lt; pfxExpression.length(); i++)
    {
      if ((expression[i] &gt;= 'a' &amp;&amp; expression[i] &lt;= 'z') || (expression[i] &gt;= 'A' &amp;&amp; expression[i] &lt;= 'Z') || (expression[i] &gt;= '0' &amp;&amp; expression[i] &lt;= '9'))
      {
        nodeType&lt;string&gt; *newNode;
  
        newNode = new nodeType&lt;string&gt;; //Create new node
        newNode-&gt;info = string(expression[i], expression[i+1]); //Set string of i to i+1 character in array to the info field 
        newNode-&gt;lLink = nullptr; //Make pointers for each branch nullptr
        newNode-&gt;rLink = nullptr;
  
        tree-&gt;push(newNode); //Push node onto the stack
  //Through the use of cout statements, I have found that the error lies on the line above
      }//end if
  </code></pre>
  <p>The following are the expressions found in the text file:</p>
  <pre><code>35 27 + 3 *
  23 30 15 * /
  34 24 12 7 / * + 23 -
  3 7 + 14 *
  
  </code></pre>
  <p>The following comes from the assignment directions themselves as an algorithm for the buildExpressionTree() member function. I apologize if the formatting is off, I tried to make it as readable as possible.</p>
  <pre><code>Here is the algorithm for building the expression tree:
   
  Initialize a stack of pointers to binary tree nodes 
  
  Get a postfix expression (this will be an input to the evaluateExpressionTree function)
  // This line did not really make sense to me since evaluate() takes no parameters
  
  Convert the string to a character array (include &lt;cstring&gt;)
  // This is the wording that led me to believe we are supposed to convert it
  //to a char array
   
  For each token in the expression: 
  
     If token is a number: 
  
       Create a node 
  
       Convert the token from a character array to a string  
  
       Store the string in the info field   
  
       Push the new node onto the stack 
  
     else if token is an operator: 
    
       Create a node and store the operator in the info field 
    
       If stack is not empty: 
  
         Use top() to get a reference to the node at the top of the stack 
  
         Store the reference in the rLink field of the new node.  
  
         Use pop() to remove the node from the stack 
  
       If stack is not empty: 
  
           Use top() to get a reference to the node at the top of the stack 
  
           Store the reference in the lLink field of the new node 
  
           Use pop() to remove the node from the stack 
  
           Push the new node back onto the stack 
  
         else: 
           Error – Stack is empty 
       else: 
         Error – Stack is empty 
     else: 
       Error – unsupported token 
  
  Get the next token
  //This ends the for loop
  
  if stack is not empty: 
     Pop the expression tree from the stack and store in root 
  
  If stack is not empty: 
     There was an error, set root back to null
  </code></pre>
  <p>And finally, I will include the base class. It's a lot to dig through, and my professor did not separate the header and implementation files.</p>
  <pre><code>//Header File Binary Search Tree
  #ifndef H_binaryTree
  #define H_binaryTree
  
  #include &lt;iostream&gt;
  
  using namespace std;
  
  //Definition of the Node
  template &lt;class elemType&gt;
  struct nodeType
  {
      elemType info;
      nodeType&lt;elemType&gt; *lLink;
      nodeType&lt;elemType&gt; *rLink;
  };
  
  //Definition of the class
  template &lt;class elemType&gt;
  class binaryTreeType
  {
  protected:
      nodeType&lt;elemType&gt;  *root;
  
  
      
  public:
      const binaryTreeType&lt;elemType&gt;&amp; operator=
      (const binaryTreeType&lt;elemType&gt;&amp;);
      //Overload the assignment operator.
  
      bool isEmpty() const;
      //Function to determine whether the binary tree is empty.
      //Postcondition: Returns true if the binary tree is empty;
      //               otherwise, returns false.
  
      void inorderTraversal() const;
      //Function to do an inorder traversal of the binary tree.
      //Postcondition: Nodes are printed in inorder sequence.
  
      void preorderTraversal() const;
      //Function to do a preorder traversal of the binary tree.
      //Postcondition: Nodes are printed in preorder sequence.
  
      void postorderTraversal() const;
      //Function to do a postorder traversal of the binary tree.
      //Postcondition: Nodes are printed in postorder sequence.
  
      int treeHeight() const;
      //Function to determine the height of a binary tree.
      //Postcondition: Returns the height of the binary tree.
  
      int treeNodeCount() const;
      //Function to determine the number of nodes in a
      //binary tree.
      //Postcondition: Returns the number of nodes in the
      //               binary tree.
  
      int treeLeavesCount() const;
      //Function to determine the number of leaves in a
      //binary tree.
      //Postcondition: Returns the number of leaves in the
      //               binary tree.
  
      void destroyTree();
      //Function to destroy the binary tree.
      //Postcondition: Memory space occupied by each node
      //               is deallocated.
      //               root = NULL;
  
      virtual bool search(const elemType&amp; searchItem) const = 0;
      //Function to determine if searchItem is in the binary
      //tree.
      //Postcondition: Returns true if searchItem is found in
      //               the binary tree; otherwise, returns
      //               false.
  
      virtual void insert(const elemType&amp; insertItem) = 0;
      //Function to insert insertItem in the binary tree.
      //Postcondition: If there is no node in the binary tree
      //               that has the same info as insertItem, a
      //               node with the info insertItem is created
      //               and inserted in the binary search tree.
  
      virtual void deleteNode(const elemType&amp; deleteItem) = 0;
      //Function to delete deleteItem from the binary tree
      //Postcondition: If a node with the same info as
      //               deleteItem is found, it is deleted from
      //               the binary tree.
      //               If the binary tree is empty or
      //               deleteItem is not in the binary tree,
      //               an appropriate message is printed.
  
      binaryTreeType(const binaryTreeType&lt;elemType&gt;&amp; otherTree);
      //Copy constructor
  
      binaryTreeType();
      //Default constructor
  
      ~binaryTreeType();
      //Destructor
  
  private:
      void copyTree(nodeType&lt;elemType&gt;* &amp;copiedTreeRoot,
                    nodeType&lt;elemType&gt;* otherTreeRoot);
      //Makes a copy of the binary tree to which
      //otherTreeRoot points.
      //Postcondition: The pointer copiedTreeRoot points to
      //               the root of the copied binary tree.
  
      void destroy(nodeType&lt;elemType&gt;* &amp;p);
      //Function to destroy the binary tree to which p points.
      //Postcondition: Memory space occupied by each node, in
      //               the binary tree to which p points, is
      //               deallocated.
      //               p = NULL;
  
      void inorder(nodeType&lt;elemType&gt; *p) const;
      //Function to do an inorder traversal of the binary
      //tree to which p points.
      //Postcondition: Nodes of the binary tree, to which p
      //               points, are printed in inorder sequence.
  
      void preorder(nodeType&lt;elemType&gt; *p) const;
      //Function to do a preorder traversal of the binary
      //tree to which p points.
      //Postcondition: Nodes of the binary tree, to which p
      //               points, are printed in preorder
      //               sequence.
  
      void postorder(nodeType&lt;elemType&gt; *p) const;
      //Function to do a postorder traversal of the binary
      //tree to which p points.
      //Postcondition: Nodes of the binary tree, to which p
      //               points, are printed in postorder
      //               sequence.
  
      int height(nodeType&lt;elemType&gt; *p) const;
      //Function to determine the height of the binary tree
      //to which p points.
      //Postcondition: Height of the binary tree to which
      //               p points is returned.
  
      int max(int x, int y) const;
      //Function to determine the larger of x and y.
      //Postcondition: Returns the larger of x and y.
  
      int nodeCount(nodeType&lt;elemType&gt; *p) const;
      //Function to determine the number of nodes in
      //the binary tree to which p points.
      //Postcondition: The number of nodes in the binary
      //               tree to which p points is returned.
  
      int leavesCount(nodeType&lt;elemType&gt; *p) const;
      //Function to determine the number of leaves in
      //the binary tree to which p points
      //Postcondition: The number of leaves in the binary
      //               tree to which p points is returned.
  };
  
  //Definition of member functions
  
  template &lt;class elemType&gt;
  binaryTreeType&lt;elemType&gt;::binaryTreeType()
  {
      root = NULL;
  }
  
  template &lt;class elemType&gt;
  bool binaryTreeType&lt;elemType&gt;::isEmpty() const
  {
      return (root == NULL);
  }
  
  template &lt;class elemType&gt;
  void binaryTreeType&lt;elemType&gt;::inorderTraversal() const
  {
      inorder(root);
  }
  
  template &lt;class elemType&gt;
  void binaryTreeType&lt;elemType&gt;::preorderTraversal() const
  {
      preorder(root);
  }
  
  template &lt;class elemType&gt;
  void binaryTreeType&lt;elemType&gt;::postorderTraversal() const
  {
      postorder(root);
  }
  
  template &lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::treeHeight() const
  {
      return height(root);
  }
  
  template &lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::treeNodeCount() const
  {
      return nodeCount(root);
  }
  
  template &lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::treeLeavesCount() const
  {
      return leavesCount(root);
  }
  
  template &lt;class elemType&gt;
  void  binaryTreeType&lt;elemType&gt;::copyTree
  (nodeType&lt;elemType&gt;* &amp;copiedTreeRoot,
   nodeType&lt;elemType&gt;* otherTreeRoot)
  {
      if (otherTreeRoot == NULL)
          copiedTreeRoot = NULL;
      else
      {
          copiedTreeRoot = new nodeType&lt;elemType&gt;;
          copiedTreeRoot-&gt;info = otherTreeRoot-&gt;info;
          copyTree(copiedTreeRoot-&gt;lLink, otherTreeRoot-&gt;lLink);
          copyTree(copiedTreeRoot-&gt;rLink, otherTreeRoot-&gt;rLink);
      }
  } //end copyTree
  
  template &lt;class elemType&gt;
  void binaryTreeType&lt;elemType&gt;::inorder
  (nodeType&lt;elemType&gt; *p) const
  {
      if (p != NULL)
      {
          inorder(p-&gt;lLink);
          cout &lt;&lt; p-&gt;info &lt;&lt; &quot; &quot;;
          inorder(p-&gt;rLink);
      }
  }
  
  template &lt;class elemType&gt;
  void binaryTreeType&lt;elemType&gt;::preorder
  (nodeType&lt;elemType&gt; *p) const
  {
      if (p != NULL)
      {
          cout &lt;&lt; p-&gt;info &lt;&lt; &quot; &quot;;
          preorder(p-&gt;lLink);
          preorder(p-&gt;rLink);
      }
  }
  
  template &lt;class elemType&gt;
  void binaryTreeType&lt;elemType&gt;::postorder
  (nodeType&lt;elemType&gt; *p) const
  {
      if (p != NULL)
      {
          postorder(p-&gt;lLink);
          postorder(p-&gt;rLink);
          cout &lt;&lt; p-&gt;info &lt;&lt; &quot; &quot;;
      }
  }
  
  //Overload the assignment operator
  template &lt;class elemType&gt;
  const binaryTreeType&lt;elemType&gt;&amp; binaryTreeType&lt;elemType&gt;::
  operator=(const binaryTreeType&lt;elemType&gt;&amp; otherTree)
  {
      if (this != &amp;otherTree) //avoid self-copy
      {
          if (root != NULL)   //if the binary tree is not empty,
              //destroy the binary tree
              destroy(root);
  
          if (otherTree.root == NULL) //otherTree is empty
              root = NULL;
          else
              copyTree(root, otherTree.root);
      }//end else
  
      return *this;
  }
  
  template &lt;class elemType&gt;
  void  binaryTreeType&lt;elemType&gt;::destroy(nodeType&lt;elemType&gt;* &amp;p)
  {
      if (p != NULL)
      {
          destroy(p-&gt;lLink);
          destroy(p-&gt;rLink);
          delete p;
          p = NULL;
      }
  }
  
  template &lt;class elemType&gt;
  void  binaryTreeType&lt;elemType&gt;::destroyTree()
  {
      destroy(root);
  }
  
  //copy constructor
  template &lt;class elemType&gt;
  binaryTreeType&lt;elemType&gt;::binaryTreeType
  (const binaryTreeType&lt;elemType&gt;&amp; otherTree)
  {
      if (otherTree.root == NULL) //otherTree is empty
          root = NULL;
      else
          copyTree(root, otherTree.root);
  }
  
  //Destructor
  template &lt;class elemType&gt;
  binaryTreeType&lt;elemType&gt;::~binaryTreeType()
  {
      destroy(root);
  }
  
  template&lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::height
  (nodeType&lt;elemType&gt; *p) const
  {
      if (p == NULL)
          return 0;
      else
          return 1 + max(height(p-&gt;lLink), height(p-&gt;rLink));
  }
  
  template &lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::max(int x, int y) const
  {
      if (x &gt;= y)
          return x;
      else
          return y;
  }
  
  template &lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::nodeCount(nodeType&lt;elemType&gt; *p) const
  {
      if (p == nullptr)
          return 0;
      else
          return 1 + nodeCount(p-&gt;lLink) + nodeCount(p-&gt;rLink);
  }
  
  
  template &lt;class elemType&gt;
  int binaryTreeType&lt;elemType&gt;::leavesCount(nodeType&lt;elemType&gt; *p) const
  {
      if (p-&gt;lLink != nullptr &amp;&amp; p-&gt;rLink != nullptr)
          return 0 + leavesCount(p-&gt;lLink) + leavesCount(p-&gt;rLink);
      else
          return 1;
  }
  
  #endif
  
  </code></pre>