[理工] 資料結構書本上的定義請益

[APE36 (PT鄉民)]

在二元樹的章節中

有提到如下的問題

若2i <= n 索引值i之左子節點被存放在索引值為2i之處。如果2i > n，則索引值i所
在節點並沒有左子節點存在。

若(2i+1) <= n 索引值i之右子節點被存放在索引值為2i+1之處。如果2i+1 >n，
則索引值i所在節點並沒有右子節點存在。

請問這段話的意思是說 左右子樹擺放位置嗎??還是??


另外一題請益 ex.如果是完全二元樹，1000各節點，試問共有多少個葉節點? 分支度為1
的節點有多少個?

這題的算法好像跟算葉節點數的公式有些出入!!!希望有神人幫分析一下，感謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.120.95
推 A4P8T6X9:那個代表編號 i 這個點，其左右子點的編號。
還是不太清楚，翻譯書筆法好難理解 @@"
※ 編輯: APE36           來自: 114.27.120.95        (03/17 15:50)
→ A4P8T6X9:葉子500個，因為最後一個父點是1000/2。
→ A4P8T6X9:http://ppt.cc/ULng
推 john35452:leaf有500個，因為n0=n2+1，所以n2有499個，又因為
→ john35452:n=n0+n1+n2，所以n1=1000-500-499=1
→ john35452:ps. n為node總個數，而ni為分支度為i的node個數
→ john35452:而第一個問題我覺得i應該是parent的編號，2i為其左子點
→ john35452:的index，2i+1則為右子點，所以當編號為2i或是2i+1大於n
→ john35452:時，因為n為總共的點數，所以代表此點不存在