[理工] 资结延伸二元树 E=I+2N s1020824 PTT批踢踢实业坊

楼主: s1020824 (HowardW) 2017-09-18 17:33:30

大家晚安
http://i.imgur.com/V6G24pR.jpg
不太懂第三步红色字那里
内,外部路径总长跟节点数的关系
烦请大大了
谢谢~~

作者: Xunion (Xun) 2017-09-18 18:29:00

左、右子树高度有少一，所以加回去有错还请指正QQ 凭印象回答的

作者: lovepipi (lovepipi) 2017-09-18 20:45:00

楼上说的是对的喔

楼主: s1020824 (HowardW) 2017-09-18 21:03:00

是加回root连接左右子树那里吗那为什么还要加回外部节点呢还是不太了解qq

作者: can18 (18号) 2017-09-18 21:17:00

它是先将root拔掉这样就可以用归纳假设将root加回去的时候每个点的高度都增加1所以实际内部路径长要再加上左右子数的点数

楼主: s1020824 (HowardW) 2017-09-18 21:21:00

喔喔懂了~~ 谢谢大大

继续阅读