473,322 Members | 1,540 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

how to implement general (each node) tree with c program

please send to me the source code how to implement general tree with three child using c programming
May 28 '13 #1
3 7612
Nepomuk
3,112 Expert 2GB
Hi samiman and welcome to bytes.com!

According to our posting guidelines, we will not do your homework for you. We will however gladly help you solve the homework yourself if you show us what you've done so far.

To get started with the task I would ask myself how a tree works and which elements from the C language could represent which parts of that structure. Maybe have another look at the material from the course on C you're obviously doing. You might even have similar examples - lists are commonly shown and are very similar to trees.
May 28 '13 #2
this was what i have done but it is not working




Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4.  
  5. #define SIZE 9
  6.  
  7. typedef struct treeNode
  8. {
  9.         int item;
  10.         struct treeNode *left;
  11.         struct treeNode *mid;
  12.         struct treeNode *right;
  13.  
  14. }treeNode;
  15.  
  16.  
  17. typedef int (*comparer)(int, int);
  18.  
  19. int compare(int a,int b)
  20. {
  21.     if(a < b)
  22.         return 1;
  23.     if(b<a<=b+5)
  24.         return 2;
  25.     if (a>b+5)
  26.         return 3;
  27.     return 0;
  28. }
  29. treeNode* create_node(int value)
  30. {
  31.     treeNode *new_node = (treeNode*)malloc(sizeof(treeNode));
  32.     if(new_node == NULL)
  33.     {
  34.         fprintf (stderr, "Out of memory!!! (create_node)\n");
  35.         exit(1);
  36.     }
  37.     new_node->item = value;
  38.  
  39.     new_node->left = NULL;
  40.     new_node->mid = NULL;
  41.     new_node->right = NULL;
  42.     return new_node;
  43. }
  44. typedef int (*comparer)(int, int);
  45. void insertNode(treeNode *root,comparer compare,int item)
  46. {
  47. if (root == NULL){
  48.        root = create_node(item);
  49.     }
  50.  
  51.    else{
  52.         int is_left = 0;
  53.         int is_mid = 0;
  54.         int is_right = 0;
  55.         int r;
  56.         treeNode* cursor = root;
  57.         treeNode* prev = NULL;
  58.         while(cursor != NULL){
  59.             r = compare(item,cursor->item);
  60.             prev = cursor;
  61.             if (r==1){
  62.                 is_left = 1;
  63.                 cursor = cursor->left;
  64.             }else if(r==2){
  65.                 is_mid = 1;
  66.                 cursor = cursor->mid;
  67.             }else if(r==3){
  68.                 is_right = 1;
  69.                 cursor = cursor->right;
  70.             }
  71.             }
  72.         if(is_left)
  73.            prev->left = create_node(item);
  74.          else if(is_mid)
  75.            prev->mid = create_node(item);
  76.          else if(is_right)
  77.            prev->right = create_node(item);
  78.  
  79.     else{
  80.         printf("duplicate values are not allowed!");
  81.     }
  82.     return root;
  83. }
  84. treeNode * search(treeNode *root,const int item,comparer compare)
  85. {
  86.  if (root == NULL)
  87.     return NULL;
  88.  
  89.  int r;
  90.  treeNode* cursor = root;
  91.  while (cursor!=NULL){
  92.     r=compare(item,cursor->item);
  93.     if(r==1)
  94.         cursor = cursor->left;
  95.     else if(r == 2)
  96.         cursor = cursor->mid;
  97.     else if(r == 3)
  98.         cursor = cursor->right;
  99.  }
  100.  return cursor;
  101.  
  102. }
  103.               //delete a node
  104. treeNode* delete_node(treeNode* root,int item,comparer compare)
  105. {
  106.     if(root==NULL)
  107.         return NULL;
  108.     treeNode *cursor;
  109.     int r = compare(item,root->item);
  110.     if(r==1)
  111.         root->left = delete_node(root->left,item,compare);
  112.     else if(r==2)
  113.         root->mid = delete_node(root->mid,item,compare);
  114.     else if(r==3)
  115.         root->right = delete_node(root->right,item,compare);
  116.     else{
  117.         if(root->left == NULL && root->mid == NULL)
  118.             {
  119.             cursor = root->right;
  120.             free(root);
  121.             root = cursor;
  122.             }
  123.         else if(root->left == NULL && root->right==NULL){
  124.             cursor = root->mid;
  125.             free(root);
  126.             root = cursor;
  127.         }
  128.         else if(root->right == NULL && root->mid == NULL){
  129.             cursor = root->left;
  130.             free(root);
  131.             root = cursor;
  132.         }
  133.  
  134.     }
  135.  
  136.   return root;
  137. }
  138. void dispose(treeNode* root)
  139. {
  140.     if(root != NULL)
  141.     {
  142.         dispose(root->left);
  143.         dispose(root->mid);
  144.         dispose(root->right);
  145.         free(root);
  146.     }
  147. }
  148.  
  149. void display(treeNode* nd)
  150. {
  151.     if(nd != NULL)
  152.         printf("%d ",nd->item);
  153. }
  154. void display_tree(treeNode* nd)
  155. {
  156.     if (nd == NULL)
  157.         return;
  158.     /* display node item */
  159.     printf("%d",nd->item);
  160.     if(nd->left != NULL)
  161.         printf("(L:%d)",nd->left->item);
  162.     if(nd->mid != NULL)
  163.         printf("(R:%d)",nd->mid->item);
  164.     if(nd->right != NULL)
  165.         printf("(R:%d)",nd->right->item);
  166.     printf("\n");
  167.  
  168.     display_tree(nd->left);
  169.     display_tree(nd->mid);
  170.     display_tree(nd->right);
  171. }
  172.  
  173.  
  174. int main(void)
  175. {
  176.     treeNode* root = NULL;
  177.     comparer int_comp = compare;
  178.  
  179.  
  180.  
  181.     int a[SIZE] = {8,3,10,1,6,14,4,7,13,15,2,5,20};
  182.     int i;
  183.     printf("--- C Binary Search Tree ---- \n\n");
  184.     printf("Insert: ");
  185.     for(i = 0; i < SIZE; i++)
  186.     {
  187.         printf("%d ",a[i]);
  188.         root = insert_node(root,int_comp,a[i]);
  189.     }
  190.     printf(" into the tree.\n\n");
  191.  
  192.     /* display the tree */
  193.     display_tree(root);
  194.  
  195.     /* remove element */
  196. int r;
  197.     do
  198.     {
  199.         printf("Enter data to remove, (-1 to exit):");
  200.         scanf("%d",&r);
  201.         if(r == -1)
  202.             break;
  203.         root = delete_node(root,r,int_comp);
  204.         /* display the tree */
  205.         if(root != NULL)
  206.             display_tree(root);
  207.         else
  208.             break;
  209.     }
  210.     while(root != NULL);
  211.     /* search for a node */
  212.  
  213.     int key = 0;
  214.     treeNode* s;
  215.     while(key != -1)
  216.     {
  217.         printf("Enter item to search (-1 to exit):");
  218.         scanf("%d",&key);
  219.  
  220.         s = search(root,key,int_comp);
  221.         if(s != NULL)
  222.         {
  223.             printf("Found it %d",s->item);
  224.             if(s->left != NULL)
  225.                 printf("(L: %d)",s->left->item);
  226.             if(s->mid != NULL)
  227.                 printf("(R: %d)",s->mid->item);
  228.             if(s->right != NULL)
  229.                 printf("(R: %d)",s->right->item);
  230.             printf("\n");
  231.         }
  232.         else
  233.         {
  234.             printf("node %d not found\n",key);
  235.         }
  236.     }
  237.  
  238.     /* remove the whole tree */
  239.     dispose(root);
  240.     return 0;
  241. }
  242. }
