laba18

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define COUNT 10
struct Tree { 	    //структура бинарного дерева
    char word[20];
    int length;
    Tree* Left; 	    //указатель на левый потомок
    Tree* Right; 	    //указатель на правый потомок
};
Tree* BTree = NULL;
//рекурсивная функция создания/добавления вершины дерева
void AddNode(Tree** BTree, Tree* TreeElement)
{
	Tree* rr;
	rr = *BTree; //вспомогательный указатель на указатель дерева
	if (rr == NULL) *BTree = TreeElement;  //если узла нет, создаем узел
	else
		if (strlen(TreeElement->word) < strlen(rr->word))  //значение тек. узла поддерева < значения узла дерева,
			AddNode(&rr->Left, TreeElement); //то заносим значение узла в левое поддерево
		else AddNode(&rr->Right, TreeElement); //иначе заносим значение узла в правое поддерево
}
int check(char* st)
{
    int fl = 0;
    char GL[] = "aeuyoiIAEUYO";
    for (int i = 0; i < 12; i++)
        if (st[0] == GL[i])
            fl++;
    return fl;
}
void print2DUtil(Tree* root, int space)
{
    if (root == NULL)
        return;
    space += COUNT;
    print2DUtil(root->Right, space);
    printf("\n");
    for (int i = COUNT; i < space; i++)
        printf(" ");
    printf("%s [%d],\n", root->word,root->length);
    print2DUtil(root->Left, space);
}
void print2D(struct Tree* root)
{
    print2DUtil(root, 0);

}

void Tree2(Tree* r)//обратный
{
    if (r != NULL)
    {
        Tree2(r->Left);
        printf("%s|| word length is %d\n", r->word,r->length);
        Tree2(r->Right);
    }
}
void inOrderTravers(Tree* root) //прямой
{
    if (root) {
        inOrderTravers(root->Right);
        printf("%s|| word length is %d\n", root->word, root->length);
        inOrderTravers(root->Left);
    }
}
void Treevowels(Tree*r)
{
    if (r != NULL)
    {
        if (check(r->word) > 0)
            printf("%4s\n", r->word);
        Treevowels(r->Left);
        Treevowels(r->Right);
    }
}
Tree* DeleteNode(Tree* node) {
    if (node == NULL) {
        return node;
    }
    else {
        if (node->Left != NULL) {
            node->Left = DeleteNode(node->Left);
        }
        if (node->Right != NULL)
            node->Right = DeleteNode(node->Right);
        if (check(node->word) > 0) {
            Tree* tmp;
            if (node->Right == NULL)
                tmp = node->Left;
            else {
                Tree* ptr = node->Right;
                if (ptr->Left == NULL) {
                    ptr->Left = node->Left;
                    tmp = ptr;
                }
                else {
                    Tree* pmin = ptr->Left;

                    while (pmin->Left != NULL) {
                        ptr = pmin;
                        pmin = ptr->Left;
                    }
                    ptr->Left = pmin->Right;
                    pmin->Left = node->Left;
                    pmin->Right = node->Right;
                    tmp = pmin;
                }
            }
            delete node;
            return tmp;
        }
    }
    return node;
}
int main(int argc, char* argv[])
{
    //указатель, тип которого соответствует узлу дерева.
    //В начале создается пустое дерево

    //Указатель на узел дерева
    Tree* TreeElement;
    char* word ;  //вводимые значения узлов дерева
    word = new char[20];
    puts("input words");
    while (gets_s(word, 20),strlen(word)!=0) // продолжать вводить пока не будет введено _
    {
        TreeElement = new Tree;  //выделение памяти под узел дерева
        strcpy_s(TreeElement->word,20,word);
        TreeElement->length = strlen(word);//запись введенного значения в узел дерева
        TreeElement->Left = NULL; //задание пустого левого поддерева
        TreeElement->Right = NULL; //задание пустого правого поддерева
        AddNode(&BTree, TreeElement); // добавление узла TreeElement в дерево BTree
         // чтение следующего числа
    }
    puts(" == Result==");
    print2D(BTree); // печать дерева BTree
    printf("\n");
    puts("sorted way to show. Reverse order");
    Tree2(BTree);//Печатает в порядке от самого маленького
    printf("\n");
    puts("sorted way to show. Straight order");
    inOrderTravers(BTree);
    printf("\n");
    puts("needed words");
    Treevowels(BTree);
    printf("\n");
    puts("after delete");
    BTree = DeleteNode(BTree);
    Tree2(BTree);
    puts("============================");
    puts("add new words or press enter to skip");
    while (gets_s(word, 20), strlen(word) != 0) // продолжать вводить пока не будет введено _
    {
        TreeElement = new Tree;  //выделение памяти под узел дерева
        strcpy_s(TreeElement->word, 20, word); //запись введенного значения в узел дерева
        TreeElement->Left = NULL; //задание пустого левого поддерева
        TreeElement->Right = NULL; //задание пустого правого поддерева
        AddNode(&BTree, TreeElement); // добавление узла TreeElement в дерево BTree
         // чтение следующего числа
    }
    puts("");
    puts("============================");
    print2D(BTree); // печать дерева BTree
    printf("\n");
    puts("sorted way to show");
    Tree2(BTree);
    return 0;
}