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.

Rating
• Bor
Lv 5
8 years ago

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

題**意思是說,給定你一個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

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