BST: print tree in sorted order using another key

I have next structures code in C for my binary tree:

struct student
{
    int studentID;
    char lastName[MAX_LENGTH];
    char firstName[MAX_LENGTH];
    float amount;
};

struct node
{
    struct student* record;
    struct node* left;
    struct node* right;
};

Records are inserted to the tree using studentID field as a key. When I'm printing the tree in order of studentID all is fine. But I want to print the SAME tree in order of lastName field.

I have only one idea: copy tree to array, sort array and display array.

Is there is any another solution?

Answers


You can build and maintain multiple binary search trees in parallel, optionally folding them into a single multi-indexed data structure:

struct node {
    struct student *record;
    struct node *left_by_id, *right_by_id,
                *left_by_name, *right_by_name;
};

Obviously, all the BST operations have to be modified for this to work: e.g. to insert a new struct student*, you must tie a single node into two trees.


Create an index for lastName. You can use another BST which will store a lastName as key and a pointer to the corresponding node in your original BST.

struct indexNode {
    char lastName[MAX_LENGTH]
    struct node* originalNode;
};

You can go on inserting into this tree while inserting data in original tree.

This way you will have to spend O(log n) space to store extra index tree but will reduce your time for searching based on lastName to O(log n). Also, practically you will be storing only a key and pointer to a node for each element.


Need Your Help

Mapping LDAP users to Django users with Django Auth Ldap

python django ldap authentication

I'm using Django 1.3 and Django Auth Ldap 1.0.6. and I'm trying to have the users who have a special status on the LDAP Server (admins) have the same status in my Django application.

How to sort textbooks by type by color code, or category in bookweb using html, javascript, css or other?

javascript html css table cgi

I am currently trying to sort a textbook list that is generated dynamically by bookweb ( a bookshop cart solution). I want to order the cart by the textbook type either prescribed or recommended.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.