C - Possible to create a tree level by level?

I'm studying trees right now, and I'd like to find some examples of how to create a binary(or k-ary) tree one level at a time, since I can't find it anywhere and my brain isn't working.

Anyone have any input on this? C's lack of functions doesn't help either. Thanks ahead, /prog/

http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

Create an array long enough to store all the nodes ( 2*(2^depth)-1 or something )

Store first level (the root element) at the 1.st index position.
Store second level at 2 to 3.
Store third level at 4 to 7.
Store fourth level at 8 to 15.
etc.

Traversing the tree in this implementation:
root node index 1
left child index 2*n
right child index 2*n+1

>>``C's lack of functions''
wait what

>>2
tree-as-array
Isn't this called a heap? But anyway, it's beside OPs point. AFAICT he wants to know if he can create a tree breadth first, which he can

One level at a time?  Keep a running count of the lowest depth of the tree and how many nodes are on that level.  Save the root, it should always be k*x where k is the arbitrary number of leaves any node can have and x is the depth.  If you have added k*x leaves to the given level, reset the counter to zero and then start adding nodes to the next level.

If the method is not of your concern and its only the results in which you are interested, add the new node anywhere, count for the level above the new node, then rebalance the tree if need be.

>>2
That's assuming my tree is going to be complete which it isn't, and that I know its length from start, which I don't. I guess I should have mentioned that, sorry.
>>4
Could you elaborate? I think I kind of understand the concept but it's still not very clear to me. Code or pseudo-code example?


Thing is I'm facing an np-complete problem, and I want to build this tree one level at a time, checking if I reach the solution at each pass. I'm doing this because in my case the first solution I find will be the best(looking for the shortest path).

I already determined that a recursive function is probably not what I want for this purpose(could be wrong), but I've never seen an iterative tree creation function(haven't been programming for long), so that's why I'm a little lost.

>>5
A lot of people have been asking a similar question lately, and the answer is to read your Xarn.¹

______________________________
References
¹ http://cairnarvon.rotahall.org/2010/02/28/search-trees-are-easy/

>>5
So you you think you want a tree, but you really want to do a breadth-first search?

>>7
For a breadth-first search I need a complete tree. My goal was avoiding the complete tree building part, which would be more efficient in my case. Xarn's post doesn't help me with this either, I already know how to build the complete tree and do a breadth-first search.

>>8
You're only adding the nodes as you need them, with Xarn's algorithms. You aren't first building the entire tree and then searching breadth-first, that would be retarded.

Hello, Xarn. When are you going to realise that Christopher's solution of not allowing comments under your articles but rather using e-mail is superior?

>>10
That's great if you want to answer the same question a million times, or, in Christopher's case, want to be able to pretend your blog actually has readers when it doesn't. Not so much when you're interested in actual discussion, though.
The only advantage would be that your pages become perfectly static, which doesn't make up for the downsides, really.

>>9
Okay I just realized that, but I can't read python, which leaves me in a shitty position.

>>12
Thats like saying you can't read pseudo code

>>13
That's saying you can't read pseudo code
FTFY

>>12
howdy number 12
welcome to /prog/
lots of people here will tell you to read this 600-page reference book or that massive library of code without offering any help. also, prepare to be ridiculed and ostricized because you're not in the clique. yep, it's exactly like high school - lonely teenagers being jerks to each other. don't mean to get you down, but if you really need programming help, this isn't the place to get it.

>>15
DON'T HELP ME

>>16
i didn't ask for help, gosling :) and it's not like you erudite nose-thumbers were going to help him anyway.

>>15
It's because we care.

>>18
unsage :)
ps. i don't think you do

>>14
I'm all for certain kinds of Grammar Fascism, but even I can't help but feel that you were taking the piss with that one.

i love how all the clique-kids sage any post that they recognize is not theirs

>>21
I think you are misunderstanding the purpose of sage. It is not some sort of thread voting mechanism, it's a way of saying, "don't bump this thread with this post". There are many good reasons not to bump a thread, for example, when they are not directly related to the topic. Are you saying that those posts should of bumped the thread? Is your quality threshold that low.

>>21
Honestly, it's a rare post on /prog/ that's even worth reading, and I prefer not to make pretenses about my own. I'm not saging you, I'm saging me. How could it be any other way? Trite Zen notwithstanding, there's bound to be a relevant shii^tchan bug. One I would like to use for evil.

