Thread: Need help with tree sort in C

  1. #1
    Registered User
    Join Date
    Apr 2012

    Need help with tree sort in C

    I suck at programming. It doesn't make sense to me. I'm not going to be programming in my career but it's part of my major. I'm desperately trying to get an c- just to pass. Would love some help. I would appreciate some explanation but it is not needed.

    Given the following struct:
    typedef struct node {
       int data;
       struct node * left;
       struct node *right;
    }tNode, *treeNode; 
    typedef struct list{
                     int data;
       struct list *next;
    }lNode, *listNode;
    First insert random numbers into the linked list
    listNode generateList ( listNode head, int size ); (10 points)
    Ask user to define the size of the list, like 100, 10000, etc.
    In the function use rand() to create numbers from 0 to (size-1), then store the numbers in the linked list.
    You can either insert the node from the beginning or the end of the list.

    Then sort the linked list using different sorting algorithms:
    Tree Sort
    listNode treeSort(listNode head); (20 points)
    The algorithm using a BST to sort the elements of an array is given in the slides.
    The basic idea of tree Sort of a linked list is as follows:
    1. Insert values in the linked list into a BST.
    2. Perform an inorder traversal of the BST and write the values back to the list in sorted order.
    Functions needed:
    1. treeNode BuildBST(treeNode root, int val); (20 points)

    2.listNode flatten(treeNode tree, listNode head);(30 points)

    Perform an inorder traversal of the BST and write the values back to the list.

    Use merge sort to compare the result.
    Merge Sort
    listNode mergeSort(listNode head);

    Remember to free the allocated memory at the end.

    I appreciate any help.

  2. #2
    Registered User
    Join Date
    Mar 2011
    linked list : google 'c linked list' . i immediately saw several simple algorithms that match your structure (first hit Building a linked list in C)
    binary tree: google 'c binary tree'. (first hit Building a binary tree in C [that site seems to have good simple examples]) (in this one, the function 'insert' === treeSort, function 'printout' is how you travese inorder'

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reading command line or text file...expression tree (sort of)
    By mathwork orange in forum C++ Programming
    Replies: 2
    Last Post: 02-13-2008, 08:52 AM
  2. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  3. Binary sort number arranging tree
    By newtocpp in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 04:19 AM
  4. Binary Tree Sort
    By BakAttack in forum C++ Programming
    Replies: 6
    Last Post: 02-06-2003, 11:07 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

Tags for this Thread