0

Here is the code directory structure,

$ ls
lcrsImpl.c  multiWalkImpl.c  tree.h

For the below two rooted tree representations,

#include"../../list/list.h"

#if defined(LCRS)
  typedef struct SiblingTreeNode{
    struct SiblingTreeNode *parent;
    void *item;
    struct SiblingTreeNode *firstChild;
    struct SiblingTreeNode *nextSibling;
  }Node;

  typedef struct LCRSTree{
    Node *root;
    int size;
  }Tree;

#elif defined(MULTI_WALK)
   typedef struct treeNode{
    struct treeNode *parent;
    void *item
    List **childList;
  }Node;

  typedef struct multiWalkTree{
    Node *root;
    int size
  }Tree;
#else
  #error "Wrong representation "
#endif

Tree abstraction can be re-used by other abstractions.

Question:

To write a Tree abstraction using two representations(mentioned above),

As per the real world experience, What are the important(common) operations that need to be implemented on rooted tree?

Can you provide the signature(function declaration) of those operations?

Note - This would help me continue my implementation

overexchange
  • 15,768
  • 30
  • 152
  • 347
  • See [What are the benefits of a relative path such as `"../include/header.h"` for a header?](http://stackoverflow.com/questions/597318/). The implementation details should be hidden from the consumers of your code — it shouldn't matter whether it is a multi-walk tree or a LCRS tree that is used behind the scenes. It matters for your tree implementation code, but not for the consumer code. Writing a completely general purpose tree implementation probably isn't sensible. Write one that meets your current requirements. – Jonathan Leffler Dec 21 '16 at 06:10
  • You'll need functions to create a tree, destroy a tree, add an item, remove an item, various traversal operations (pre-order, in-order, post-order, BFS, etc), various search operations. You'll need to consider whether you're dealing with generic items or with a specific item type — how are you going to do comparisons. Do you have to parse the data in order to be able to add an item? If so, how will that be done? Adding a file path to a tree modelling a file system hierarchy is very different from a simple binary search tree. What are you trying to handle? – Jonathan Leffler Dec 21 '16 at 06:12
  • @JonathanLeffler Actual code written, can be seen [here](https://github.com/shamhub/Computing/tree/master/7_Tree/Rooted_tree/Rooted_tree_Implementation_c). It does not reflect the structure of the code in the query. The way code posted in the query is for simplicity to get the intent. Do you think the structure of code in shared link looks fine? – overexchange Dec 21 '16 at 06:18
  • The code doesn't compile — it doesn't look good. It doesn't have header guards in place. It includes four superfluous headers. As the consumer, I need header guards around: `typedef struct Tree Tree; Tree *newTree(void); void insert(Tree *, void *item); void* delete(Tree *, void *item); void preOrder(Tree*);` except that the `preOrder()` function needs to know what to do when it visits a node, so it needs a function pointer to the 'visitor function', and I had to fix the prototype for `delete()` — adding the second argument and the semicolon. Somewhere along the line you need a comparator. – Jonathan Leffler Dec 21 '16 at 06:26
  • @JonathanLeffler Made the working changes [here](https://github.com/shamhub/Computing/tree/master/7_Tree/Rooted_tree/Rooted_tree_Implementation_c), included header guard in `.h` files only – overexchange Dec 21 '16 at 07:37
  • @JonathanLeffler am using rooted tree in a contract of state propagation tree – overexchange Dec 21 '16 at 08:36
  • Multi walk tree for state propagation tree. LCRS tree for priority queue – overexchange Dec 21 '16 at 08:37

0 Answers0