# Alphabetic binary tree sorting

Page 1 of 1

## 4 Replies - 14129 Views - Last Post: 13 February 2010 - 07:50 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=155266&amp;s=7cbe8e97e2797225b3c8c5dd00485133&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 not1975

Reputation: 0
• Posts: 51
• Joined: 26-December 06

# Alphabetic binary tree sorting

Posted 10 February 2010 - 07:49 PM

This is my program for sorting words alphabetically into a binary tree. So far it only sorts based on the first character. I'm getting an access violation error and a crash with the insert() recursively called within insert.

```#include <stdio.h>
#define STRING_LEN 100

struct node
{
char word[STRING_LEN+1];
struct node* left;
struct node* right;
};

void insert(struct node* new, struct node* current)
{
if(new->word[0] <= current->word[0])
{
if(current->left==NULL)
{
current->left = new;
}
else
insert(current, new);
}

else
{
if(current->right == NULL)
current->right = new;
else
insert(current, new);
}
}

{
printf("%s", node->word);
if(node->left != NULL)
{
}
else if(node->right != NULL)
{
}
}

int main()
{
struct node* root_node = (struct node *) malloc(sizeof(struct node));;

char word[STRING_LEN+1];
int eof_flag = 0;

FILE* word_file = fopen("C:\\wordlist.txt", "r");
while(!eof_flag)
{
struct node* new_node= (struct node *) malloc(sizeof(struct node));

if(fgets(new_node->word, STRING_LEN, word_file)==NULL)
{
eof_flag=1;
break;
}

insert(new_node, root_node);
}

system("PAUSE");

if(fclose(word_file) != 0)
return -1;
else return 0;
}

```

This post has been edited by not1975: 10 February 2010 - 07:55 PM

Is This A Good Question/Topic? 0

## Replies To: Alphabetic binary tree sorting

### #2 Keerigan

Reputation: 10
• Posts: 55
• Joined: 04-February 10

## Re: Alphabetic binary tree sorting

Posted 10 February 2010 - 08:40 PM

Im not at my pc right now, so i don't really want to get into depth wiht this, but have you check out maps?
they are basically a struct with 2 items. The first one is the key that has to be unique for each struct, then the second can be whatever kind of data you want( including more structs or maps ).

The nice thing about this is that is that maps are always kept sorted by the key.

Don't know if that helps at all, but I thought that I would throw that out there before I put my phone away.

### #3 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: Alphabetic binary tree sorting

Posted 11 February 2010 - 06:37 AM

One problem I see is that your root node is uninitialized. I am sorry I ran out of time to look this over but hopefully someone else will pick up the task.

I prefer myself to wrap things like a tree by a second struct that has a pointer to the root node, then have a function insertToTree(tree, node) -- on of the things this give you is you can check if tree.root_node == null then make the new node the root node, else scale the tree and insert.

there is something fishy about your insert routine but I just ran out of time before I could really look into it. I could be wrong but I could "almost" sware you should be doing something like this:
```void insert(struct node* newone, struct node* current) {
if (newone->word[0] <= current->word[0]) {
if (current->left==NULL) {
current->left = newone;
} else {
insert(newone, current->left);
}
} else {
if (current->right == NULL) {
current->right = newone;
} else {
insert(newone, current->right);
}
}
}
```
-- Note that code is UNTESTED and written off the cuff in like 30seconds -- please look it over before you use it!

also note, while 'new' is not a reserved word in C it is generally a good idea to treat it as one. Not a big deal but should you ever want to migrate you code to C++ it might cause trouble.

### #4 not1975

Reputation: 0
• Posts: 51
• Joined: 26-December 06

## Re: Alphabetic binary tree sorting

Posted 13 February 2010 - 07:11 AM

```#include <stdio.h>
#define STRING_LEN 100

struct node
{
char word[STRING_LEN+1];
struct node* left;
struct node* right;
};

void insert(struct node* new, struct node* current)
{

//For now the program only sorts based on the first character
if(new->word[0] <= current->word[0])
{
if(current->left==NULL)
{
current->left = new;
}
else
{
insert(current->left, new);
}
}

else
{
if(current->right == NULL)
{
current->right = new;
}
else
{
insert(current->right, new);
}
}
}

{
printf("%s", node->word);
if(node->left != NULL)
{
}
if(node->right != NULL)
{
}
}

int main()
{
struct node* root_node = (struct node *) malloc(sizeof(struct node));
root_node->word[0]=' ';
root_node->word[1]='\n';
root_node->word[2]='\0';
root_node->left=NULL;
root_node->right=NULL;

char word[STRING_LEN+1];

FILE* word_file = fopen("C:\\wordlist.txt", "r");
while(1)
{
struct node* new_node= (struct node *) malloc(sizeof(struct node));

if(fgets(new_node->word, STRING_LEN, word_file)==NULL)
break;

insert(new_node, root_node);
}

system("PAUSE");

if(fclose(word_file) != 0)
return -1;
else return 0;
}

```

I initialized the variables for root_node. I'm still getting the same access violation error in the insert routine. But now it shows it coming from the first if statement in insert:
``` if(new->word[0] <= current->word[0])
```

I don't even know what that means. Is there something I'm doing with the arrays that's incorrect?

• Saucy!

Reputation: 6246
• Posts: 24,014
• Joined: 23-August 08

## Re: Alphabetic binary tree sorting

Posted 13 February 2010 - 07:50 AM

Compiling with warnings on yields an issue:
```tree.c:55: warning: implicit declaration of function ‘malloc’
tree.c:55: warning: incompatible implicit declaration of built-in function ‘malloc’
```

you need to include stdlib.h.

EDIT: If you're compiling as a C program, you should NEVER need to cast the return value of malloc. Requiring such in order to compile means exactly what you see above: you failed to include stdlib.h.

This post has been edited by JackOfAllTrades: 13 February 2010 - 07:52 AM