CODEWITHSUNDEEP
ctext-filesbinary-treebinary-search-tree
Christopher M.
Christopher M.

Reputation: 71

Saving C Binary search tree to txt file

I am doing a C BST library and im trying to do a function that will save the binary search tree into a text file.I am quite confuse on how to do it.Heres my tree structure:

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

typedef struct Node TNode;
typedef struct Node *binary_tree;

Creation of the tree:

binary_tree NewBinaryTree(int value_root) {
    binary_tree newRoot = malloc(sizeof(TNode));
    if (newRoot) {
        newRoot->value = value_root;
        newRoot->left = NULL;
        newRoot->right = NULL;
    }
    return newRoot;
}

Adding elements to it:

void Insert(binary_tree *tree, int val) {
    if (*tree == NULL) {
        *tree = (binary_tree)malloc(sizeof(TNode));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
    } else {
        if (val < (*tree)->value) {
            Insert(&(*tree)->left, val);
        } else {
            Insert(&(*tree)->right, val);
        }
    }
}

I did a start of the function but I dont know how to do this:

void savetree(binary_tree *tree, char * filename)
{
FILE *afile;
int remainn, counter, readsize, i;
int *bb;

afile = fopen(filename, "wb");
if (afile) {
    bb = calloc(sizeof(int), BBSIZE);  //BBSIZE =4096
    remainn = treesize(tree);
    counter = 0;
    while (remainn > 0) {
        if (remainn > BBSIZE) {
            readsize = BBSIZE;
        } else {
            readsize = remainn;
        }

Heres the treesize function:

int treesize( binary_tree tree )
{
    if( tree == NULL )
    {
        return (0) ;
    }
    else
    {
        return( 1 + treesize( tree->left ) + treesize( tree->right ) ) ;
    }
}

This savetree function is not completed but im not sure on how to complete it/if what I did is correct.

thank you

Upvotes: 1

Views: 2477

Answers (3)

Douglas Su
Douglas Su

Reputation: 3364

For a sparse binary tree(Binary tree which has rare nodes but height is very), One method is save its preorder and postorder traversals and then rebuild this binary tree from these two traversals to avoid saving many NULL bytes as suggested by Dulguun.

Some examples: Construct Full Binary Tree from given preorder and postorder traversals

Upvotes: 0

Dulguun
Dulguun

Reputation: 554

The easiest way to save binary tree to a txt file is saving them as an array. Only downside is you will waste space because it will save the binary tree as complete binary tree.

It is easy to write and even to read. Because left, right child and parent of node at ith index can be found as:

int left(int i) {
    return 2*i + 1;
}
int right(int i) {
    return 2*i + 2;
}
int parent(int i) {
    return (i-1)/2;
}

enter image description here

Upvotes: 1

Malcolm McLean
Malcolm McLean

Reputation: 6404

Nested parentheses and trees are alternative representations for the same thing.

So writing a tree is easy

   void writenode(Node *node)
   {
      printf("{");
      printf("%d ", node-.value);
      if(node->left)
         writenode(node->left);
      if(node->right)
         writenode(node->right);
      printf("}");
    }

Reading is quite a bit harder. You have to detect malformed input, and construct the children recursively.

Upvotes: 1

Related Questions