※ 引述《kakahikari (光仔)》之銘言：
: 代po
: 98年交大離散
: 2.4題
: http://www2.lib.nctu.edu.tw/n_exam/exam98/cslz/cslz1002.pdf
: 他的問題是這樣的:
: fully binary tree 的點數不是(2^H( T )+1)-1 怎會有range
: 先感謝各位回答
我講清楚一點好了
剛剛本來想說用推文稍微解釋就可以
可是好像很難講XD
而且其實我發現我有點搞錯了=.=
簡而言之 你現在說的定義 也不是 complete binary tree的定義
你說的是"完整二元樹"的定義對吧 也就是全部填滿
可能是多一個y的關係吧@@
也就是說:
"fully" binary tree是全滿的二元樹
complete binary tree是除了最下面那層的節點是由左邊開始填滿以外，
上面各層都要是滿的。
而"full" binary tree是:
A binary tree in which each node has exactly zero or two children.
也就是說除了leaf以外的節點都要是滿的
但是問題就出在
這幾個名詞在各本書上面用法不太一樣
所以有可能會有把上面complete binary tree定義寫成full binary tree的情形
等等
因此我們必須從題目其他地方來判斷題目到底是在問哪個定義
這題因為有"range"
所以就知道應該是在問上面說的full binary tree而不是fully binary tree
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.83
※ 編輯: jameschou 來自: 140.113.139.83 (01/12 16:58)