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.

Generic Tree

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.

GUI Tree objects

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.

File Explorer objects

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

 Vote 0

Similar topics related to this section

Queue, reverse single linked list, delete single linked list, Stack, Tree and Binary tree, Binary tree, traverse Binary tree, Binary search tree, double Binary tree,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan