---

---

※ 引述《tucson.bbs@bbs.ee.nsysu.edu.tw (愛睡了)》之銘言：
:        要怎麼寫比較好呢....
:        是不是用遞回寫比較好....
:        請告訴我好嗎...謝啦...

如你的 tree 為 binary tree 且是以 array 來 present 的話，

如 N 為 node 個數，則可由 [log2(N)] 求得。

如 tree 以 linked-list 來 present 則一時也只想到用 recursive。

龍龍

--

你是一位聰明人嗎?如果是，你該記住，你的聰明是跟那些人學來的，
然後在適當的地點，適當的時間，輕輕的對那人說：這是你教我的。
聲音要輕，而且只告訴他一個人。
                                摘錄自"牧羊少年奇幻之旅"

--
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: DickG.m5.ntu.ed

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

發信人: qing.bbs@cszone.cc.ntu.edu.tw (東京紅色情人夢-中島廣香), 看板: C_and_CPP
標  題: Re: 怎麼找樹的height呀??
發信站: 程式設計樂園(CSZone) (Tue Apr 13 10:46:04 1999)
轉信站: Ptt!CSZoneNews!CSZone

※ 引述《DickG.bbs@ptt.csie.ntu.edu.tw (龍龍)》之銘言：
: ※ 引述《tucson.bbs@bbs.ee.nsysu.edu.tw (愛睡了)》之銘言：
: :        要怎麼寫比較好呢....
: :        是不是用遞回寫比較好....
: :        請告訴我好嗎...謝啦...
: 如你的 tree 為 binary tree 且是以 array 來 present 的話，
: 如 N 為 node 個數，則可由 [log2(N)] 求得。

        呃, 這樣說好像也不太對..:-) 要是這顆樹不是 complete 或是
        full 呢?



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

發信人: AT.bbs@cszone.cc.ntu.edu.tw (貓兒), 看板: C_and_CPP
標  題: Re: 怎麼找樹的height呀??
發信站: 程式設計樂園(CSZone) (Tue Apr 13 11:06:41 1999)
轉信站: Ptt!CSZoneNews!CSZone

※ 引述《tucson.bbs@bbs.ee.nsysu.edu.tw (愛睡了)》之銘言：
:        要怎麼寫比較好呢....
:        是不是用遞回寫比較好....
:        請告訴我好嗎...謝啦...

  如果你的樹只有 data, pointer 的欄位, 那麼就利用 bfs, dfs
  來搜尋整棵樹, 並且記錄樹的高度.

  或者, 在 tree node 中加入 height 欄位, 記錄每個 node 的
  高度, 在插入或刪除 node 時就需要更新此欄位, 因此會增加額
  外的工作.


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

---

※ 引述《qing.bbs@cszone.cc.ntu.edu.tw (東京紅色情人夢-中島廣香)》之銘言：
: ※ 引述《DickG.bbs@ptt.csie.ntu.edu.tw (龍龍)》之銘言：
: : 如你的 tree 為 binary tree 且是以 array 來 present 的話，
: : 如 N 為 node 個數，則可由 [log2(N)] 求得。
:         呃, 這樣說好像也不太對..:-) 要是這顆樹不是 complete 或是
:         full 呢?
嗯...ㄑㄧ\ 說得很有道理...
我的前題是該加個 complete binary tree ^^

龍龍


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

發信人: AT.bbs@cszone.cc.ntu.edu.tw (貓兒), 看板: C_and_CPP
標  題: Re: 怎麼找樹的height呀??
發信站: 程式設計樂園(CSZone) (Wed Apr 14 00:03:47 1999)
轉信站: Ptt!CSZoneNews!CSZone

※ 引述《tucson.bbs@bbs.ee.nsysu.edu.tw (愛睡了)》之銘言：
: ※ 引述《AT.bbs@cszone.cc.ntu.edu.tw (貓兒)》之銘言：
: :   如果你的樹只有 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

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:41:51