Thread: How to represent list using trees

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    22

    Unhappy How to represent list using trees

    Hi all,

    Can someone help in devicing an efficient method for building a tree for representing a list as list represented using trees take less time to traverse and delete...

    Thanks in advance

    Regards
    C_Enthusiast

  2. #2
    Registered User
    Join Date
    Jul 2010
    Posts
    20
    Code:
    struct tree_node {
         char data[80];
         struct tree_node *parent;
         struct tree_node *left_child;
         struct tree_node *right_child;
    };
    All else depends on traversal type:
    - inorder
    - preorder
    - postorder
    - level-order

  3. #3
    Registered User
    Join Date
    Jun 2010
    Posts
    22
    Quote Originally Posted by 68656c70 View Post
    Code:
    struct tree_node {
         char data[80];
         struct tree_node *parent;
         struct tree_node *left_child;
         struct tree_node *right_child;
    };
    All else depends on traversal type:
    - inorder
    - preorder
    - postorder
    - level-order
    I want inorder taversal... Kindly tell the technique not the structure for nodes..
    Thanks in advance

  4. #4
    Registered User
    Join Date
    Jul 2010
    Posts
    20

    Lightbulb

    I hope it's bug-free... and correct.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct tree_node {
         int data;
         struct tree_node *parent;
         struct tree_node *left_child;
         struct tree_node *right_child;
    };
    
    int tree_push(struct tree_node *, int);
    
    int inorder_traversal(struct tree_node *);
    
    int main() {
         struct tree_node root;
         int i, val;
         root.data = 128;
         root.parent = NULL;
         root.left_child = NULL;
         root.right_child = NULL;
         srand(RAND_MAX - 1);
         for (i=0; i<20; i++) {
              val = (rand() % 256) + 1;
              tree_push(&root, val);
         }
         inorder_traversal(&root);
         printf("\n");
         return 0;
    }
    
    int tree_push(struct tree_node *parent, int value) {
         if (value < (*parent).data) {
              if ((*parent).left_child != NULL) {
                   tree_push((*parent).left_child, value);
              } else {
                   (*parent).left_child = malloc(sizeof(struct tree_node));
                   (*((*parent).left_child)).data = value;
                   (*((*parent).left_child)).parent = parent;
                   (*((*parent).left_child)).left_child = NULL;
                   (*((*parent).left_child)).right_child = NULL;
              }
         } else {
              if ((*parent).right_child != NULL) {
                   tree_push((*parent).right_child, value);
              } else {
                   (*parent).right_child = malloc(sizeof(struct tree_node));
                   (*((*parent).right_child)).data = value;
                   (*((*parent).right_child)).parent = parent;
                   (*((*parent).right_child)).left_child = NULL;
                   (*((*parent).right_child)).right_child = NULL;
              }
         }
         return 0;
    }
    
    int inorder_traversal(struct tree_node *parent) {
         if (parent == NULL) {
              return 0;
         } else {
              inorder_traversal((*parent).left_child);
              printf(" %d",(*parent).data);
              inorder_traversal((*parent).right_child);
         }
         return 0;
    }

  5. #5
    Registered User
    Join Date
    Jun 2010
    Posts
    22
    Quote Originally Posted by 68656c70 View Post
    I hope it's bug-free... and correct.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct tree_node {
         int data;
         struct tree_node *parent;
         struct tree_node *left_child;
         struct tree_node *right_child;
    };
    
    int tree_push(struct tree_node *, int);
    
    int inorder_traversal(struct tree_node *);
    
    int main() {
         struct tree_node root;
         int i, val;
         root.data = 128;
         root.parent = NULL;
         root.left_child = NULL;
         root.right_child = NULL;
         srand(RAND_MAX - 1);
         for (i=0; i<20; i++) {
              val = (rand() % 256) + 1;
              tree_push(&root, val);
         }
         inorder_traversal(&root);
         printf("\n");
         return 0;
    }
    
    int tree_push(struct tree_node *parent, int value) {
         if (value < (*parent).data) {
              if ((*parent).left_child != NULL) {
                   tree_push((*parent).left_child, value);
              } else {
                   (*parent).left_child = malloc(sizeof(struct tree_node));
                   (*((*parent).left_child)).data = value;
                   (*((*parent).left_child)).parent = parent;
                   (*((*parent).left_child)).left_child = NULL;
                   (*((*parent).left_child)).right_child = NULL;
              }
         } else {
              if ((*parent).right_child != NULL) {
                   tree_push((*parent).right_child, value);
              } else {
                   (*parent).right_child = malloc(sizeof(struct tree_node));
                   (*((*parent).right_child)).data = value;
                   (*((*parent).right_child)).parent = parent;
                   (*((*parent).right_child)).left_child = NULL;
                   (*((*parent).right_child)).right_child = NULL;
              }
         }
         return 0;
    }
    
    int inorder_traversal(struct tree_node *parent) {
         if (parent == NULL) {
              return 0;
         } else {
              inorder_traversal((*parent).left_child);
              printf(" %d",(*parent).data);
              inorder_traversal((*parent).right_child);
         }
         return 0;
    }
    The above code is just to create a binary tree... I want to create a tree in which external nodes represents linked list nodes and internal nodes contain the count of linked list nodes to their left side....
    This is something like creating a tree for huffman codes but in this case an almost balanced binary tree can be created....

    Regards
    C_Enthusiast

  6. #6
    Registered User
    Join Date
    Jul 2010
    Posts
    20
    If you sort your input, you have a linked list.

  7. #7
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Stop providing code without having the OP make any effort in solving his own problem.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by C_Enthusiast View Post
    The above code is just to create a binary tree... I want to create a tree in which external nodes represents linked list nodes and internal nodes contain the count of linked list nodes to their left side....
    Okay, you're beginning to describe an 'AVL Tree'. Look that up.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jul 2010
    Posts
    20

    Unhappy

    A graphic representation would really help...

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Seriously there are pictures, diagrams, videos, applets and tutorials galore, on the net about AVL trees... Let me google that for you
    A few of the regular contributors here even have information about them on their sites.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Jul 2010
    Posts
    20
    I was talking to C_Enthusiast...

  12. #12
    Registered User
    Join Date
    Jun 2010
    Posts
    22
    Quote Originally Posted by 68656c70 View Post
    I was talking to C_Enthusiast...
    I am still here....
    I cannot provide any pictures butt his idea of representing list using trees is given in book data structures using c and c++ by tenanbaum... page number 308 section 5.4

    I am not getting that why they want to so this after all creating a tree would have been better...

    Thanks for your help till now
    Regards
    C_Enthusiast

  13. #13
    Registered User
    Join Date
    Jul 2010
    Posts
    20
    @C_Enthusiast: At least you can draw something...

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by 68656c70 View Post
    I was talking to C_Enthusiast...
    Sorry, I think I must have mistook you for the OP.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Jun 2010
    Posts
    22
    Quote Originally Posted by 68656c70 View Post
    @C_Enthusiast: At least you can draw something...
    Hi all,

    Nothing better that this I can provide... This shows a linked list and the corresponding tree representation in which the internal nodes contain the number of linked list nodes present to its left and the external nodes represent the nodes of linked list..

    Hope this will be helpful....
    Thnaks in advance

    Regards
    C_Enthusiast

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM