作者AmigoSin (>3<)
看板C_and_CPP
標題[問題] Binary Search Tree實作問題 (Structure
時間Tue Sep 8 13:57:27 2020
各位大神好～
肥宅我最近複習資料結構，
在BST的Insertion遇到了一點問題。
程式碼如下網址
https://reurl.cc/WLrA99
註解的部分是本肥手動Insertion，
測出來結果都正確。
目前已知函式運作後，
node有成功new出來，
但parent 沒有指到new出來的node，
請問我的寫法哪裡有問題QQ？
是因為遞迴呼叫到Leaf的時候，
Leaf的child pointer指向NULL，
而函式複製了一份NULL傳進去遞迴，
所以這個NULL不是原本指向的NULL?
(Call by value?)
**
補充說明：
參考置頂的新手十三誡文的第13點後
我使用pointer to pointer終於能成功了
（果然還是要多爬文）
雖然我還在理解為何一階pointer不能成功XD
非常謝謝各位熱心的回文指點！
原始版本：
https://i.imgur.com/MACCGeW.png
二階指標版本：
https://i.imgur.com/sIEmi1j.png
參考文章：
https://i.imgur.com/nBqyKym.png
手機排版請見諒><
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.47.226 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1599544650.A.FA8.html
1F：推 b0920075: 新new的Node沒給上一層的Node阿09/08 14:24
2F：推 NTUmaki: 你的insertion 函式沒有回傳值09/08 14:27
4F：→ AmigoSin: 抱歉各位我的指標觀念不太好09/08 15:22
5F：→ AmigoSin: newNode(30) 回傳的新Node位址，assign給root09/08 15:29
6F：→ AmigoSin: root是上一個遞迴的root->right，這樣做會連不上嗎09/08 15:32
7F：→ AmigoSin: 我知道有方法是把Node指標當作函式的回傳類型去實作09/08 15:34
8F：→ AmigoSin: 我只是想釐清我指標的盲點QQ09/08 15:35
9F：→ AmigoSin: 謝謝1F和2F大大的留言09/08 15:35
10F：推 NTUmaki: 我剛剛測試你的寫法 直接傳Null進去new 然後輸出位址會是09/08 15:42
11F：→ NTUmaki: 0x0 函式改成有回傳值的就會有位址09/08 15:42
12F：→ NTUmaki: 我也沒想過這種寫法@@ 不過實際測試出來你這樣寫 最後roo09/08 15:43
13F：→ NTUmaki: t的child pointer 會沒位址09/08 15:43
14F：→ loveme00835: 你可以在 Insertion() 前後觀察一下指標值有無變化,09/08 16:13
15F：→ loveme00835: 你只有改到參數, 而不是傳進來的指標物件本身09/08 16:13
16F：→ AmigoSin: 謝謝NTU大大幫我測試XD 我怕如果不釐清其中的運作機制09/08 16:19
17F：→ AmigoSin: ，以後還是會生出這種可怕的code (掩面)09/08 16:19
18F：→ AmigoSin: 謝謝Love大！所以pointer當參數只是複製一份和pointer09/08 16:28
19F：→ AmigoSin: 相同的值（一樣的記憶體位置?）再傳到函式裡面作用對嗎09/08 16:28
20F：→ AmigoSin: 那我傳進去NULL和函式裡面的NULL如果位置一樣，應該會09/08 16:31
21F：→ AmigoSin: 指向同一個生出來的物件會，這樣觀念對嗎？ 09/08 16:31
22F：→ AmigoSin: 1. 是因為傳進來當參數的NUL和原本的right的NULL實際上09/08 16:58
23F：→ AmigoSin: 指向不同的位置嗎？09/08 16:58
24F：→ AmigoSin: 2. 還是因為NULL根本不指向任何記憶體的實際位置，只有09/08 16:58
25F：→ AmigoSin: 在我new的時候才分配記憶體位置給該層遞迴指向的NULL。09/08 16:58
26F：→ AmigoSin: 所以我new出來的物件只停留在newNode的那層遞迴，原本09/08 16:58
27F：→ AmigoSin: 的child則沒有改到嗎？09/08 16:58
28F：→ AmigoSin: 謝謝NTU大和Love大不厭其煩為我解答和測試><09/08 16:59
29F：→ AmigoSin: 我測試new前後的結果，new出來的物件有記憶體位置和正09/08 17:01
30F：→ AmigoSin: 確的data值，但回到上層遞迴後原本的right又變回NULL了09/08 17:01
31F：→ AmigoSin: 謝謝各位，我看完置頂的新手十三誡第13點後好像明白了09/08 17:50
32F：→ a27417332: Insertion的第一個參數型別到底是Node*還是Node*&09/08 19:04
33F：→ loveme00835: 看到 *& 我就笑了 :D09/08 19:37
34F：→ AmigoSin: 哈哈哈*&是我剛剛參考置頂文章再測試XD09/08 20:22
35F：→ AmigoSin: 我還在研究置頂的十三誡XD09/08 20:22
37F：→ AmigoSin: 原本發問的程式碼，避免點進去看到我在亂改程式碼XD09/08 20:40
※ 編輯: AmigoSin (36.224.102.202 臺灣), 09/08/2020 21:05:50
38F：推 asd3136396: 要往下遞迴Insertion(root->right, data); 09/09 16:51
39F：→ asd3136396: 之前先檢查root->right == NULL 09/09 16:51
40F：→ asd3136396: 是的話root->right = newnode(data); 09/09 16:51