: 推 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配置空間節省很多
--
: → 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配置空間節省很多
--
All Comments