May 29 '13 #3
Nepomuk
3,112 Expert 2GB
OK... Well, first of all: In what way doesn't it work? Have you tested parts of it? Just writing code without testing it ever so often is not a good idea, as it's more difficult to find errors that way.

Here are errors I can find without testing or fixing the code myself:
  • I'm not aware of a malloc.h header file; this may depend on the compiler though.
  • In line 23 you seem to want to compare a and b with the line b<a<=b+5. This will not however find out, whether b<a and a<=b+5. What it will do is this assuming a = b + 6 and b > -5:
    Expand|Select|Wrap|Line Numbers
    1. b < a <= b + 5
    2. (b < a) <= b + 5
    3. 1 <= b + 5
    4. 1
    This is because there's no own boolean primitive data type in C and instead false = 0 and true = every other number. What you want instead is this:
    Expand|Select|Wrap|Line Numbers
    1. if(b < a && a <= b + 5) ...
  • In line 82 you return root within the method insertNode(...). This is not correct, as a void method will not return an element. As you use the result of that call later, I asume it should have a different type?
  • In line 84 you start a new function (search) while you're still in the insertNode method. Same with delete_node in line 104, dispose in line 138 and so on.
  • You define comparer twice: In line 17 and line 44.
  • In line 5 you define SIZE as 9. In 181 you create an array with SIZE elements but then hand it 13.
  • In line 188 you call a method called insert_node while in line 45 you define a method called insertNode. I guess, those should be the same?
That should be enough to get it to compile; then we can get it to do what it should.
May 30 '13 #4

Sign in to post your reply or Sign up for a free account.

Similar topics

1
by: Mikael P | last post by:
Hi, I am using argouml ( really neat UML modeling tool) to create a model. I export the model to xmi format ( it's xml). My UML-diagram looks like this: Brand A |
7
by: Rolf Kemper | last post by:
Dear All, somehow I remember that such or similar question was discussed already somewhere. But I can't find it anymore. I have a template calling itself. As long it goes deeper into the...
12
by: Dino L. | last post by:
I am putting data from DataTable to treeView foreach( DataRow aRow in aTable.Rows) { TreeNode tnode = new TreeNode(aRow.ToString() + aRow.ToString() + " " + aRow.ToString());...
2
by: Sean | last post by:
Hi all, I have a question here regarding implementing Binary Tree. I understand that Binary Tree can be implemented in one of the following methods: 1)using nodes with pointers to two...
9
by: raylopez99 | last post by:
What's the best way of implementing a multi-node tree in C++? What I'm trying to do is traverse a tree of possible chess moves given an intial position (at the root of the tree). Since every...
4
by: sharan | last post by:
Hello Friends I have a problem in Data Structure (In C) i want to implement a General tree having three child nodes of each parent node ...please send me any simple Example( code) by which i can...
0
by: RolfK | last post by:
Hello All, I'm trying to output an XML node tree in COMMENT tags. Processing is done with XSLT2.0. The output schould be avild xml like this: <root> <e c="some element 1"/> <e c="some...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.