Random tree generation always creating regular tree
up vote
0
down vote
favorite
I have been doing experiments with tree algorithms in C. To check their correctness I have implemented a simple function to generate random binary trees. Somehow it seems that all the generated trees are regular, meaning that the tree is "full" and has exactly (2^height)-1 nodes.
I start at the root node and with a certain probability call the function recursively on left and right child. The function also has a depth limit. The created tree does not always have the full height, but it is always regular. My guess is that something is wrong with my random number generator.
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
/* tree node; data left out for brevity */
typedef struct node {
struct node *left, *right;
} Node;
/* simple helper function to print a tree */
void _print_tree(Node *node, int lvl) {
if (!node) return;
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("r");
_print_tree(node->right, lvl+1);
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("l");
_print_tree(node->right, lvl+1);
}
void print_tree(Node *root) {
_print_tree(root, 0);
}
/* make random tree with a given probability of creating a child
node and given maximum depth / height of the tree */
Node *make_random_tree(double prob, int maxdepth) {
Node *root = NULL;
if (maxdepth--)
root = calloc(1, sizeof(Node));
if (root) {
if (rand() < (double) RAND_MAX * prob)
root->left = make_random_tree(prob, maxdepth);
if (rand() < (double) RAND_MAX * prob)
root->right = make_random_tree(prob, maxdepth);
}
return root;
}
int main(int argc, char *argv) {
double prob = 0.5;
int maxdepth = 20;
if (argc > 1) {
char *ep;
prob = strtod(argv[1], &ep);
if (*ep) return 1;
}
if (argc > 2) {
char *ep;
maxdepth = strtol(argv[2], &ep, 10);
if (*ep) return 1;
}
/* random number generator is initialized properly?! */
struct timeval tv;
gettimeofday(&tv, NULL);
unsigned int seed = tv.tv_sec ^ tv.tv_usec;
srand(seed);
Node *tree = make_random_tree(prob, maxdepth);
print_tree(tree);
}
c tree random
asked 38 mins ago
streptococotte
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
0
down vote
favorite
I have been doing experiments with tree algorithms in C. To check their correctness I have implemented a simple function to generate random binary trees. Somehow it seems that all the generated trees are regular, meaning that the tree is "full" and has exactly (2^height)-1 nodes.
I start at the root node and with a certain probability call the function recursively on left and right child. The function also has a depth limit. The created tree does not always have the full height, but it is always regular. My guess is that something is wrong with my random number generator.
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
/* tree node; data left out for brevity */
typedef struct node {
struct node *left, *right;
} Node;
/* simple helper function to print a tree */
void _print_tree(Node *node, int lvl) {
if (!node) return;
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("r");
_print_tree(node->right, lvl+1);
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("l");
_print_tree(node->right, lvl+1);
}
void print_tree(Node *root) {
_print_tree(root, 0);
}
/* make random tree with a given probability of creating a child
node and given maximum depth / height of the tree */
Node *make_random_tree(double prob, int maxdepth) {
Node *root = NULL;
if (maxdepth--)
root = calloc(1, sizeof(Node));
if (root) {
if (rand() < (double) RAND_MAX * prob)
root->left = make_random_tree(prob, maxdepth);
if (rand() < (double) RAND_MAX * prob)
root->right = make_random_tree(prob, maxdepth);
}
return root;
}
int main(int argc, char *argv) {
double prob = 0.5;
int maxdepth = 20;
if (argc > 1) {
char *ep;
prob = strtod(argv[1], &ep);
if (*ep) return 1;
}
if (argc > 2) {
char *ep;
maxdepth = strtol(argv[2], &ep, 10);
if (*ep) return 1;
}
/* random number generator is initialized properly?! */
struct timeval tv;
gettimeofday(&tv, NULL);
unsigned int seed = tv.tv_sec ^ tv.tv_usec;
srand(seed);
Node *tree = make_random_tree(prob, maxdepth);
print_tree(tree);
}
c tree random
asked 38 mins ago
streptococotte
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have been doing experiments with tree algorithms in C. To check their correctness I have implemented a simple function to generate random binary trees. Somehow it seems that all the generated trees are regular, meaning that the tree is "full" and has exactly (2^height)-1 nodes.
I start at the root node and with a certain probability call the function recursively on left and right child. The function also has a depth limit. The created tree does not always have the full height, but it is always regular. My guess is that something is wrong with my random number generator.
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
/* tree node; data left out for brevity */
typedef struct node {
struct node *left, *right;
} Node;
/* simple helper function to print a tree */
void _print_tree(Node *node, int lvl) {
if (!node) return;
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("r");
_print_tree(node->right, lvl+1);
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("l");
_print_tree(node->right, lvl+1);
}
void print_tree(Node *root) {
_print_tree(root, 0);
}
/* make random tree with a given probability of creating a child
node and given maximum depth / height of the tree */
Node *make_random_tree(double prob, int maxdepth) {
Node *root = NULL;
if (maxdepth--)
root = calloc(1, sizeof(Node));
if (root) {
if (rand() < (double) RAND_MAX * prob)
root->left = make_random_tree(prob, maxdepth);
if (rand() < (double) RAND_MAX * prob)
root->right = make_random_tree(prob, maxdepth);
}
return root;
}
int main(int argc, char *argv) {
double prob = 0.5;
int maxdepth = 20;
if (argc > 1) {
char *ep;
prob = strtod(argv[1], &ep);
if (*ep) return 1;
}
if (argc > 2) {
char *ep;
maxdepth = strtol(argv[2], &ep, 10);
if (*ep) return 1;
}
/* random number generator is initialized properly?! */
struct timeval tv;
gettimeofday(&tv, NULL);
unsigned int seed = tv.tv_sec ^ tv.tv_usec;
srand(seed);
Node *tree = make_random_tree(prob, maxdepth);
print_tree(tree);
}
c tree random
asked 38 mins ago
streptococotte
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I have been doing experiments with tree algorithms in C. To check their correctness I have implemented a simple function to generate random binary trees. Somehow it seems that all the generated trees are regular, meaning that the tree is "full" and has exactly (2^height)-1 nodes.
I start at the root node and with a certain probability call the function recursively on left and right child. The function also has a depth limit. The created tree does not always have the full height, but it is always regular. My guess is that something is wrong with my random number generator.
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
/* tree node; data left out for brevity */
typedef struct node {
struct node *left, *right;
} Node;
/* simple helper function to print a tree */
void _print_tree(Node *node, int lvl) {
if (!node) return;
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("r");
_print_tree(node->right, lvl+1);
for (int i=0; i<lvl; i++) printf("%3s", "");
puts("l");
_print_tree(node->right, lvl+1);
}
void print_tree(Node *root) {
_print_tree(root, 0);
}
/* make random tree with a given probability of creating a child
node and given maximum depth / height of the tree */
Node *make_random_tree(double prob, int maxdepth) {
Node *root = NULL;
if (maxdepth--)
root = calloc(1, sizeof(Node));
if (root) {
if (rand() < (double) RAND_MAX * prob)
root->left = make_random_tree(prob, maxdepth);
if (rand() < (double) RAND_MAX * prob)
root->right = make_random_tree(prob, maxdepth);
}
return root;
}
int main(int argc, char *argv) {
double prob = 0.5;
int maxdepth = 20;
if (argc > 1) {
char *ep;
prob = strtod(argv[1], &ep);
if (*ep) return 1;
}
if (argc > 2) {
char *ep;
maxdepth = strtol(argv[2], &ep, 10);
if (*ep) return 1;
}
/* random number generator is initialized properly?! */
struct timeval tv;
gettimeofday(&tv, NULL);
unsigned int seed = tv.tv_sec ^ tv.tv_usec;
srand(seed);
Node *tree = make_random_tree(prob, maxdepth);
print_tree(tree);
}
c tree random
c tree random
asked 38 mins ago
streptococotte
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 38 mins ago
streptococotte
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 38 mins ago
streptococotte
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 38 mins ago
streptococotte
1
asked 38 mins ago
streptococotte
1
1
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
streptococotte is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
streptococotte is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209877%2frandom-tree-generation-always-creating-regular-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
streptococotte is a new contributor. Be nice, and check out our Code of Conduct.
streptococotte is a new contributor. Be nice, and check out our Code of Conduct.
streptococotte is a new contributor. Be nice, and check out our Code of Conduct.
streptococotte is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209877%2frandom-tree-generation-always-creating-regular-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
