有多少片葉子有四叉樹？

Question

讓N爲quadtree內部節點的數量。爲什麼葉子的數量等於1 + 3 * N？我不明白我們需要爭辯。

Answer 1

考慮通過細分葉節點來擴展四叉樹。該葉節點成爲內部節點（將葉數減1），並添加四個葉節點。如果以前的內部節點數爲N，則新的內部節點數爲N + 1，樹葉數爲1 + 3 * N-1 + 4 = 1 + 3 *（N + 1）。一般性聲明如下歸納。