二元樹問題

c 新人發問二元樹

abalun52 2020-11-26 21:30:33 ‧ 1964 瀏覽

分享至

問題:http://140.135.65.53:10080/problem/0/50111
完整程式碼:https://ideone.com/SF94B1

想問的是我寫a[i]=root->value能夠讀取到上面set_leaf的值嗎?
還是這種題目不能用迴圈讀取set_leaf的值?

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

1 個回答

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 );
    }
  }
}