CODEWITHSUNDEEP
csortingbinary-tree
Vadim Tor
Vadim Tor

Reputation: 40

How can I can sort binary tree by other parameter?

I am trying to count occurrences of every word in text. So I have stored all words and counts in binary tree:

typedef struct Node{
         char* word;
         int count;
         struct Node *left;
         struct Node *right;
         struct Node *parent;
} Node;

Now I need to sort tree by number of count. I can't just do while cycle and sort it, so I am wondering, which way I can do it?

Here is example of what I have now:

                               The - 3
                             /       \
                    Project - 1      of - 3
                     /    \          /    \ 
                 ....     ....      ....    ....

And I need to print top N words in text.

Upvotes: 0

Views: 215

Answers (2)

pm100
pm100

Reputation: 50110

Traverse the tree and extract the word and its count into an array of these:

struct WordAndCount {
  char * word;
  int count;
};

Then use qsort to sort the array. You will need a custom compare function that compares WordAndCount.count;

Upvotes: 1

Hisham H M
Hisham H M

Reputation: 6798

What is your criteria for storing items in the tree? Is it the case that nodes to the left always have lower count than nodes to the right? If so, to get the top N words you do a post-order traversal keeping a counter and stop it when it reaches N.

Upvotes: 0

Related Questions