Вопрос 4: Упорядоченный массив как способ хранения дерева двоичного поиска

Если последовательность хранится в массиве, то построить ДДП можно методом деления пополам: поместить в корень дерева средний по порядку элемент, затем рекурсивно создать левое поддерево из первой половины последовательности, а правое — из второй.

Node* build(int a, int b, int* data) // Сборка ДДП из массива узлов data
{
    if (b <= a)
        return 0;

    int c = (a + b) / 2;
    Node* s = new Node(data[c]);

    s->left = build(a, c, data);
    s->right = build(c + 1, b, data);

    return s;
}