Представление линейных списков деревьями

Такое представление позволяет за логарифмическое время иметь доступ к узлу дерева как по ключу, так и по порядковому номеру. Для решения этой задачи в каждый узел дерева добавим новое поле по имени Rank.Это поле содержит порядковый номер узла при обратном обходе в дереве, которое из него исходит. На

Рис. 46 Представление массива бинарным деревом

Ниже представлен текст функции, выполняющей поиск элемента массива по индексу. Алгоритм предполагает наличие головы у дерева. Собственно дерево является левым поддеревом головы.

struct NODE {

int Info;

NODE *Left;

NODE *Right;

int Rank;

};

//--------------------------------------------

NODE *FindByIndex(NODE *Head, int Index){

// найти узел по индексу (счет от 0)

int k;

NODE *Cur;

k=Index+1;

Cur=Head;

while(Cur!=NULL && k!=Cur->Rank){

if(k < Cur->Rank){

Cur=Cur->Left;

} else {

k-=Cur->Rank;

Cur=Cur->Right;

}

}

return Cur;

}