P
pc_newbie
is there any algorithm to create a breadth-first order binary tree?
M
Mike Wahler
pc_newbie said:
Yes. If I wanted one, I'd probably follow
the google-brick road.
-Mike
P
pc_newbie
where can i find it?Mike said:
M
Morris Dovey
E
Emmanuel Delahaye
In 'comp.lang.c' said:
Since when is an algorithm question a C-question?
P
pc_newbie
can't find any information about it yetMorris said:
M
Morris Dovey
pc_newbie said:
My apologies. I should have provided more info.
[1] Go to http://www.google.com
[2] Run a search on "binary tree"
[3] Click on link "Search within these results"
[4] Run subsearch on "breadth-first"
[5] Puzzle out a new subsearch because 12300 results seem like
too much to read.
O
osmium
pc_newbie said:
Very few people that say "use google" have actually tried their advice in
the case at hand. It is just an adult's answer to "why is the sky blue,
daddy?". Look it up, kid. I can't be bothered. If there *is* an answer
it's probably on google, it doesn't follow that the answer can be found with
a reasonable expenditure of effort. Or that the questioner knows the right
buzz words to actually find the answer. You need a tool kit of jargon and
catchy phrases and a certain amount of experience to google successfully.
This may help.
http://www.wikipedia.org/wiki/Breadth_first_recursion
Post any follow ups to comp.programming, this is the wrong newsgroup for
your question.
M
Martin Ambuhl
M
Mike Wahler
osmium said:
Exactly. My reply was a (apparently too subtle)
indication of this.
-Mike
O
osmium
Morris said:[5] Puzzle out a new subsearch because 12300 results seem like
too much to read.
Yes, that's the rub, what *is* the next step? Remember that the OP has used
up *all* his knowledge at this point. I have no desire to pursue this
particular example, this may yield a useful result at this point, it may
not. But I have been there many times in the past with similar problems
and the next step is far from clear. I know of no way of eliminating course
outlines, vu-graphs, and syllabuses from the list of hits. The cases where
I actually did this for myself were full of useless dreck. The best answer
is filtered through a human mind. Perhaps if he reposts as I suggested he
will still get a meaningful answer before the sun bloats up and kills us
all.
M
Mark McIntyre
Morris said:[5] Puzzle out a new subsearch because 12300 results seem like
too much to read.
Yes, that's the rub, what *is* the next step?
a) random selection
b) start from the top.
Either seems reasonable.
Then (and no offense to the OP) further use of the internet seems
highly unlikely to be useful. For is it not said "go not to the elves
for counsel, and also the internet, innit?" . Using the net for basic
understanding requires a high level of well, understanding, first....
M
Mark McIntyre
I can. I almost always find the answer, be it "is suchandsuch a make
of children's building bricks compatible with lego" or "whats
ankylosing spondylitis and can you recover from it". (answers are yes
and no, in either order).
What is required is a bit of common sense, and some understanding of
googling. To get the latter, learn. To get the former..
FWIW My own search turned up seve ral relevant references in page 1,
including some code samples.
M
Morris Dovey
osmium said:Morris said:[5] Puzzle out a new subsearch because 12300 results seem
like too much to read.
Yes, that's the rub, what *is* the next step?
Exactly so. My own next step was to do a subsearch on "C source"
(quoted) which reduced the number of entries substantially; but
reflected my own interests, rather than the OP's stated interest
(algorithms).
My rationale was that at least a subset of available algorithms
can be extracted from source codes; and that at least a rough
estimate of quality can be made by skimming each reference's C code.
[Somebody's Law: "Ninety percent of everything is crud."]
On the other hand, if the OP was looking for some in-depth
discussion (prose) dealing with "breadth-first order binary
trees" my approach would probably not be terribly productive.
O
osmium
Mark said:
Not at all. There are a great many things I can do if someone will open the
book up at the right page for me. But I will be damned if I know how to
*find* that page. I have no reason to believe I am unusual in that respect.
K
Keith Thompson
Morris Dovey said:
Sturgeon's. (That's Theodore Sturgeon, the late science fiction
author.)
P
pc_newbie
thanks a lot all guyspc_newbie said:
P
pc_newbie
you all guys are misunderstanding what i asked, what i want is how topc_newbie said:
create a breadth-first order binary, not to travel a binary tree with
breadth first order. but thanks a lot anyway, i should find the way by
myself.
that's what i want
1
2 3
4 5 6 7
normal binary is
4
3 5
1 2 6 7
S
Simon Biber
pc_newbie said:
#include <stdio.h>
#include <stdlib.h>
struct tree {
int value;
struct tree *left;
struct tree *right;
};
struct tree *create(int start, int max)
{
struct tree *new = NULL;
/* If this node should exist: */
if(start < max)
{
/* First, create it: */
new = malloc(sizeof *new);
if(!new)
{
fprintf(stderr, "Error allocating memory\n");
exit(EXIT_FAILURE);
}
new->value = start;
/* Then create its children: */
new->left = create(start * 2, max);
new->right = create(start * 2 + 1, max);
}
return new;
}
Call it with create(1, 8) for your example tree.
C:\prog\c>gcc -std=c99 -pedantic -Wall -W -O2 bftree.c -o bftree
C:\prog\c>bftree 32
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
My tree pretty-printing routine is quite interesting.
L
LibraryUser
pc_newbie said:
Now you have actually described your problem, assuming the digits
above are indexes of entry order and not keys. I have no idea
what you consider "normal binary".
BTW, your postings would be much more understandable if you used
upper case letters where appropriate, such as the start of
sentences or the pronoun I.
As others have pointed out, this is OT for c.l.c, but quite
topical for comp.programming. I have cross-posted this and set
follow-ups, so any further discussion should be there.