пятница, 25 октября 2019 г.

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

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

typedef struct TNode *PNode;
typedef struct TNode
{
    int data;
    PNode left;
    PNode right;
} TNode;
Будем вводить элементы массива и сразу формировать дерево:
Функция добавления звена в дерево:
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;
}

1 комментарий:

  1. Do you understand there's a 12 word phrase you can communicate to your partner... that will trigger deep feelings of love and impulsive attraction for you buried within his heart?

    Because deep inside these 12 words is a "secret signal" that fuels a man's instinct to love, treasure and guard you with his entire heart...

    12 Words Who Trigger A Man's Love Instinct

    This instinct is so built-in to a man's mind that it will drive him to try harder than before to build your relationship stronger.

    Matter-of-fact, fueling this powerful instinct is absolutely mandatory to getting the best ever relationship with your man that the moment you send your man a "Secret Signal"...

    ...You'll instantly notice him open his soul and heart for you in such a way he haven't experienced before and he will see you as the one and only woman in the world who has ever truly attracted him.

    ОтветитьУдалить