: 推 jennya: 1.阵列建二元树：(X) 不必使用BFS，使用for循环将阵列跑一 04/07 01:55
: → jennya: 遍就可以做到，省下bfs queue的空间 04/07 01:55
: 推 Ninja5566: 楼上第一题怎么用for 建complete b-tree?我还真想不到 04/07 02:04
: → Ninja5566: 而且还是在不用额外内存的情况下 04/07 02:04
: 推 Ninja5566: 利用pre or inorder traversal建还是需要暂存parent 04/07 02:07
: → Ninja5566: 不然要怎么返回parent node? 04/07 02:07
: 推 jennya: @Ninja5566 你说的对。我原本的想法像是这样： 04/07 02:44
: → jennya: https://www.paste.org/97946 04/07 02:44
: → jennya: 但是仔细一想这的确和BFS差不多。这部分我的确是呛原PO呛 04/07 02:44
: → jennya: 错了。谢谢~~ 04/07 02:44
忍不住认真一下…
其实这是可行的，所以jennya大并没有呛错（疑？）
这就这很像帮array-based tree写一个iterator
顺手写了一下code，没有仔细改，可能不是很concise
https://pastebin.com/AidafGZP
这其实是在工作中可能会出现，很实际的需求：
你在开发一个micro-controller程式，这个环境没有heap，只有超小的stack
memory中已存在一个以array表示的binary search tree
请写一个function在O(N)时间及O(1)空间做完in-order traversal
(N=number of elements)
Notes:
* O(1)空间表示严格来说不能用recursion，否则是O(log(N))
* 我的算法走访每个edge两次，所以是时间O(N)
* 以array表示binary tree是很实继的做法，尤其当资料是immutable时
比为了每个node分别在heap配置空间节省很多

讨论下去就要去softjob板啦XD

讨论串还不错欸，学到很多XD

他是说建树 不是 traverse

你讲的是另一题，traverse tree’s inorder with iteration

稍微改一下树不就建起来了吗

建树是另外一回事, 除非你另外存在struct不然node不知道自己的parent还有自己是左子还右子

...我们讨论的是complete binary tree

建树还是要o(log(N))吧我是指暂存

他说省下queue的空间, 你其实也是做一样的事情, 只是把空间移到struct而已换句话讲人家用BFS用queue,而 你用不同方式纪录ptr而已

建树当然至少要O(N)

如果是指暂存,不计树本身,那jennya的for loop 应该较好?