6_ Структуры и ...

}

// Вычисление длины

int LengthList(Node* pHead){

int len=0;

for(Node* p=pHead; p>0; p=p->m_pNext, len++)

;

return len;

}

6.5 Двоичные деревья

Двоичным или бинарным деревом принято называть конечное множество , один элемент которого называется корнем, а оставшиеся элементы разбиваются на два непересекающихся подмножества и , каждое из которых само является деревом. При этом дерево называется левым поддеревом, - правым поддеревом дерева . Корень дерева T называется родителем или предком для корней поддеревьев и . Таким образом, каждый элемент (узел) дерева является корнем некоторого поддерева (возможно пустого).

Каждому узлу дерева поставлено в соответствие натуральное число, называемое его уровнем. По определению, уровень корня всего дерева равняется единице. Уровень каждого оставшегося узла на единицу больше уровня его предка. Поэтому количество узлов, находяшихся на уровне с номером n, ограничено числом 2^n-1, а общее число узлов дерева, находящихся на уровнях с первого по n-ый, ограничено числом 2ⁿ-1.