How to read file into a binary tree?

I need to read binary tree from a file then mirror it and write it out to another file. I have managed to mirror it, but can't find any way how to read it from file before mirroring. I have seen other people asking it, but none of them seem to get an answer.

#include <iostream>
using namespace std;

// Data structure to store a binary tree node
struct Node
{
    int data;
    Node *left, *right;

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

// Function to perform preorder traversal on a given binary tree
void preorder(Node* root)
{
    if (root == nullptr) {
        return;
    }

    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

// Function to convert a given binary tree into its mirror
void convertToMirror(Node* root)
{
    // base case: if the tree is empty
    if (root == nullptr) {
        return;
    }

    // convert left subtree
    convertToMirror(root->left);

    // convert right subtree
    convertToMirror(root->right);

    // swap left subtree with right subtree
    swap(root->left, root->right);
}

int main()
{
    /* Construct the following tree
              1
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
    */

    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->left = new Node(6);
    root->right->right = new Node(7);

    convertToMirror(root);
    preorder(root);

    return 0;
}

CodePudding user response：

With trees, recursive functions are usually the easiest way to go, since they allow you to iterate over the entire tree without having to manually maintain the state of the iteration.

For example, your Node::write() method (that you use to dump the state of your tree to disk) might look something like this (untested pseudocode):

void Node::write(FILE * fpOut) const
{
   fprintf(fpOut, "BEGIN Node data=%i\n", data);
   if (left) left->write(fpOut);
   if (right) right->write(fpOut);
   fprintf(fpOut, "END Node\n");  
}

For example, for a tree that contains just the root (with data=1) and two children (with data=2 and data=3), that would result in a file that looks like this:

BEGIN NODE data=1
BEGIN NODE data=2
END NODE
BEGIN NODE data=3
END NODE
END NODE

... but how to read it back in? That's a bit trickier, but you can do that with a similar recursive function, something like this (again, untested pseudocode):

Node * readTree(Node * parent, FILE * fpIn)
{
   char buf[128];
   fgets(buf, sizeof(buf), fpIn);
   while(strncmp(buf, "BEGIN NODE data=", 16) == 0)
   {
      Node * childNode = new Node(atoi(buf 16));
      (void) readTree(childNode, fpIn);  // recurse to read child node

      if (parent)
      {
             if (parent->left == NULL) parent->left = childNode;
        else if (parent->right == NULL) parent->right = childNode;
        else
        {
           printf("File contains more than two children for node!?\n");
           delete childNode;  // avoid memory leak
           break;
        }
      }
      else return node;  // return the root of the tree to the caller
   }

   return NULL;
}

CodePudding user response：

Taking a page from the book of LISP, you could represent your tree as: (whitespace for clarity)

(1
  (2
    (4 * *)
    (5 * *))
  (3
    (6 * *)
    (7 * *)))

with a simple read function as:

Node * readTree(istream& is) {
    std::istream::sentry s(is);
    if (!s) {
        // should not happen!
    }

    int data;
    Node *left=nullptr, *right=nullptr;
    if (is.peek() == '(') {
        is.get(); // eat (
        is >> data;
        left = readTree(is);
        right = readTree(is);
        is.get(); // eat )

        return TODO; // create Node from data, left, right
    } else if (is.peek() == '*') {
        is.get(); // eat *
        return nullptr;
    } else {
        // should not happen!
    }
}