Lv 4
asked in 電腦與網際網路程式設計 · 8 years ago

資料結構:Complete binary tree的問題

有人可以幫我解釋一下這題問問題的意思嘛? 或是可以證明的...

我看不太懂題目的意思...或者可以說明一下...感謝

題目:

Given a binary tree t, its extension is defined as the binary tree e(t) formed from t by adding a new leaf node at each NULL left and right pointer in t.

The new leaves are called external nodes, and the original nodes

(which are all non-leaves) are called internal nodes,

e(t) is called an extended binary tree.

問題:

Show that the complete binary tree of order n is the nth extension of the binary

tree consisting of a single node.

1 Answer

Rating
  • Bor
    Lv 5
    8 years ago
    Favorite Answer

    不知道個人理解有沒有錯,在此就試著解看看,若解錯了尚請包涵

    題**意思是說,給定你一個binary tree(在題目裡稱為t),而現在我要做它的extension(在題幹裡,這個新的tree稱為e(t), 這個名稱是隨意給定,也可以是其它名稱),那麼我要怎麼做呢?

    這個做法就是在t上的每一個leaf node都加上新的結點(adding a new leaf node at each NULL left and right pointer in t)

    而新加入的點都稱為external nodes,原本的點稱為internal nodes,此時得到的新tree為e(t)

    而最後問題所求:

    一開始只有一個node,逐漸依照上述方法產生新樹

    開始幾步大概是這樣的:

    ------(initial)

      .

     . .

    ------(extension 1)

      .

     . .

    . . .

    ------(extension 2)

       .

      . .

     . . .

    . . . .

    -------(extension 3)

    如圖中所示每一層的新的extenstion都是新的complete binary tree

    因為一開始只有一個點(也是一個complete binary tree)

    而之後會補滿所有的下一層子節點,使其不為NULL,

    故每一層得到的都是complete binary tree

    嗯...不知道這樣子說明可不可以?

Still have questions? Get your answers by asking now.