generating k permutations of a series and then generating all possible binary trees from them
ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
generating k permutations of a series and then generating all possible binary trees from them
I am trying to solve a problem , (1) Take a positive integer (say K) as an input from the user. Generate all the K! Binary Search Tree from numbers {1,2,…,K}. i.e. all permutations and then I have to check For each K! BST, check whether that particular BST is full binary tree, complete binary tree and perfect binary tree. Can any one share the code in C or any programming language.What I generated is permutation of all the number of a given series in a file.
Code:
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#define N 10
void print(int *num, int n)
{
FILE *fp;
fp=fopen("result.txt","a");
int i;
for ( i = 0 ; i < n ; i++)
// printf("%d ", num[i]);
fprintf(fp,"%d ",num[i]);
fprintf(fp,"\n");
fclose(fp);
}
int main()
{
int num[N];
int *ptr;
int temp;
int i, n, j;
printf("\nHow many number you want to enter: ");
scanf("%d", &n);
printf("\nEnter a list of numbers to see all combinations:\n");
for (i = 0 ; i < n; i++)
scanf("%d", &num[i]);
for (j = 1; j <= n; j++) {
for (i = 0; i < n-1; i++) {
temp = num[i];
num[i] = num[i+1];
num[i+1] = temp;
print(num, n);
}
}
return 0;
}
but this generates all permutation and stores them in a file result.txt now from that file how do I read and create Binary search tree's that is not clear to me.
Honestly, I'm not sure how someone with the skill on display would be having trouble with either reading the file or creating the tree. You obviously know how to write files, so I assume you know how to read them. And each line is just a single integer, so there's no parsing involved other than atoi.
A typical C binary search tree implementation would involve a Node struct containing data (the integer) and two pointers: one to each child. You then implement the standard algorithms for, say, the insert operation. There are zillions of examples online.
That code opens, writes to, and closes the file n times. How ... inefficient.
@dugan,
You're likely correct. I do wonder if the code was also part of the given part of the problem and therefore the question is then the actual assignment.
There is so very much information about B-tree's on the web. This is a very old programming concept. Please take the time to look a bit further on this subject.
You obviously know how to write files, so I assume you know how to read them. And each line is just a single integer, so there's no parsing involved other than atoi.
that assumption is wrong. It is not just atoi there is strtok,fgets,atoi,while + fgets + strtok or strchr + atoi or strtol every thing required here some thing similar to programming a shell in c. I had a deadline which I missed so i could not implement all this in a hurry.
do wonder if the code was also part of the given part of the problem .
No the code was not given as part of problem it is mostly copy paste work from various sources on internet.I searched permutations program in C and implemented file handling in it (that was my modification) later on found binary search tree code and then merged that with this permutations code , now the only difficulty I am having is in reading line by line from file some thing similar to if (fgets(command, 4097, stdin)!= NULL) {
Code:
// accept empty lines
if (!strcmp(command, "\n")) {
continue;
}
// parse the input
int nwords = 0;
char *token;
token = strtok(command, " \t\n");
while (token != NULL) {
words[nwords] = token;
token = strtok(NULL, " \t\n");
nwords++;
}
words[nwords] = NULL;
if (words[0] == NULL) { // prevent it from segfaulting when spaces are typed
continue;
}
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.