問題詳情

39.二元樹（binary tree）的每個節點有兩個分支，分支可以是空連結（null）或者是其他節點。現在給定一棵二元樹，假設共有100個節點，則此棵二元樹共有幾個空連結？
(A)99
(B)100
(C)101
(D)200

參考答案

答案：C
難度：困難0.34507
統計：A(38),B(17),C(49),D(7),E(0)

用户評論

【Yi Fang】評論

求解

【chaowinch】評論

若不考慮分支為1的節點，答案是對的，題目有問題

【古佳怡】評論

題目應該是問complete binary tree，也就是盡量填滿，最後一層則靠左的情況？這樣的話，因為2h - 1 = 100，可以回推出h = 6點多，也就是第六層全滿，第七層部分滿的情況。所以空連結的數量會有：第六層node數 * 2(左空和右空)  -  第七層node數  +   第七層node數 * 2(左空和右空)= 25*2 - (100 - 25 - 24 - ... - 1) + (100 - 25 - 24 - ... - 1)*2= 101