Research Space for Linear Algebra & Discrete Mathematics
因為我在資結看到的full BT 的定義: 高度為K的二元樹,其具有最多的NODE樹(i,e, 2^k-1者稱之)Complete BT : 高度為K的BT具有N個NODE且滿足: 1.2^K-1< n < 2^k-1 2.節點編號與full BT之前n個NODE編號一一對應
的確, 一般在資結裡定義的 full 指的是具有 2^(k+1)-1 個點的那個看起來很完整的樹, 其中樹的高度為 k (note: 資結與離散有時對於height的定義也不同, 我這裡高度用的是離散的定義, i.e., root 的高度為 0), 而 complete 指的則是樹高為 k, 但 node 數介於 2^k 到 2^(k+1)-1 之間的那一種, 但離散裡的定義就像書上 p7-15 所寫的那樣, 與資結裡所定義的並不相同還有一點要注意的是, 有些離散的書所定義的 full 和 complete, 和書上的版本是剛好相反的, 就像老師在第四版裡所定義的 full 和 complete 就和第五版裡所定義的剛好相反, 我想這兩種定義應該都很多人用, 所以在考試時記得要再自行判斷一下出題老師他用的是哪一種版本
那考數學時根據離散定義去寫 考資結時根據資結定義去寫 這樣應該妥當吧@@
嗯嗯通常這樣做是都不會有問題的, 而且通常都可以判斷, 如果真的有出現無法判斷的情況, 你再說明一下你用的是哪一種定義就可以了
OK 3Q助教了
張貼留言
5 則留言:
因為我在資結看到的
full BT 的定義:
高度為K的二元樹,其具有最多的NODE樹(i,e, 2^k-1者稱之)
Complete BT :
高度為K的BT具有N個NODE且滿足:
1.2^K-1< n < 2^k-1
2.節點編號與full BT之前n個NODE編號一一對應
的確, 一般在資結裡定義的 full 指的是具有 2^(k+1)-1 個點的那個看起來很完整的樹, 其中樹的高度為 k (note: 資結與離散有時對於height的定義也不同, 我這裡高度用的是離散的定義, i.e., root 的高度為 0), 而 complete 指的則是樹高為 k, 但 node 數介於 2^k 到 2^(k+1)-1 之間的那一種, 但離散裡的定義就像書上 p7-15 所寫的那樣, 與資結裡所定義的並不相同
還有一點要注意的是, 有些離散的書所定義的 full 和 complete, 和書上的版本是剛好相反的, 就像老師在第四版裡所定義的 full 和 complete 就和第五版裡所定義的剛好相反, 我想這兩種定義應該都很多人用, 所以在考試時記得要再自行判斷一下出題老師他用的是哪一種版本
那考數學時根據離散定義去寫
考資結時根據資結定義去寫
這樣應該妥當吧@@
嗯嗯通常這樣做是都不會有問題的, 而且通常都可以判斷, 如果真的有出現無法判斷的情況, 你再說明一下你用的是哪一種定義就可以了
OK 3Q助教了
張貼留言