Binary Tree

This is a discussion on Binary Tree within the C Programming forums, part of the General Programming Boards category; I need help!! There is a question where I have to create a program to perform Inorder on the following ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    8

    Binary Tree

    I need help!!

    There is a question where I have to create a program to perform Inorder on the following data:
    60, 40, 80, 22, 55, 99

    I think I got the right coding for Inorder. But I have problem in inserting the data. I got the InsertTree function from a book.But the function has 3 parameters. Do I need key in this function?

    Urgent help needed. Thanks.

    #include<stdio.h>
    struct TreeNode
    {
    int Data;
    struct TreeNode *Left, *Right;
    };
    typedef struct TreeNode TreePointer;
    void InsertTree(TreePointer Root,Datarecord rec,int key);
    void Inorder(TreePointer Root);
    void main()
    {
    TreePointer Root;
    /*60,40,80,22,55,99*/
    printf("Enter number");
    scanf("%d", num);
    InsertTree(?;?;?);
    Inorder(num);
    getch();
    }
    void Inorder(TreePointer Root)
    {
    if(Root!=NULL)
    {
    Inorder(Root->Left);
    printf("%d ", Root->Data);
    Inorder(Root->Right);
    }
    }
    void InsertTree(TreePointer Root,Datarecord rec,int key)
    {
    if (Root == NULL)
    {
    Root = (TreePointer)malloc(sizeof(TreeNode));
    Root->Key = Key;
    Root->Data = rec;
    Root->Left = NULL;
    Root->Right = NULL;
    }
    else
    {
    if (Key < Root->Key)
    InsertTree(Root->Left,rec,Key);
    else
    InsertTree(Root->Right,rec,Key);
    }
    }

  2. #2
    Me want cookie! Monster's Avatar
    Join Date
    Dec 2001
    Posts
    680
    Hi papedum,

    - I don't think you need the key parameter in this case. Just remove this argument.
    - Since you only need numbers you can change the Datarecord into int.
    - In the InsertTree function you are checking if Root is a NULL pointer. So you must give a pointer to a TreeNode and not the TreeNode itself:

    Code:
    int main()
    {
      TreeNode *Root = NULL;
      ...
    }
    
    void InsertTree(TreeNode *Root, int Data)
    {
      if(Root == NULL)
      {
        Root = (TreeNode *)malloc(sizeof(TreeNode));
        ...
      }
      ...
    }
    However, this is not going to work because you use the malloc function in your InsertTree function. The malloc function returns a new pointer to allocated space. This will not work because the Root variabele (in main) is still pointing to NULL. There are two ways (that I can think of) to solve this. One way is by returning the newly allocated pointer. The other way is by passing a pointer to a pointer:
    Code:
    option 2:
    
    void InsertTree(TreePointer **Root, int Data) 
    { 
      if (*Root == NULL) 
      { 
        (*Root) = (TreePointer *)malloc(sizeof(TreeNode)); 
        (*Root)->Data = Data; 
        (*Root)->Left = NULL; 
        (*Root)->Right = NULL; 
      } 
      else 
      { 
        if (Data < (*Root)->Data) 
          InsertTree(&(*Root)->Left, Data); 
        else 
          InsertTree(&(*Root)->Right,Data); 
      } 
    }
    
    int main()
    {
      TreeNode *Root = NULL;
      ...
      InsertTree(&Root);
      ....
    }
    I hope this will help you.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >void main()
    No, int main ( void ).

    You had an almost endless number of errors in this code, compare how I've fixed it with what you had before to see what changes were made. Note that I changed the rec variable to an int so that it matched the definition of the TreeNode, you can use another struct variable as you apparently were doing before, but be sure to make TreeNode->Data an instance of that struct as well. You didn't post the definition of Datarecord, so I changed it to int.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
     
    struct TreeNode 
    { 
      int Data; 
      struct TreeNode *Left, *Right; 
    }; 
    
    typedef struct TreeNode *TreePointer; 
    void InsertTree(TreePointer *Root,int rec); 
    void Inorder(TreePointer Root); 
    
    int main ( void ) 
    {
      int num = 0;
      TreePointer Root = NULL; 
      printf("Enter a number (Ctrl+Z to quit): ");
      while ( scanf("%d", &num) == 1 ) {  
        InsertTree(&Root,num);
        printf("Enter a number (Ctrl+Z to quit): ");
      }
      Inorder(Root); 
      (void)getchar();
      return EXIT_SUCCESS;
    }
     
    void Inorder(TreePointer Root) 
    { 
      if(Root!=NULL) 
      { 
        Inorder(Root->Left); 
        printf("%d ", Root->Data); 
        Inorder(Root->Right); 
      } 
    } 
    
    void InsertTree(TreePointer *Root,int rec) 
    { 
      if ((*Root) == NULL) 
      { 
        (*Root) = malloc(sizeof **Root);  
        (*Root)->Data = rec; 
        (*Root)->Left = NULL; 
        (*Root)->Right = NULL; 
      } 
      else if (rec < (*Root)->Data) 
        InsertTree(&(*Root)->Left,rec); 
      else 
        InsertTree(&(*Root)->Right,rec); 
    }
    -Prelude
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Jan 2002
    Posts
    8
    Thanks Prelude.

    Sorry to bother you again, but I would like to know how the CTRL+Z works.

    Is scanf(..., &num)==1 similar to a boolean true or false where 1 stands for true.

    Is there any simpler way without using the CTRL+Z?

    Thanks in advance.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Ctrl+Z is the key combination for EOF on Windows/DOS systems, it's Ctrl+D for *NIX systems. This could be any value you want provided it is valid for scanf, you can then check it for the exit condition. I chose EOF for the exit condition because scanf returns either the number of values converted, or EOF. If you enter anything but a number then scanf will not return 1 and the loop will exit, you could just as easily have said

    printf("Enter a number or \ 'q\ '<Footnote> to quit: ");

    >Is scanf(..., &num)==1 similar to a boolean true or false where 1 stands for true
    1 stands for the number of conversions that a successful call to scanf will occur. If the call to scanf reads values into two variables then a successful call would return 2. I used while ( scanf (...) == 1 ) so that the loop would exit upon any failure such as a character being read or EOF.

    -Prelude

    Footnote: There shouldn't be a space between the \ and ', these boards wouldn't let me place them together without removing the \.
    My best code is written with the delete key.

  6. #6
    Unregistered
    Guest
    Instead of accepting numbers from user input, how could you use this binary tree structure to read in a text file from stdin, identify new words, and add them to the tree?

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Well, to accept a file from stdin you have to redirect the file from the command line:

    C:\ program < inputfile

    Then of course you would have to change the structure to accept strings instead of numbers and use strcmp to make sure that the string is not already in the tree. Other than that and printing/reading strings, the code is pretty much the same.

    -Prelude
    My best code is written with the delete key.

  8. #8
    Comment your source code! Lynux-Penguin's Avatar
    Join Date
    Apr 2002
    Posts
    533
    How many binary tree questions have been asked on this forum?
    Perhaps it should be moved to FAQ or just globally clarified somehow.
    Asking the right question is sometimes more important than knowing the answer.
    Please read the FAQ
    C Reference Card (A MUST!)
    Pointers and Memory
    The Essentials
    CString lib

  9. #9
    Registered User
    Join Date
    Mar 2002
    Posts
    11
    Yes, input from command line - yeah. But, how about the buffer array for the individual words? And, how would you pass the individual word to the Insert function?

    Thanks.

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >But, how about the buffer array for the individual words? And,
    >how would you pass the individual word to the Insert function?
    Just create a char array to hold each word, use scanf to read a single word from the file and pass that to the Insert function. The changes really are minor:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    struct TreeNode 
    { 
      char Data[BUFSIZ]; 
      struct TreeNode *Left, *Right; 
    }; 
    
    typedef struct TreeNode *TreePointer; 
    static void InsertTree(TreePointer *Root, char *rec); 
    static void Inorder(TreePointer Root); 
    
    int main ( void ) 
    {
      char word[BUFSIZ] = {'\0'};
      TreePointer Root = NULL; 
      while ( scanf("%s", word) == 1 ) {  
        InsertTree(&Root,word);
      }
      if ( Root != NULL )Inorder(Root); 
      (void)getchar();
      return EXIT_SUCCESS;
    }
     
    void Inorder(TreePointer Root) 
    { 
      if(Root!=NULL) 
      { 
        Inorder(Root->Left); 
        printf("%s\n", Root->Data); 
        Inorder(Root->Right); 
      } 
    } 
    
    void InsertTree(TreePointer *Root, char *rec) 
    { 
      if (*Root == NULL) 
      { 
        *Root = malloc(sizeof **Root);
        if ( *Root != NULL ) {
          strcpy ( (*Root)->Data, rec ); 
          (*Root)->Left = NULL; 
          (*Root)->Right = NULL;
        }
      } 
      else if ( strcmp ( rec, (*Root)->Data ) < 0 ) 
        InsertTree(&(*Root)->Left,rec);
      else if ( strcmp ( rec, (*Root)->Data ) > 0 )
        InsertTree(&(*Root)->Right,rec);
    }
    >Perhaps it should be moved to FAQ or just globally clarified somehow.
    I doubt either could be done easily, binary trees just aren't easy to grasp at first.

    -Prelude
    My best code is written with the delete key.

  11. #11
    Registered User
    Join Date
    Mar 2002
    Posts
    11
    Prelude...............you are a genius..............

  12. #12
    Unregistered
    Guest
    is this a ordinary binary tree or an AVL binary tree??

    i'm not sure of the different.....

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >is this a ordinary binary tree or an AVL binary tree??
    This is a standard binary tree. An AVL tree maintains a balance by defining a balance factor in the node structure and rotating nodes upon insertion into the tree so that the balance factors remain between -1 and +1.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21