一題complete binary tree請益

A complete binary tree is defined inductively as follows. A complete binary tree of height 0 consists of 1 node which is the root.A complete binary tree of height h+1 consists of two complete binary tree of height h whose roots are connected to a new root. Let T be a complete binary tree of height h. The height of a node in T is h minus the node's distance from the root(e.g., the root has height h, whereas a leaf has height 0). What is the sum of the heights of all the node in T?

不是很懂這題的意思,希望有人可以幫忙解說一下

萬分感謝

3 個解答

評分
  • sponge
    Lv 6
    6 年前
    最佳解答

    假設 T 中所有點的高度總和為 S

    因為題目的 complete binary tree 以高度來定義,所以 S 與 h 有關,記為 S(h)

    根據題目定義,高度 h+1 的 complete binary tree 可記為 T'=T∪T∪x

    其中 x 表示二個 T 的樹根連接到的新樹根

    S 中的高度是從樹葉算起,因此二個 T 各點高度總和在 T' 裡仍為 S(h)

    x 是 T' 的樹根,所以高度是 h+1

    T' 各點高度總和是 S(h+1)=S(h)+S(h)+h+1

    將此關係改為 h 與 h-1 的關係以利計算如下

    S(h)

    =2S(h-1)+h

    =4S(h-2)+2(h-1)+h

    =8S(h-3)+4(h-2)+2(h-1)+h

    =...

    =2^h*S(h-h)+2^(h-1)*1+2^(h-2)*2+...+2(h-1)+h

    =2^h*S(0)+2^(h-1)*1+2^(h-2)*2+...+2(h-1)+h

    S(0) 來自高度 0 的 complete binary tree, 其值為 0

    故 S(h)=2^(h-1)*1+2^(h-2)*2+...+2(h-1)+h=Σ 2^i*(h-i), i=0~h-1

    將 2^i*(h-i)=2^i*h - 2^i*i 兩段來分析Σ

    Σ 2^i*h

    =hΣ 2^i

    =h*(2^h - 1)

    利用 generating function 推 Σ 2^i*i

    Σ x^i = (x^h - 1)/(x-1)

    兩邊微分,Σ i*x^(i-1) = h*x^(h-1)/(x-1) - (x^h - 1)/(x-1)^2

    同乘以 x, Σ i*x^i = h*x^h/(x-1) - (x^(h+1) - x)/(x-1)^2

    x=2 代入得 Σ i*2^i = h*2^h - 2^(h+1) + 2

    所以所求 S(h)=h*(2^h - 1) - h*2^h + 2^(h+1) - 2=2^(h+1) - h - 2

    希望以上回答對您有幫助!

    • 登入以對解答發表意見
  • 6 年前

    二叉樹是啥東西..

    我只聽過二元樹

    • 登入以對解答發表意見
  • 6 年前

    恩.. Google翻譯

    一個完整的二叉樹歸納定義如下。高度為0的完全二叉樹由1個節點是高度為h+1 root.A完全二叉樹由高度為h兩個完整的二叉樹,其根源都連接到一個新的根。設T是高度為h的完全二叉樹。在T節點的高度為h減去從根節點的距離(如,根具有高度h,而葉子的高度為0)。什麼是T中所有節點的高度之和?

    • 登入以對解答發表意見
還有問題?馬上發問,尋求解答。