[問題] 不固定子個數的Tree

看板C_and_CPP (C/C++)作者karaokstar (卡拉歐科史達)時間13年前 (2013/01/18 19:57)推噓1(1推 0噓 3→)

留言4則, 4人參與討論串1/2 (看更多)

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) Microsoft Visual Studio 2010 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) #include<vector> 問題(Question)：大家好, 小弟現在想要實作一個每個節點無固定個數子的樹想法是這樣的話class Node的結構裡面必須要有個可以動態成長連結child的pointer vector<Node> *children, 一個pointer指向一個vector, vector儲存Node vector<Node*> children, 這Node本身有一個Vector, 裡面存放著pointer to Node 想請問一下這兩種實作上哪種比較好，或者說比較符合我的需求還是說有更好的實作方法可以提示一下, 因為我只有想到這兩種小弟想要實作出的樹狀結構如右圖 http://ppt.cc/BHrX 謝謝大家! 餵入的資料(Input)：預期的正確結果(Expected Output)：錯誤結果(Wrong Output)：程式碼(Code)：(請善用置底文網頁, 記得排版) 補充說明(Supplement)： -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.213 ※ 編輯: karaokstar 來自: 140.112.28.213 (01/18 19:58)

→

linotwo

01/18 20:16, , 1^F

01/18 20:16, 1^F

這樣的話樹狀結構會變成 root | v child-->child-->child 其實這個樹的結構有點像prefix tree 當我要insert進node的時候，必須先判斷目前的字串是否已經有node存在 ex: 假設我要insert的是 bdc, 會先從root指到的child判斷是否已經有b這個node 如果有就接下去search b的node是否有child是d這個node, 以此類推沒有就create一個新的b node, 再create d node以及 c node接起來那如果用到list的結構的話，在search node時就必須要從頭trace一次我現在是想到說用 map<key, node> 這種形式, 如果要找是否已經存在就可以用 map.find or map.count 這兩個func

→

legnaleurc

01/18 21:52, , 2^F

01/18 21:52, 2^F

→

loveme00835

01/19 15:13, , 3^F

01/19 15:13, 3^F

請問所謂的raw pointer就是自己在class定義的那種 pointer to sth. 嗎所以如果class裡面想要用pointer去指, 應該用什麼樣的方式呢? 像是legnaleurc大大提到的shared_ptr ?

推

yoco315

01/19 19:32, , 4^F