6_ Структуры и .
...doc}
// Вычисление длины
int LengthList(Node* pHead){
int len=0;
for(Node* p=pHead; p>0; p=p->m_pNext, len++)
;
return len;
}
6.5 Двоичные деревья
Двоичным или бинарным деревом принято называть конечное множество , один элемент которого называется корнем, а оставшиеся элементы разбиваются на два непересекающихся подмножества и , каждое из которых само является деревом. При этом дерево называется левым поддеревом, - правым поддеревом дерева . Корень дерева T называется родителем или предком для корней поддеревьев и . Таким образом, каждый элемент (узел) дерева является корнем некоторого поддерева (возможно пустого).
Каждому узлу дерева поставлено в соответствие натуральное число, называемое его уровнем. По определению, уровень корня всего дерева равняется единице. Уровень каждого оставшегося узла на единицу больше уровня его предка. Поэтому количество узлов, находяшихся на уровне с номером n, ограничено числом 2n-1, а общее число узлов дерева, находящихся на уровнях с первого по n-ый, ограничено числом 2n-1.