作者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/cn.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