>>15,21
Butthurt because people make fun of him for not being able to understand capitalization.

I got my program running and running super fucking fast. Thanks /prog/, for what it's worth

>>21 insinuating that sage is a negative thing?
>>22,23 having to set >>21 straight?
>>24 saying "butthurt"?
OP apparently not knowing how to build a tree with linked lists?

What the fuck is going on here, /prog/?

30 Name: Anonymous 2010-12-10 8:58

31 Name: Anonymous 2011-02-03 7:26

32 Name: Anonymous 2013-09-01 14:36

　 　　　　 　　ﾄ､.,__　　　　　　　 ／7'iヽ.　　　八雲　紫　　十七歳（自称）
　　　　　 　　|:::::!　｀ヽ､__,,....,,___!::::!　l:::|
　　　　　　 　';::::l‐ ''´|::|　 　 　/:::/-､|/　　　　　┬ l二l　ノ ﾉ￣i_,
　　　　　 ／　＼'､ 　 V　　　/／　／　｀ヽ.　　　土 l二l　イ -‐ｧ
　　　　 / 　､__ｒ-ヽ＞'￣`r‐'"ヽ!-'､､,__　　 ':,　　　 ノ　!_,　| _メ､__
　　 　　! r''「＞'-‐'"´￣￣ ｀ヽ､7_ゝ-､ノ ,　.i
　　　　r'Y´　／ _/l_　;　　　 ; __!_　｀ヽ､/ｰ､k_　　　 __l_____,!__　-‐ｧ　　--'--　 ﾉ-┼‐
　　　rく/　 ,'　´/ _」_,ﾊ　 　,ﾊ_」__｀ ',　 ヽ/　_」_　　　 !　 / 　--┼‐‐ __'三'__ 　 -┼‐
　　 「´7 　 i　 ｧ'i´ '｀!` ',　 /' i´ 'ﾊ`i !　　Y､___〉　　_,>く..__　　､ﾉ　　|　口　」　____|____
　　 `イ 　 ﾉﾚ,ﾊ. '､_,r!　 ﾚ'　　!,__り.ﾉ`ﾊ　ﾊ,.イ　　　　　　　　　　　　　　　　　　　　　　　（自称）
　　　 ﾉ　 )へ/ !"´　 　　 . 　　　｀"7ノレ' i　 `ヽ.
　　　´⌒ﾚ〉　! ﾍ. 　 　　._ _,.　　 　,ｲ 　',.　 '､ 　　｀':,
　　　　 ,./　ﾉ 　 ,!` :.､, 　 　 　 ,.イ /i,. -'‐'"`i ｀ヽ､　 ':,
　　　 ノ,'　〈　 r'__,,.イ i｀''＝ '"i.　ﾄ､/　 　　 i〉ヽ, !く{　 i
　　,:'　 ! 　 !ヽ(ﾍ!:::::'､`ヽ.__,. イ ./:::i　　　　/　く」ヽ　　i
　/　　ﾉ Y´:::::くﾝゝ:::::':､/ムヽ／:::;「ﾄ､,____,ﾊﾄ,　ﾚ'　 i　ﾊ
　!　 〈　 i､:;_::::/V':;::::::::Yl+lY::::::/:::!:ヽ､___i_ﾝ7　 　 ノ!〈　i
　',　　.) ﾊ:::::'':i:::::::::＞'::ヽ+l+ﾝ'::／!:::::::::::::!。i 　 ,:'´　!/_/
　　)' （ 　 ';:::::::ヽ;:::::＼::::::Y/:／:::::!::::::::::::::::::!　/　}＞!ﾍ_」
　くﾝく{ ヽ. .';::::::::::i｀::::::::ヽ:::!':::::::::::::!::::::::::::::::,' .,'　　ノ i
　　　　〉　!/i:::::::/::::::::::::::::Yo::::::::::::';:::::::::::::::i　iヽ. 〈／
　　　　　(l　|::::;:'`'':::::::::::::::l;o:::::::::::::ゝ､:;___ノ ,'　 '（
　　　　　　 ,ｧ'::::::::::::::::::::::;':::::::::::::::::::::::::!/`'（
　　　 _,,..;:'く::::::::::::::::::::::/i::::::::::::::::::::::::::;ゝ,
　r‐''"／　/ヽ､:;______/TL__________;;::イ .ハ
　|::::,:'　　,'　　　　i　　　!　　　　i　　　', 　 ':,
　|:,' 　　/　　　　 |　　　 ',　　 　:　　　 ':,　　ヽ.

33 Name: Anonymous 2013-09-01 16:09

:::::::::: ::: : : : :　:　　 ___,,,... -‐- ､..,,__
:::: ::: : : : _,,.. - ''"´　　　　　　　 _,,...,,_｀ヽ､　 T7
::: : : : ／　　　　　　　　　　　　　｀ヽ. ｀':,　Y 'ｧ'"´ ﾊ
　　 ,:'　　　ヽ､　　　　 ﾉ__　　ﾄ､.,__ノ　　 !　|ﾉ　　/! |
く＼ﾍ_ゝ-､_ﾉ´｀iコ二ﾊ､__ﾊ_,ﾍ.　　　　,.ム/　　.　|　!　　　 ,,.. --────
　＼ﾊ､_＞‐''"´:.;:.:.:.:.:.:.:.:.:.';:.:.:.:.`'' ｰ''7-､_!__∠___!_/ 　 ／
_ノ´Y´/:.:./:./:.:.;':.:.:.i:.:.:.:.:.:.:.!:.:.:.ﾊ:.:.:.:ヽ.__,.ム､_ﾊ.､　　 ,'　　あ　特　喘　今
L___,':.:!:.:.:.!:.:!､:;_!_;.:;ﾊ:.:.!､:_/;;::イ:.!:.:.:!:.:.';.:.:.:.:.ｷ ｀ヽ!　　|.　　げ　別　息　日
..└i:.:.:'､:.:.!.ﾊ__」__ﾊ! ﾚ' ｧｰr-‐ｧ'i7:.:.!:.:.:!:.:.:.:.:.!ｭノ」 　 !.　　る　に.　の　は
　　!:.:.:.:.ヽ:!〈'ヽ,.ﾊ`　　' 　 i　 r;ﾝi__;ﾊ__」:.:.:.:.:|/´　 　 |. 　 わ　見　調
　　|ﾊ___|:,ﾊ. 。 ゝ'　:.:.:.:.:..　`"´,.,.,!:. o :!:.:.:.:.:.i　　　 ∠.　　　　 逃　子
　ｾﾞｪ　';.:.:.:.! '"'"　　　　　　　u .,'.:.:.:.!:.|:.:.:.;.:;:'　　　　 |　　 　　 し.　が
. ,.､　　ﾉ:i:.:..':､　　　 i´￣ヽ. 　 ,/:.:.:.:;':.:!:.:.:.i/| ｾﾞｪ 　 .!　　　 　 て　悪
(　_)　,':.:.!:. ( )｀＞.､.,` -‐ ',,.イ/:.:.:.:.:.:.:! ,.-'-､　　　　 |　　　　　　　 い
　　　i:.: (　) :.:.:.ノ:.:.:.!｀T'´ __,/:.:;':.:/'‐ /　　　ｿ､.　 　 !　　　 　 　　 か
　　　!:.::/.:.:.:／ ';!イ ｀7i´　,':.:.:/:./!:: /　`ｰｧ'´､ ヽ.　　',　　　　　　　ら
　　　!:/:.r'" ,.'´　/ヽ/ムﾚ'i.:.:.;':.:i rノ　　 /ｰ-､ ヽ､!,_　ヽ､.,_____________________
[__＞「7」　/　　 ,.-､　 | 　!:.:.:! ,.:´ __　　/　　/｀ヽrｧﾍ
　くノ:.:.:!rく_　 ,./ 　 'ｰ-､ [iコ' !　´　ヽ. i 　./　 /｀〉 /i
　〈:.:.:.:.:iヽﾍ>i/ 　　　　 ﾉi:.:.:,ﾊヽ､　 　 ｿ- '､_ノ_,.:'イﾝ
　 ヽﾍ:.」　i7´iヽ､_____,.ｲｉ Lﾊ_」､ i ｀二´7'' ｰ-‐' i/
　　　　　 i'　 `'ｰ-'-- ' |'　　 ハ !　　 ｀ '' ｰ-‐'Y

---

Don't change these.

Name:		Email:
Entire Thread Thread List

All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -