Сортировка по возрастанию с помощью бинарного дерева

В С++ в STL нет контейнера для формирования динамической структуры бинарное дерево. Поэтому используют структуру с полями указателями на левое и правое поддерево:

typedef struct TNode *PNode;

struct TNode

{

    int data;

    PNode left;

    PNode right;

} ;

Будем вводить элементы массива и сразу формировать дерево:

Функция добавления звена в дерево:

void MakeTree(int k, PNode &p)

 {

if (p==NULL) //если нет корня

    {

        p=new TNode;

        p->data=k;

        p->left=NULL;

        p->right=NULL;

    }

else {  if (k<=p->data)

// если меньше корня, то добавляем влево

        if (p->left!=NULL)

            MakeTree(k, p->left);

        else{

            p->left=new TNode;

            p->left->left=NULL;

            p->left->right=NULL;

            p->left->data=k;

        }

    }

if (k>p->data)

//если больше корня, то добавляем вправо

    {if (p->right!=NULL)

            MakeTree(k, p->right);

        else        {

            p->right=new TNode;

            p->right->left=NULL;

            p->right->right=NULL;

            p->right->data=k;        }

    }

}

}

Функции обхода дерева:

void Search_LKP(PNode p)

{//левое-корень-правое

    if(p!=NULL)

    {

        Search_LKP(p->left);

        cout << p->data << '  ';

        Search_LKP(p->right);

     }

}

Вывод данных: 1 2 3 4 5 6 9

void Search_KLP(PNode p)

{//корень-левое-правое

    if(p!=NULL)

    {

        cout << p->data << ' ';

        Search_KLP(p->left);

        Search_KLP(p->right);

    }

}
Вывод данных: 4 2 1 3 6 5 9

void Search_LPK(PNode p)

{//левое-правое-корень

    if(p!=NULL)

    {

        Search_LPK(p->left);

        Search_LPK(p->right);

        cout << p->data << ' ';

    }

}

Вывод данных: 1 3 2 5 9 6 4

Функция удаления:

void DeleteTree(PNode &p)

{

    if(p->left!=NULL)

    {

        DeleteTree(p->left);

    }

    if(p->right!=NULL)

    {

        DeleteTree(p->right);

    }

    delete p;

}

Основная программа:

int main()

{

    PNode t;

    t=NULL;

    int x;

//ввод  до нуля  

    cin>>x;

    while(x!=0)

    {

        MakeTree(x, t);   cin>>x;

    }

//обход дерева

    Search_LKP(t);

//удаление дерева

    DeleteTree(t);

    return 0;

}