PTT數位生活區 / C_and_CPP (C/C++)

[問題] BST的建立

看板C_and_CPP (C/C++)作者 (orz811017)時間12年前 (2014/03/01 15:19), 編輯推噓1(1推 0噓 4→)
留言5則, 4人參與, 最新討論串1/1
上學期有上過DS 所以會用插入的方法建立BST 可是如果已經知道此Tree 的Preorder traversal 有沒有比較快的方法建立它呢?? 找到方法囉 分享一下~ http://zephiruswt.blog.51cto.com/5193151/885951 -- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.131.104
→
03/01 16:09, , 1F
需要知道兩個traversal結果才有辦法建立BST
03/01 16:09, 1F
推
03/01 16:33, , 2F
當然有, 用笛卡爾樹可以做到O(n log n) //這個複雜度是來
03/01 16:33, 2F
→
03/01 16:33, , 3F
自排序. 排完敘舊獲得中序了, 剩下用stack O(n)建出來
03/01 16:33, 3F
→
03/01 20:09, , 4F
感謝樓上同學XDD 我會做了 可是助教測資GG
03/01 20:09, 4F
→
03/01 22:07, , 5F
附上和 C/C++ 有關連的部分吧... 不然刪文
03/01 22:07, 5F
※ 編輯: orz811017 來自: 61.228.131.104 (03/02 11:13)
‣ 更多 orz811017 的文章
文章代碼(AID): #1J4OeTPO (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 orz811017 的文章
文章代碼(AID): #1J4OeTPO (C_and_CPP)