Рассмотрим, как операции создания бинарного сбалансированного дерева и его обхода реализуются на языке программирования С++. Для упрощения примера будем использовать дерево, поле записи которого содержит только ключи, являющиеся вещественными числами, тогда элемент дерева описывается следующим образом:
struct element
{ double k;
element* left;
element* right;
};
Далее необходимо ввести указатель вершины дерева и рабочие указатели для реализации функции создания дерева.
element *tree=NULL,*P,*Q;
Пока дерево не создано, указатель корня нулевой (*tree=NULL).
Ниже представлена функция создания бинарного дерева
void maketree(double a) //создание дерева
{ if(!tree)
{ tree=new element;
tree->k=a;
tree->right=tree->left=NULL;
P=tree;
Q=NULL;
return;
};
P=Q=tree;
while (P!=NULL)
{ Q=P;
if(a<P->k) P=P->left; else P=P->right;
};
if(a<Q->k) { Q->left=new element;
Q->left->k=a;
Q->left->left=Q->left->right=NULL;
}
else { Q->right=new element;
Q->right->k=a;
Q->right->left=Q->right->right=NULL;
};
}
В теоретической части лабораторной работы были рассмотрены 3 вида обхода бинарного дерева. Алгоритм наиболее часто используемого вида обхода слева-направо на С++ для созданного выше дерева будет иметь следующий вид:
void printree(element* tree) //просмотр и печать дерева
{ if(tree)
{ printree(tree->left);
cout<<tree->k<<" ";
printree(tree->right);
};
}