What is tree data structure? What is binary tree and the utility? Explain with an example.

Tree is a data structures are used to store info in hierarchical order. Each record in a tree is called node. The top most node which has no parent is called root node. Each node has either no child or one or more children. A node which has no child is the outer most node and also known as leaf node.

This is the general Tree node data structure in C -

struct node {
  struct node *child;
  struct node *prent;
  int value;
};

A node can hold one or more child nodes. Storing child nodes in a node depends of the design. If number of children in known the we can name individual child as child1, child2,..,childN.-

struct node {
  struct node *child1;
  struct node *child2;
  ...
  struct node *childN;
  int value;
};

Alternately array can be used-

struct node {
  struct node *child[MAX_CHILD];
  int value;
};

Dynamic array can also be possible-

struct node {
  struct node **child;
  int value;
};

Storing hierarchical data structure often requires traversal back to upper node i.e. to parent node. Node often contains a member called parent pointer.

struct node {
  struct node *child1;
  struct node *child2;

  struct node *parent;
  int value;
};

Example 1: This is very useful data structure to deal with hierarchical records. Most of the time GUI objects are designed with this type of data structure. In GUI every object or node is called window. Like a message box for example has three child items – one text field, two buttons OK and Cancel. Now we take message dialog box as the parent node. Then it has a child text field. This child has sibling as ok button. Again ok button has a sibling as cancel button. At last cancel button is the last child of the dialog this it has no sibling or its sibling is NULL. Here every child item of dialog box has no further child. Thus for each item child is NULL.

struct window dialog_box;
struct window text_field;
struct window ok_button;
struct window cancel_button;

dialog_box.child           = text_field;
dialog_box. sibling_next   = NULL;
text_field.sibling_next    = ok_button;
ok_button.sibling_next     = cancel_button;
cancel_button.sibling_next = NULL;
text_field.child           = NULL;
ok_button.child            = NULL;
cancel_button.child        = NULL;

Example 2: Directory structure is another good example of tree data structure.

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›