[理工] 109 交大 資演 (14)

[stmilton (阿米)]

想請問第14題

答案是A

https://i.imgur.com/08MyzZp.jpg

實在看不懂他的code在幹嘛？

x和y應該沒有限定初始位置吧?

那x和y是不是可以是完全沒關係的兩個leaf?




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.229.86.211 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1641994818.A.B88.html
推 jacksoncsie: 這題的 successor 是指 inorder 的上一個
→ jacksoncsie: 打錯 successor 是下一個 :(
→ jacksoncsie: predcessor 才是 inorder 的上一個 node
j大successor意思我知道，但是為什麼x,y一定會有這關係？
→ JBdonSH: x,y的值一定會是相鄰的，根據題意x不會是整棵樹的最大值
JB大請問一下，題意上有說x,y會相鄰嗎？我看不太出來是在哪邊敘述的？
※ 編輯: stmilton (36.229.86.211 臺灣), 01/12/2022 23:58:35
推 jimmy1112111: 這段code可以找出BST在inorder順序下，x的下一個數
→ jimmy1112111: 值，可能是它的child或parent或跟他沒有edge相連的
→ jimmy1112111: node
我看懂了，謝謝各位大大，我一直把第二行和第三行看成return y==p[x]
※ 編輯: stmilton (101.12.53.15 臺灣), 01/13/2022 09:52:50
推 x3767x: 106海大有一題很像的，你可以參考一下