search trees...

[nadleeh]

how would i go about sorting multiple items in a binary search tree..
for example if i have a list of first last and middle names and i want to sort it in a tree by last name, how would i store all three of them in each node..
should i create a struct with them in it and a separate struct for my tree?
whats the easiest way to do this?

[abhimanipal]

There are 2 concepts involved here

Concept 1: In a Binary Search tree if you print all of the nodes inorder then the output will be an array sorted in ascending order. Extending this to your problem, you can use the last name as an index for inserting data into the bst tree. Then when you print the data it will be sorted in ascending order by last name.

Concept 2: A binary search tree is basically a collection of structs. You can store any number of names in a struct. So you struct could be

struct person
{
  char* firstName;
  char* lastName;
  char* middleName;
};

Disclaimer: If you want to sort your BST by first name, last name, middle name simultaneously then the problem is a hard problem

[nadleeh]

Ok that makes so if I have my struct how would I go about sorting it into my tree.lets say my struct looks like this

struct tree {
      char nameLast[10];
      char nameFirst[10];
      struct tree *left, *Right;
      }NODE, *root;

Is this correct.. And like I said how would I sort it

[Narue]

You don't sort a binary search tree because it's inherently sorted. Just use the last name as your key for insertion.

[nadleeh]

So I need to store my info in a linked list and then index them in the tree?

[Narue]

Dude, wtf. Just build your freaking tree. It's already sorted! You don't need a linked list, you don't need a separate sorting step:

#include <stdio.h>
#include <string.h>

struct person {
    char first_name[20];
    char last_name[20];
};

struct node {
    struct person data;
    struct node *link[2];
};

struct node *insert(struct node *root, struct person data)
{
    if (root == NULL) {
        root = malloc(sizeof *root);
        
        if (root != NULL) {
            root->data = data;
            root->link[0] = root->link[1] = NULL;
        }
    }
    else if (strcmp(data.last_name, root->data.last_name) < 0)
        root->link[0] = insert(root->link[0], data);
    else
        root->link[1] = insert(root->link[1], data);

    return root;
}

void display(struct node *root)
{
    if (root == NULL)
        return;

    display(root->link[0]);
    printf("%s, %s\n", root->data.last_name, root->data.first_name);
    display(root->link[1]);
}

int main(void)
{
    struct person people[] = {
        {"John", "Doe"},
        {"Joe", "Public"},
        {"Random", "Person"}
    };
    struct node *root = NULL;
    size_t i;

    for (i = 0; i < sizeof people / sizeof *people; i++) {
        struct node *temp = insert(root, people[i]);

        if (temp == NULL) {
            fputs("Error allocating memory\n", stderr);
            break;
        }

        root = temp;
    }

    display(root);

    return 0;
}

Do you even know what a binary search tree is?

[nadleeh]

umm obviously not.. If understood them completely why would I be here asking questions to get a grasp of it...

[Narue]

If understood them completely why would I be here asking questions to get a grasp of it...

Forums are insufficient when what you really need is a book or tutorial dedicated to the topic. It's difficult to ask a question that makes sense without at least some foundation in the basics, which your questions so far suggest you lack.

To be specific, asking how to sort a binary search tree is nonsensical. If one understands the basic concept of a binary search tree, sorting isn't an issue.

[nadleeh]

My English isn't the best so sometimes phrase things well. Basically I already have a tree containing last names. And I wanted to know the easiest was to also store the additional info in each node. But I figured it out so nvm. I understand the basics just don't know everything.

[Narue]

If that's what your problem was, the question you asked is completely different. But I'm glad you figured it out.