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

[問題] Binary Search Tree實作問題

看板C_and_CPP (C/C++)作者 (>3<)時間4年前 (2020/09/08 13:57), 4年前編輯推噓4(4推 0噓 36→)
留言40則, 6人參與, 4年前最新討論串1/1
各位大神好～ 肥宅我最近複習資料結構， 在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://www.ptt.cc/bbs/C_and_CPP/M.1599544650.A.FA8.html
推
09/08 14:24, 4年前 , 1F
新new的Node沒給上一層的Node阿
09/08 14:24, 1F
推
09/08 14:27, 4年前 , 2F
你的insertion 函式沒有回傳值
09/08 14:27, 2F
→
09/08 15:22, 4年前 , 3F
09/08 15:22, 3F
→
09/08 15:22, 4年前 , 4F
抱歉各位我的指標觀念不太好
09/08 15:22, 4F
→
09/08 15:29, 4年前 , 5F
newNode(30) 回傳的新Node位址，assign給root
09/08 15:29, 5F
→
09/08 15:32, 4年前 , 6F
root是上一個遞迴的root->right，這樣做會連不上嗎
09/08 15:32, 6F
→
09/08 15:34, 4年前 , 7F
我知道有方法是把Node指標當作函式的回傳類型去實作
09/08 15:34, 7F
→
09/08 15:35, 4年前 , 8F
我只是想釐清我指標的盲點QQ
09/08 15:35, 8F
→
09/08 15:35, 4年前 , 9F
謝謝1F和2F大大的留言
09/08 15:35, 9F
推
09/08 15:42, 4年前 , 10F
我剛剛測試你的寫法 直接傳Null進去new 然後輸出位址會是
09/08 15:42, 10F
→
09/08 15:42, 4年前 , 11F
0x0 函式改成有回傳值的就會有位址
09/08 15:42, 11F
→
09/08 15:43, 4年前 , 12F
我也沒想過這種寫法@@ 不過實際測試出來你這樣寫 最後roo
09/08 15:43, 12F
→
09/08 15:43, 4年前 , 13F
t的child pointer 會沒位址
09/08 15:43, 13F
→
09/08 16:13, 4年前 , 14F
你可以在 Insertion() 前後觀察一下指標值有無變化,
09/08 16:13, 14F
→
09/08 16:13, 4年前 , 15F
你只有改到參數, 而不是傳進來的指標物件本身
09/08 16:13, 15F
→
09/08 16:19, 4年前 , 16F
謝謝NTU大大幫我測試XD 我怕如果不釐清其中的運作機制
09/08 16:19, 16F
→
09/08 16:19, 4年前 , 17F
，以後還是會生出這種可怕的code (掩面)
09/08 16:19, 17F
→
09/08 16:28, 4年前 , 18F
謝謝Love大！所以pointer當參數只是複製一份和pointer
09/08 16:28, 18F
→
09/08 16:28, 4年前 , 19F
相同的值（一樣的記憶體位置?）再傳到函式裡面作用對嗎
09/08 16:28, 19F
→
09/08 16:31, 4年前 , 20F
那我傳進去NULL和函式裡面的NULL如果位置一樣，應該會
09/08 16:31, 20F
→
09/08 16:31, 4年前 , 21F
指向同一個生出來的物件會，這樣觀念對嗎？
09/08 16:31, 21F
→
09/08 16:58, 4年前 , 22F
1. 是因為傳進來當參數的NUL和原本的right的NULL實際上
09/08 16:58, 22F
→
09/08 16:58, 4年前 , 23F
指向不同的位置嗎？
09/08 16:58, 23F
→
09/08 16:58, 4年前 , 24F
2. 還是因為NULL根本不指向任何記憶體的實際位置，只有
09/08 16:58, 24F
→
09/08 16:58, 4年前 , 25F
在我new的時候才分配記憶體位置給該層遞迴指向的NULL。
09/08 16:58, 25F
→
09/08 16:58, 4年前 , 26F
所以我new出來的物件只停留在newNode的那層遞迴，原本
09/08 16:58, 26F
→
09/08 16:58, 4年前 , 27F
的child則沒有改到嗎？
09/08 16:58, 27F
→
09/08 16:59, 4年前 , 28F
謝謝NTU大和Love大不厭其煩為我解答和測試><
09/08 16:59, 28F
→
09/08 17:01, 4年前 , 29F
我測試new前後的結果，new出來的物件有記憶體位置和正
09/08 17:01, 29F
→
09/08 17:01, 4年前 , 30F
確的data值，但回到上層遞迴後原本的right又變回NULL了
09/08 17:01, 30F
→
09/08 17:50, 4年前 , 31F
謝謝各位，我看完置頂的新手十三誡第13點後好像明白了
09/08 17:50, 31F
→
09/08 19:04, 4年前 , 32F
Insertion的第一個參數型別到底是Node*還是Node*&
09/08 19:04, 32F
→
09/08 19:37, 4年前 , 33F
看到 *& 我就笑了 :D
09/08 19:37, 33F
→
09/08 20:22, 4年前 , 34F
哈哈哈*&是我剛剛參考置頂文章再測試XD
09/08 20:22, 34F
→
09/08 20:22, 4年前 , 35F
我還在研究置頂的十三誡XD
09/08 20:22, 35F
→
09/08 20:38, 4年前 , 36F
09/08 20:38, 36F
→
09/08 20:40, 4年前 , 37F
原本發問的程式碼，避免點進去看到我在亂改程式碼XD
09/08 20:40, 37F
※ 編輯: AmigoSin (36.224.102.202 臺灣), 09/08/2020 21:05:50
推
09/09 16:51, 4年前 , 38F
要往下遞迴Insertion(root->right, data);
09/09 16:51, 38F
→
09/09 16:51, 4年前 , 39F
之前先檢查root->right == NULL
09/09 16:51, 39F
→
09/09 16:51, 4年前 , 40F
是的話root->right = newnode(data);
09/09 16:51, 40F
‣ 更多 AmigoSin 的文章
文章代碼(AID): #1VLnrA-e (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 AmigoSin 的文章
文章代碼(AID): #1VLnrA-e (C_and_CPP)