[爆卦]二元樹建立是什麼?優點缺點精華區懶人包

為什麼這篇二元樹建立鄉民發文收入到精華區:因為在二元樹建立這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者forris (喬巴)看板Examination標題[問題] 資料結構時間Sat May 17 ...

二元樹建立 在 革命開始的時候躺下來 Instagram 的精選貼文

2021-08-19 00:32:23

 ▸ 最後是寂寞 ◂  朋友們爭論過好幾次村上改編電影最棒的到底是《東尼瀧谷》還是《燃燒烈愛》,你覺得呢?  洋子,這個問題真不好回答,就像你問我喜歡草莓蛋糕還是檸檬塔一樣。  高中一年級和一個女孩看了《挪威的森林》,至此更喜歡低溫感、纖細而真空的電影。我從電影看回原著小說,真愛的一...


1. 將 1234567 七個數目依某順序插入一個空的二元搜尋樹 (Binary Search Tree) 後,
所得的二元搜尋數如下圖所示:
4
/ \
2 6
/ \ / \
1 3 5 7

總共有幾種可能的插入順序?
(a) 40 種 (b) 48 種 (c) 80 種 (d) 96 種

2. 某二元搜尋樹內存有 10 到 50 之間的數目。自此二元搜尋樹搜尋數目 30 時,
其搜尋過程中比對過的數目,不可能是下列哪一個順序?
(a) 15,43,18,39,20,36,27,30
(b) 38,10,19,37,21,33,31,30
(c) 24,48,44,25,40,33,26,34,30
(d) 42,39,12,13,23,35,28,32,30

為什麼是選 c ?

3. 在二元樹上,依照節點所在的層次,由最上層至最下層一層層走動 (traverse) 時,
需要用到哪一種資料結構?
(a) stack (b) queue (c) hash table (d) heap

為何要選 b 而不是 d ?


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.240.43
※ 編輯: forris 來自: 218.173.240.43 (05/17 00:56)
flamemmx2:第一題:第一個插入的一定是4(一種方法),然後再考慮第 05/17 09:33
flamemmx2:二層的2和6,有可能是2先或是6先插入(2*1種方法),再來 05/17 09:34
flamemmx2:考慮第三層的1、3、5、7(有4*3*2*1種方法),故全部的方 05/17 09:35
flamemmx2:法數為1*1*2*4*3*2*1=48種。不知道這樣解對不對XD 05/17 09:36
steter:第一題我也有疑問? 05/17 10:02
steter:我記得答案不是48 雖然我算48 XD 05/17 10:06
cutedoll7411:缺少了像2163 57這一類的 05/17 11:56
cutedoll7411:所以除了原本的48再加上將213為一堆,657為一堆 05/17 11:56
cutedoll7411:一開始先選擇要哪一堆,若選擇213,則為2*2!, 05/17 11:57
cutedoll7411:再將6插入213中的4個位置其中一個,為 C4取1 05/17 11:58
cutedoll7411:最後在排57,則為(C4取1)*2! 05/17 12:00
cutedoll7411:所以為48+2*2!*4*2! 05/17 12:00
steter:我也記得答案是80 05/18 14:59

> -------------------------------------------------------------------------- <

作者: canatmis (Guest~) 看板: Examination
標題: Re: [請益] 資料結構
時間: Sat May 17 11:31:45 2008

※ 引述《forris (喬巴)》之銘言:
: 1. 將 1234567 七個數目依某順序插入一個空的二元搜尋樹 (Binary Search Tree) 後,
: 所得的二元搜尋數如下圖所示:
: 4
: / \
: 2 6
: / \ / \
: 1 3 5 7
: 總共有幾種可能的插入順序?
: (a) 40 種 (b) 48 種 (c) 80 種 (d) 96 種


這題我也是跟原po那篇推文的幾個大大一樣的算法
如果是以上圖所示的二元搜尋樹來插入的話
第一層的4<-- root 只有一種插入順序
第二層的2和6誰都可以先插入,而不影響另一個,所以可有2!種插入順序
第三層的1、3、5、7,如因為2和6已完成插入
,所以第三層誰先插入也都可以所以有4!種插入順序
因此,1!*2!*4! = 48 種插入順序


: 2. 某二元搜尋樹內存有 10 到 50 之間的數目。自此二元搜尋樹搜尋數目 30 時,
: 其搜尋過程中比對過的數目,不可能是下列哪一個順序?
: (a) 15,43,18,39,20,36,27,30
: (b) 38,10,19,37,21,33,31,30
: (c) 24,48,44,25,40,33,26,34,30
: (d) 42,39,12,13,23,35,28,32,30
: 為什麼是選 c ?

二元搜尋樹的定義:如果不是空集合,左子樹的所有節點值必小於root值
右子樹的所有節點值必大於root值

因此用此觀念來run

選項 c: root = 24,再看後面一個48 > 24,故48(含)以後的值都必大於24
(因為,在搜尋過程不會再突然變到root的左子樹去,會一直比下去
故,後面的所有值都大於root值)
因此,後面的搜尋過程比較,也依此類推
24
\
(48、44、25、40、33、26、34、30)



24
\
48
/
(44、25、40、33、26、34、30)


24
\
48
/
44
/
25
\
40
/
33
/
26
\
「34」<---錯,因為34並不小於33



: 3. 在二元樹上,依照節點所在的層次,由最上層至最下層一層層走動 (traverse) 時,
: 需要用到哪一種資料結構?
: (a) stack (b) queue (c) hash table (d) heap
: 為何要選 b 而不是 d ?

我們舉個例子好了,以下圖所示,印出走訪過的節點值

4
/ \
2 6
/ \ / \
1 3 5 7

如果我的走訪順序是4、6、5的話,要印出走訪過的節點值
也會像走訪過的順序一樣印出
這樣一來,像不像Queue的定義呢?
Queue的定義:FIFO,先進先出


以上,有錯的請各位大大校正

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.127.66.114
cutedoll7411:應該是用深度追蹤(DFS)去想 05/17 12:03
cutedoll7411:先追蹤4,將26放入queue中,因為下一次要追蹤第2層 05/17 12:08
cutedoll7411:將queue中2 pop出來,再將13放入queue 05/17 12:08
cutedoll7411:將queue中6 pop出來,再將57放入queue 05/17 12:08
cutedoll7411:這樣就能保證1層1層追蹤,所以使用queue 05/17 12:09
galdar:別想太多..level order就是queue... 05/17 13:28
jojoh:C大 這應該是廣度追蹤 用Queue去做 05/18 02:21
jojoh:總結來說 ..level order就是queue... 05/18 02:21
canatmis:嗯,了解,謝謝各位大大的校正,還有第一題是80種 05/18 09:15
canatmis:為原來的48+(2*2!)*(2*2!*2!) 05/18 09:16

你可能也想看看

搜尋相關網站