CODEWITHSUNDEEP
cdata-structuresrecursiontreebinary-tree
user2097471
user2097471

Reputation:

Binary tree insertion sort in C

Hey can anyone explain how to sort a binary tree using insertion sort in C language where time complexity is an issue. I am just learning to code. Thank you guys!

Upvotes: 0

Views: 1802

Answers (3)

Adrian Statescu
Adrian Statescu

Reputation: 99

#include <stdio.h>
#include <malloc.h>
#define FIN "algsort.in"
#define FOUT "algsort.out"

struct Node {
   int val;
   struct Node *left;
   struct Node *right;
};

typedef struct Node node;

void insert(node **bt, node *Node) {

if( !(*bt) ) {

     *bt = Node;

} else {

        if( Node->val < (*bt)->val )

            insert(&((*bt)->left), Node);

        else

            insert(&((*bt)->right), Node);
 }
 }

 void printout(struct Node *node) {

   if(node->left) printout(node->left); 

   printf("%d ", node->val);  

   if(node->right) printout(node->right);
 }

 void postorder(struct Node *node) {

      if(node->left) printout(node->left);   

      if(node->right) printout(node->right); 

      printf("%d ", node->val);  
 }

 int main () {

     int i, n, elem;    

     node *curr; 

     freopen(FIN, "r", stdin);

     freopen(FOUT, "w", stdout);

     node *bt = NULL;

     scanf("%d", &n);

     for(i = 0; i < n; ++i) {

        scanf("%d", &elem); 

        curr = malloc( sizeof(struct Node) );

        curr->val = elem;

        curr->left = NULL;

        curr->right = NULL;

        insert(&bt, curr );

     }

    printout( bt ); 

    return(0);
  }

Let's say that algsort.in contains the following array of integers:

algsort.int -> 9,8,7,6,5,4,3,2,0,1,-1;

algsort.out -> -1,0,1,2,3,4,5,6,7,8,9

Upvotes: 0

Cody
Cody

Reputation: 145

It's worth noting that there's a certain terminology to use here. A binary tree is a data structure where every node has at most two children. There are no conventions for ordering of nodes in a binary tree.

A binary search tree is a binary tree such that for given a node N all nodes in the left subtree of N are considered "less than" N and all nodes in the right subtree of N are considered "greater than" N. You could also let nodes considered "equal to" N in the tree, as long as you consistently define them to be put in the left subtree or right subtree.

As others have suggested, your best best is either to amend the code to construct a binary search tree instead of a normal binary tree, or convert the binary tree into a linear data structure and sort it.

Upvotes: 1

James Oravec
James Oravec

Reputation: 20391

If you coded the binary tree in the traditional sense, then when you add items to the tree, it will preserve the sorted order. You can get the full list of items in order by traversing the tree. I would recommend you read:

Also take a look at: http://nova.umuc.edu/~jarc/idsv/lesson1.html

Upvotes: 0

Related Questions