Н.С. Гриценко, Ю.С. Белов
2
1) левое и правое поддерево узла
k
должны являться двоичным
деревом поиска;
2) значение ключа «левого ребенка» узла
k
должно быть меньше
значения ключа самого узла
k
;
3) значение ключа «правого ребенка» узла
k
должно быть больше
значения ключа самого узла
k
.
Эти требования выполнимы при условии уникальности ключа, т. е.
когда значение ключа любого из узлов дерева не будет повторяться.
Схема хранения двоичного дерева поиска представлена на рис. 1,
а листинг ее реализации приведен ниже [4]:
struct Tree
{
int data;
Tree *leftChild;
Tree *rightChild;
}*top;
Tree *AddElement(Tree *top, int n)
{
if (top == NULL)
{
top = new Tree;
top->data = n;
top->leftChild = NULL;
top->rightChild = NULL;
}
else
{
if (n > top->data)
top->rightChild = AddElement(top-
>rightChild, n);
else
top->leftChild = AddElement(top-
>leftChild, n);
}
return top;
}
void PrintTree(Tree *t, int n)
{
if(t != NULL)
{
PrintTree(t->rightChild, n+1);
for(int i = 0; i < n; i++)
cout<<" ";
cout<<t->data<<endl;
PrintTree(t->leftChild, n+1);
}
}
