作者cormen5566 (风行者)
看板Grad-ProbAsk
标题Re: [问题] Binary Treee
时间Wed Apr 22 20:49:01 2009
※ 引述《peterpan126 (云淡风轻)》之铭言：
: 例题.Why do we use a binary tree to represent a general tree?
: Please state your opinions.
: 可否给个完整的说明呢!谢谢..
因为可以减少浪费的空间!
若以degree d来论
每个node宣告如下图:
______________________________
| data | link 1 | ... | link d |
______________________________
则具n个node的tree所真正有用到的link数为 n - 1
所有的link数却有n*d个
所以,link的有效使用率为
(n * d - (n - 1)) / n * d
其中 d=2时为最佳使用率,i.e., n+1/2n
因此,多数人都使用Binary Tree来表示!!!
有错请鞭罗^^
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.229.77.39
1F：→ peterpan126:谢谢 04/23 11:29