Binary Tree

[papedum]

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);
}
}

[Monster]

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:

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:

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.

[Prelude]

>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.

#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

[papedum]

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.

[Prelude]

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 \.

[Unregistered]

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?

[Prelude]

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

[Lynux-Penguin]

How many binary tree questions have been asked on this forum?
Perhaps it should be moved to FAQ or just globally clarified somehow.

[Steven Snell]

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.

[Prelude]

>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:

#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

[Steven Snell]

Prelude...............you are a genius..............

[Unregistered]

is this a ordinary binary tree or an AVL binary tree??

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

[Prelude]

>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