※ 引述《[email protected] (愛睡了)》之銘言：
: 要怎麼寫比較好呢....
: 是不是用遞回寫比較好....
: 請告訴我好嗎...謝啦...
如你的 tree 為 binary tree 且是以 array 來 present 的話，
如 N 為 node 個數，則可由 [log2(N)] 求得。
如 tree 以 linked-list 來 present 則一時也只想到用 recursive。
龍龍
--
你是一位聰明人嗎?如果是，你該記住，你的聰明是跟那些人學來的，
然後在適當的地點，適當的時間，輕輕的對那人說：這是你教我的。
聲音要輕，而且只告訴他一個人。
摘錄自"牧羊少年奇幻之旅"
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: DickG.m5.ntu.ed
> -------------------------------------------------------------------------- <
發信人: [email protected] (東京紅色情人夢-中島廣香), 看板: C_and_CPP
標 題: Re: 怎麼找樹的height呀??
發信站: 程式設計樂園(CSZone) (Tue Apr 13 10:46:04 1999)
轉信站: Ptt!CSZoneNews!CSZone
※ 引述《[email protected] (龍龍)》之銘言：
: ※ 引述《[email protected] (愛睡了)》之銘言：
: : 要怎麼寫比較好呢....
: : 是不是用遞回寫比較好....
: : 請告訴我好嗎...謝啦...
: 如你的 tree 為 binary tree 且是以 array 來 present 的話，
: 如 N 為 node 個數，則可由 [log2(N)] 求得。
呃, 這樣說好像也不太對..:-) 要是這顆樹不是 complete 或是
full 呢?
> -------------------------------------------------------------------------- <
發信人: [email protected] (貓兒), 看板: C_and_CPP
標 題: Re: 怎麼找樹的height呀??
發信站: 程式設計樂園(CSZone) (Tue Apr 13 11:06:41 1999)
轉信站: Ptt!CSZoneNews!CSZone
※ 引述《[email protected] (愛睡了)》之銘言：
: 要怎麼寫比較好呢....
: 是不是用遞回寫比較好....
: 請告訴我好嗎...謝啦...
如果你的樹只有 data, pointer 的欄位, 那麼就利用 bfs, dfs
來搜尋整棵樹, 並且記錄樹的高度.
或者, 在 tree node 中加入 height 欄位, 記錄每個 node 的
高度, 在插入或刪除 node 時就需要更新此欄位, 因此會增加額
外的工作.
> -------------------------------------------------------------------------- <
作者: DickG (龍龍) 看板: C_and_CPP
標題: Re: 怎麼找樹的height呀??
時間: Tue Apr 13 13:56:09 1999
※ 引述《[email protected] (東京紅色情人夢-中島廣香)》之銘言：
: ※ 引述《[email protected] (龍龍)》之銘言：
: : 如你的 tree 為 binary tree 且是以 array 來 present 的話，
: : 如 N 為 node 個數，則可由 [log2(N)] 求得。
: 呃, 這樣說好像也不太對..:-) 要是這顆樹不是 complete 或是
: full 呢?
嗯...ㄑㄧ\ 說得很有道理...
我的前題是該加個 complete binary tree ^^
龍龍
> -------------------------------------------------------------------------- <
發信人: [email protected] (貓兒), 看板: C_and_CPP
標 題: Re: 怎麼找樹的height呀??
發信站: 程式設計樂園(CSZone) (Wed Apr 14 00:03:47 1999)
轉信站: Ptt!CSZoneNews!CSZone
※ 引述《[email protected] (愛睡了)》之銘言：
: ※ 引述《[email protected] (貓兒)》之銘言：
: : 如果你的樹只有 data, pointer 的欄位, 那麼就利用 bfs, dfs
: : 來搜尋整棵樹, 並且記錄樹的高度.
: : 或者, 在 tree node 中加入 height 欄位, 記錄每個 node 的
: : 高度, 在插入或刪除 node 時就需要更新此欄位, 因此會增加額
: : 外的工作.
: bfs和dfs是搜尋用的沒錯....
: 可是怎麼用在記錄tree的高度呀....
: 那不就要多加一個欄位記錄樹的高度呀....
: 可不可以寫清楚一點....謝啦....:)
1. 進行 bfs, dfs 時, 以一個變數記錄目前的高度, 再以另外一個
變數來記錄樹的最大高度值, 當目前高度超過最大值時, 就更新
最大高度值.
2. 加入一個欄位, 在進行 bfs, dfs 時更新每個 node 的高度值,
並記錄出現過的最大高度值.
--
貓眼看天下 ...... A.T.
--
※ Origin: 程式設計樂園 ◆ From: Clark.cs.nthu.edu.tw