Каждый уровень двоичного дерева содержит в два раза больше узлов, чем предыдущий уровень. Если у вас есть n
узлов, то количество требуемых уровней (высота дерева) будет log2(n) + 1
, округленное до целого числа. Таким образом, если у вас есть 5 узлов, ваше двоичное дерево будет иметь высоту 3.
Число узлов в полном двоичном дереве высоты h
равно (2^h) - 1
. Итак, вы знаете, что максимальный размер массива, который вам нужен для 5 элементов, равен 7. Предполагается, что все уровни заполнены, кроме, возможно, последнего.
Последняя строка вашего дерева будет содержать (2^h)-1 - n
узлов. Последний уровень полного дерева содержит 2^(h-1)
узлов. Предполагая, что вы хотите сбалансировать его, чтобы половина узлов находилась слева, а половина - справа, а правая сторона была заполнена слева, то есть вы хотите:
1
2 3
4 5 6 7
8 9 10 11
Номер массива пространство, необходимое для последнего уровня вашего дерева, равно 1, или это половина числа, требуемого для полного дерева, плюс половина узлов, требуемых для вашего дерева.
Итак:
n = 5
height = roundUp(log2(n) + 1)
fullTreeNodes = (2^height) - 1
fullTreeLeafNodes = 2^(height-1)
nodesOnLeafLevel = fullTreeNodes - n
Теперь самое интересное. Если на уровне листа требуется более 1 узла, и вы хотите сбалансировать стороны, вам понадобится половина fullTreeLeafNodes
плюс половина nodesOnLeafLevel
. Например, в дереве выше уровень листьев имеет потенциал для 8 узлов. Но у вас есть только 4 листовых узла. Вы хотите, чтобы два из них с левой стороны и два справа. Таким образом, вам нужно выделить место для 4 узлов с левой стороны (2 для элементов левой стороны и 2 пустых пространства), плюс еще два для двух элементов правой стороны.
if (nodesOnLeafLevel == 1)
arraySize = n
else
arraySize = (fullTreeNodes - fullTreeLeafNodes/2) + (nodesOnLeafLevel / 2)
Компилятор не знает, что spe_context_ptr_t является типом. Проверьте, что соответствующее определение типа находится в объеме, когда этот код компилируется. Вы, возможно, забыли включать соответствующий заголовочный файл.
У меня было такое же сообщение об ошибке, но решение другое.
Компилятор анализирует файл сверху вниз.
Убедитесь, что структура определена ДО того, как использовать ее в другой:
typedef struct
{
char name[50];
wheel_t wheels[4]; //wrong, wheel_t is not defined yet
} car_t;
typedef struct
{
int weight;
} wheel_t;
Вы должны назвать свою структуру так:
typedef struct car_t {
char
wheel_t
} car_t;
Для проектов iPhone какао:
У меня была эта проблема, и благодаря комментарию Эрика Фарраро я смог ее решить. Я импортировал класс WSHelper.h во многие другие мои классы. Но я также импортировал некоторые из тех же классов в свой WSHelper.h (как сказал Эрик). Итак, чтобы исправить это, я переместил импорт из моего файла WSHelper.h в свой файл WSHelper.m, так как в любом случае они действительно не нужны в файле .h.
Я получил это с помощью цикла импорта:
---FILE B.h
#import "A.h"
@interface B{
A *a;
}
@end
---FILE A.h
#import "B.h"
@interface A{
}
@end