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