• InOrderTraversal

100000  000001  32   1 *
100001  000011  33   3  
100010  000101  34   5  
100011  000111  35   7  
100100  001001  36   9 *
100101  001011  37  11  
100110  001101  38  13  
100111  001111  39  15  
101000  010001  40  17  
101001  010011  41  19  
101010  010101  42  21 *
101011  010111  43  23  
101100  011001  44  25  
101101  011011  45  27  
101110  011101  46  29 *
101111  011111  47  31  
110000  100001  48  33  
110001  100011  49  35 *
110010  100101  50  37  
110011  100111  51  39  
110100  101001  52  41  
110101  101011  53  43 *
110110  101101  54  45  
110111  101111  55  47  
111000  110001  56  49  
111001  110011  57  51  
111010  110101  58  53  
111011  110111  59  55 *
111100  111001  60  57  
111101  111011  61  59  
111110  111101  62  61  
111111  111111  63  63 *











100000  000001  32   1 *
010000  000010  16   2 *
100001  000011  33   3  
001000  000100   8   4 *
100010  000101  34   5  
010001  000110  17   6  
100011  000111  35   7  
000100  001000   4   8 *
100100  001001  36   9 *
010010  001010  18  10  
100101  001011  37  11  
001001  001100   9  12  
100110  001101  38  13  
010011  001110  19  14  
100111  001111  39  15  
000010  010000   2  16 *
101000  010001  40  17  
010100  010010  20  18  
101001  010011  41  19  
001010  010100  10  20 *
101010  010101  42  21 *
010101  010110  21  22  
101011  010111  43  23  
000101  011000   5  24  
101100  011001  44  25  
010110  011010  22  26 *
101101  011011  45  27  
001011  011100  11  28  
101110  011101  46  29 *
010111  011110  23  30  
101111  011111  47  31  
000001  100000   1  32 *
110000  100001  48  33  
011000  100010  24  34  
110001  100011  49  35 *
001100  100100  12  36  
110010  100101  50  37  
011001  100110  25  38 *
110011  100111  51  39  
000110  101000   6  40  
110100  101001  52  41  
011010  101010  26  42  
110101  101011  53  43 *
001101  101100  13  44 *
110110  101101  54  45  
011011  101110  27  46  
110111  101111  55  47  
000011  110000   3  48 *
111000  110001  56  49  
011100  110010  28  50  
111001  110011  57  51  
001110  110100  14  52  
111010  110101  58  53  
011101  110110  29  54  
111011  110111  59  55 *
000111  111000   7  56 *
111100  111001  60  57  
011110  111010  30  58  
111101  111011  61  59  
001111  111100  15  60 *
111110  111101  62  61  
011111  111110  31  62 *
111111  111111  63  63 *


j = rounddown_pow_of_two(t->size - 1);

/* Inorder traversal */
while (1) {
        // do stuff
        
        if (j == rounddown_pow_of_two(t->size) - 1)
                break;

        if (j * 2 + 1 < t->size) {
                j = j * 2 + 1;

                while (j * 2 < t->size)
                        j *= 2;
        } else
                j >>= ffz(j) + 1;
}

0001
0010
1001
0100
0101
1010
1101
1000
0011
0110
1011
1100
0111
1110
1111


static inline unsigned bset_tree_mid(unsigned start, unsigned size)
{
        unsigned f = rounddown_pow_of_two(size) >> 1;

        return (size & f)
                ? f << 1
                : size - f;
}