iT邦幫忙

0

二元樹問題

問題:http://140.135.65.53:10080/problem/0/50111
完整程式碼:https://ideone.com/SF94B1
https://ithelp.ithome.com.tw/upload/images/20201126/20132864pB6pF8xi6E.png
想問的是我寫a[i]=root->value能夠讀取到上面set_leaf的值嗎?
還是這種題目不能用迴圈讀取set_leaf的值?

1 個回答

6
marlin12
iT邦研究生 5 級 ‧ 2020-11-27 01:07:13
最佳解答
             root               M=8
       +-------+-------+
       L               R        M=4
   +---+---+       +---+---+
   L       R       L       R    M=2
 +-+-+   +-+-+   +-+-+   +-+-+
 L   R   L   R   L   R   L   R  M=1
i=0 i=1 i=2 i=3 i=4 i=5 i=6 i=7

對於母節點來說,如果i < M/2,子節點是在左面。否則,子節點是在右面。
對下一層右面的子節點來說,i的數值是在母節點時的i - M/2。

int read_leaf(Node* root, int i, int M)
{
  if (M == 1) {
    return root->value;
  } else {
    int Mdiv2 = M / 2;
    if (i < Mdiv2) {
      read_leaf( root->left, i, Mdiv2 );
    } else {
      read_leaf( root->right, i - Mdiv2, Mdiv2 );
    }
  }
}
看更多先前的回應...收起先前的回應...
abalun52 iT邦新手 5 級 ‧ 2020-11-27 02:10:35 檢舉

能夠解釋一下為什麼對於右節點i的數值需要-M/2嗎

看到您用 code block 出二元樹
我一定得來按10個
/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif

marlin12 iT邦研究生 5 級 ‧ 2020-11-27 08:44:55 檢舉

二元樹
假設葉節點的i=5,當root跳到下一層的右節點時,對於那個節點而言,原本i=5的葉節點,就會變成i=1,剛好就是上一層的(i - M/2) = (5 - 8/2)。

marlin12 iT邦研究生 5 級 ‧ 2020-11-27 08:51:01 檢舉

謝謝海綿大大的誇獎

我要發表回答

立即登入回答