Implement a Binary Tree using array

Question

in HW i am asked to implement a Binary Tree using pointers and then using the array implementation of bt. The problem is that while i know how to do both , they have to share the same main file . By that i mean , the exact same code i used for the pointers implementation is to be used by the array implementation. This means that when i am refercing to insertTree(tree,tree->left) must works for the array also .i am totally lost. My node is:

    Typedef  struct BTNode{
     itemtype data;
      Struct BTNode * left;
     Struct BTNode * left;
    }BTNode;

bruno · Accepted Answer · 2019-04-22 12:19:10Z

1

In the 'standard' case a new cell is supported by the result of a malloc and when it become useless you free it

Using an array can be to have an array of BTNode and rather than to malloc a new cell you get a free entry in the array. Because the cells can be get/released a priori in any order you can link the free cells too, so when a cell is released it is reintroduced in the free list associated to the array

So only the malloc/free calls have to be modified to be able to use an array or not

Note :

Typedef  struct BTNode{
     itemtype data;
      Struct BTNode * left;
     Struct BTNode * left;
    }BTNode;

you mean

typedef  struct BTNode{
   itemtype data;
   struct BTNode * left;
   struct BTNode * right;
} BTNode;

edited Apr 22, 2019 at 12:19

answered Apr 22, 2019 at 12:10

bruno

34.3k8 gold badges31 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Stelios V. Over a year ago

So if i understand correctly i am just using Malloc for an array of BTNodes . What's the purposes of this abstract type ? I mean its just like using the usual abstract type . Anyway thanks for the answer i will update the post for the furthermore issues.

bruno Over a year ago

not easy to use a abstract type in C, probably the best way is to use functions BTNode * allocBTnode() and void freeBTNodes(BTNode *) and to propose 2 definitions of them, one using malloc/free and the second the array, the choice between the 2 definitions can be done using the preprocessor (#ifdef USEARRAY .. #else ... #endif) to choose the one to use at compile time

Collectives™ on Stack Overflow

Implement a Binary Tree using array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related