Частотный словарь из слов текстового файла в виде дерева двоичного поиска

void print_Tree(tnode *tree,int level)
{
    if(tree != NULL)
    {
        print_Tree(tree->left,level + 1);
        for(int i = 0;i < level;i++) 
            printf("      ");
        printf("%s\n",tree->data); 
        print_Tree(tree->right,level + 1);
    }
}

#include "stdafx.h"
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <locale>
#include <iostream>
using namespace std;
 
struct tnode {
    char *data;
    tnode *parent;
    tnode *left;
    tnode *right;
};
 
 
void print_Tree(tnode *tree,int level);
void inorder_tree_walk(tnode *tree);
tnode *tree_insert(tnode *tree, char *item);
tnode *tree_minimum(tnode *tree);
tnode *tree_maximum(tnode *tree);
tnode *tree_search(tnode *tree, char *s);
 
tnode *tree_delete(tnode *tree, tnode *z);
void print_menu();
 
const int MAXLINE = 100;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
    tnode *tree = (tnode *)malloc(sizeof(tnode));
    tree = NULL;
    FILE *in = fopen("input.txt", "r");
    char *buf = (char *)malloc(MAXLINE*sizeof(char));
    while(!feof(in))
    {
        fscanf(in, "%s", buf);
        if(strcmp(buf, ""))
            if(tree == NULL)
                tree = tree_insert(tree, buf);
            else
                tree_insert(tree, buf);
        strcpy(buf, "");
    }
    fclose(in);
    int action;
    tnode *node = (tnode *)malloc(sizeof(tnode));
    while(true)
    {
        print_menu();
        printf("Выберите пункт меню:\n");
        scanf("%d", &action);
        while(action < 0 || action > 7)
        {
            printf("Ошибка! Неправельный ввод! Выберите пунк меню:\n");
            scanf("%d", &action);
        }
        if(action == 0)
            break;
        switch(action)
        {
        case 1:
            inorder_tree_walk(tree);
            printf("\n");
            break;
 
        case 2:
            printf("Введите слово для добавления :\n");
            scanf("%s", buf);
            tree_insert(tree, buf);
            in = fopen("input.txt", "a");
            fprintf(in, "%s\n", buf);
            printf("Слово добавлено\n");
            fclose(in);
            strcpy(buf, "");
            break;
        case 3:
            printf("Введите слово для удаления:\n");
            scanf("%s", buf);
            node = tree_search(tree, buf);
            if(node != NULL)
            {
 
                tree_delete(tree, node);
 
                printf("Слово удалено\n");
            }
            else
                printf("Слово не найдено\n");
            break;
 
        case 4:
            node = tree_maximum(tree);
            printf("%s\n", node->data);
            break;
        case 5:
            node = tree_minimum(tree);
            printf("%s\n", node->data);
            break;
        case 6:
            printf("\n");
            print_Tree(tree,0);
            break;
        case 7:
            printf("Введите слово для поиска:\n");
        scanf("%s", buf);
            double duration1=0;
            double duration2=0;
            clock_t start1, finish1;
            start1 = clock();
            for (int i = 0; i<100000; i++)
                node = tree_search(tree, buf);
            finish1 = clock();
            duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;
 
            FILE *in = fopen("input.txt", "r");
            char *s = (char *)malloc(MAXLINE*sizeof(char));
            fscanf(in, "%s", s);
            int ser=0;
            clock_t start2, finish2;
            start2 = clock();
            for (int i = 0; i<10000; i++)
            {
                FILE *in = fopen("input.txt", "r");
                while(!(feof(in)))
                {
                    if((strcmp(s, buf))!=0)
                    {
                        ser = 0;
                        fscanf(in, "%s", s);
                    }
                    else
                    {
                        ser = 1;
                        break;
                    }
                }
                fclose(in);
            }
            finish2 = clock();
            duration2 = (double)(finish2 - start2) / CLOCKS_PER_SEC;
 
            fclose(in);
            if((node != NULL) && (ser == 1))
                printf("Слово найдено\n");
            else
            {
                int question;
                printf("Слово не найдено! Хотите добавить его? (1-да/0-нет)\n");
                scanf("%d",&question);
                if (question == 1)
                {
                    tree_insert(tree, buf);
                    FILE *in = fopen("input.txt", "a");
                    fprintf(in, "\n%s\n", buf);
                    printf("Слово добавлено\n");
                    fclose(in);
                }
                else
                    break;
            }
            //printf("\n%lf   %lf\n",duration1,duration2);
            cout<<"Время поиска: В дереве = "<< duration1<< "   В файле = "<<duration2<<endl;
            strcpy(buf, "");
            break;
 
 
        }
        
 
    }
    return 0;
}
 
void print_menu()
{
 
    printf(" 1 - Обход дерева\n");
    printf(" 2 - Вставить слово\n");
    printf(" 3 - Удалить слово\n");
    printf(" 4 - Максимальное\n");
    printf(" 5 - Минимальное\n");
    printf(" 6 - Вывести дерево\n");
    printf(" 7 - Поиск слова\n");
    printf(" 0 - Выход\n");
 
}
 
void print_Tree(tnode *tree,int level)
{
    if(tree != NULL)
    {
        print_Tree(tree->left,level + 1);
        for(int i = 0;i < level;i++) 
            printf("      ");
        printf("%s\n",tree->data); 
        print_Tree(tree->right,level + 1);
    }
}
 
tnode *tree_delete(tnode *tree, tnode *z)
{
    tnode *y;
    if(z->left == NULL || z->right == NULL)
        y = z;
    tnode *x;
    if(y->left != NULL)
        x = y->left;
    else
        x = y->right;
    if(x != NULL)
        x->parent = y->parent;
    if(y->parent == NULL)
        return x;
    else if(y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;
    if(y != z)
        strcpy(z->data, y->data);
    return y;
}
 
 
 
tnode *tree_search(tnode *tree, char *s)
{
    while(tree != NULL && strcmp(s, tree->data))
    {
        if(strcmp(s, tree->data) < 0)
            tree = tree->left;
        else
            tree = tree->right;
    }
    return tree;
}
 
tnode *tree_maximum(tnode *tree)
{
    while(tree->right != NULL)
        tree = tree->right;
    return tree;
}
 
tnode *tree_minimum(tnode *tree)
{
    while(tree->left != NULL)
        tree = tree->left;
    return tree;
}
 
tnode *tree_insert(tnode *tree, char *item)
{
    tnode *z = (tnode *)malloc(sizeof(tnode));
    z->data = (char *)malloc(MAXLINE*sizeof(char));
    strcpy(z->data, item);
    z->left = z->right = NULL;
    tnode *y = NULL;
    tnode *x = tree;
    while(x != NULL)
    {
        y = x;
        if(strcmp(z->data, x->data) < 0)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if(y == NULL)
        return z;
    else if(strcmp(z->data, y->data) < 0)
        y->left = z;
    else
        y->right = z;
}
 
void inorder_tree_walk(tnode *tree)
{
    if(tree != NULL)
    {
        inorder_tree_walk(tree->left);
        printf("%s\n", tree->data);
        inorder_tree_walk(tree->right);
    }
}

tnode *tree = (tnode *)malloc(sizeof(tnode));
tree = NULL;

#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <time.h>
 
#define IN_FILE            "input.txt" 
 
struct TREE_NODE;
 
static void    PrintMenu();
 
static void          Insert (TREE_NODE** pNode,TREE_NODE* pParent,const char* const pszStr);
static TREE_NODE*    Search (TREE_NODE** pNode,const char* const pszStr);
 
static void          Walker (const TREE_NODE* const pNode);
static void          Print  (const TREE_NODE* const pNode,int iLevel);
 
static void          DelNode(TREE_NODE* pNode);
static TREE_NODE*    Minimum(TREE_NODE* pNode);
static TREE_NODE*    Maximum(TREE_NODE* pNode);
static void          Delete (TREE_NODE* pNode);
 
struct TREE_NODE
{           
   char*          pData;
   int            iCount;
   TREE_NODE*     pParent;
   TREE_NODE*     pLeft;
   TREE_NODE*     pRight;
};
      
const int   MAX_LINE = 100;
const int   TIMES1   = 100000;
const int   TIMES2   = 10000;
 
///////////////////////////////////////////////////////////////////////////////
 
int _tmain(int argc,_TCHAR** argv)
{
   TREE_NODE*   pRoot = NULL;
   
   FILE*    pIn = fopen(IN_FILE,"rt");
   
   char*    pBuf = new char[MAX_LINE + 1];
   
   while (!feof(pIn))
   {
      *pBuf = 0;
 
      fscanf(pIn,"%s",pBuf);
 
      if (*pBuf)
      {
         Insert(&pRoot,NULL,pBuf);
      }
   }
 
   fclose(pIn);
   pIn = NULL;
   
   int      iAction = 0;
   
   TREE_NODE*   pNode = new TREE_NODE;
   
   if (!pNode)
   {
      // Error !
      return 0;
   }
 
   memset(pNode,0,sizeof(TREE_NODE));
 
   do
   {
      bool     bAnswered = false;
 
      while (!bAnswered)
      {
         PrintMenu();
      
         printf("You choice:\n");
         iAction = getch();
 
         switch (iAction)
         {
            case 'W':
            case 'w':
            {
               Walker(pRoot);
               printf("\n");
 
               bAnswered = true;
               break;
            }
            case 'I':
            case 'i':
            {
               printf("Type word for append:\n");
               gets(pBuf);
 
               Insert(&pRoot,NULL,pBuf);
 
               pIn = fopen(IN_FILE,"a");
 
               fprintf(pIn,"%s\n",pBuf);
               printf("Appended.\n");
 
               fclose(pIn);
 
               strcpy(pBuf,"");
 
               bAnswered = true;
               break;
            }
            case 'D':
            case 'd':
            {
               printf("Type word for delete:\n");
               gets(pBuf);
 
               pNode = Search(&pRoot,pBuf);
 
               if (pNode)
               {
                  DelNode(pNode);
 
                  printf("Deleted.\n");
               }
               else
               {
                  printf("Nothing found.\n");
               }
 
               bAnswered = true;
               break;
            }
            case 'M':
            {
               pNode = Maximum(pRoot);
 
               printf("%s\n",pNode->pData);
 
               bAnswered = true;
               break;
            }
            case 'm':
            {
               pNode = Minimum(pRoot);
 
               printf("%s\n",pNode->pData);
 
               bAnswered = true;
               break;
            }
            case 'P':
            case 'p':
            {
               printf("\n");
 
               Print(pRoot,0);
 
               bAnswered = true;
               break;
            }
            case 'F':
            case 'f':
            {
               printf("Type word for search:\n");
               gets(pBuf);
 
               clock_t     start1 = clock();
 
               for (int ii = 0; ii < TIMES1; ++ii)
               {
                  pNode = Search(&pRoot,pBuf);
               }
 
               clock_t     finish1 = clock();
 
               double      duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;
 
               FILE* pIn = fopen(IN_FILE,"rt");
 
               char*    pszStr = new CHAR[MAX_LINE + 1];
 
               fscanf(pIn,"%s",pszStr);
 
               bool     bFound = false;
 
               clock_t     start2 = clock();
 
               for (int jj = 0; jj < TIMES2; ++jj)
               {
                  FILE* pIn = fopen(IN_FILE,"r");
 
                  while (!(feof(pIn)))
                  {
                     if (strcmp(pszStr,pBuf))
                     {
                        bFound = false;
                        fscanf(pIn,"%s",pszStr);
                     }
                     else
                     {
                        bFound = true;
                        break;
                     }
                  }
 
                  fclose(pIn);
               }
 
               clock_t     finish2 = clock();
 
               double      duration2 = (double) (finish2 - start2) / CLOCKS_PER_SEC;
 
               fclose(pIn);
 
               if (pNode && bFound)
               {
                  printf("Found.\n");
               }
               else
               {
                  int   iAppend = 0;
 
                  printf("Word not found! Append? (Y/N)\n");
                  iAppend = getch();
 
                  if ((iAppend == 'Y') || (iAppend == 'y'))
                  {
                     Insert(&pRoot,NULL,pBuf);
 
                     FILE* pIn = fopen(IN_FILE,"at");
 
                     fprintf(pIn,"\n%s\n",pBuf);
 
                     printf("Appended.\n");
 
                     fclose(pIn);
                  }
                  else
                  {
                     break;
                  }
               }
 
               printf("Search time: In the tree: %10.3f\n",duration1);
               printf("Search time: In the file: %10.3f\n",duration2);
 
               bAnswered = true;
               break;
            }
            case 'E':
            case 'e':
            {
               iAction   = 0;
               bAnswered = true;
               break;
            }
            default:
            {
               printf("Error! Incorrect input! You choice:\n");
            }
         }
      }
   }
   while (iAction);
 
   Delete(pRoot);
 
   delete pNode;
   pNode = NULL;
 
   delete[] pBuf;
   pBuf = NULL;
 
   return 0;
}
 
///////////////////////////////////////////////////////////////////////////////
 
static void PrintMenu()
{
   printf(" W - Walk\n");
   printf(" I - Insert\n");
   printf(" D - Delete\n");
   printf(" M - Max\n");
   printf(" m - Min\n");
   printf(" P - Print\n");
   printf(" F - Find\n");
   printf(" E - Exit\n");
}
 
///////////////////////////////////////////////////////////////////////////////
 
static void Print(const TREE_NODE* const pNode,int iLevel)
{
   if (pNode)
   {
      Print(pNode->pLeft,iLevel + 1);
 
      for (int ii = 0; ii < iLevel; ++ii)
      {
         printf(" ");
      }
 
      printf("%s\n",pNode->pData);
 
      Print(pNode->pRight,iLevel + 1);
   }
}
 
///////////////////////////////////////////////////////////////////////////////
 
static void Delete(TREE_NODE* pNode)
{
   if (!pNode)
   {
      return;
   }
 
   Delete(pNode->pLeft);
   Delete(pNode->pRight);
 
   if (pNode && pNode->pData)
   {
      delete[] pNode->pData;
      pNode->pData = NULL; 
   }
   
   if (pNode)
   {
      delete pNode;
      pNode = NULL;
   }
}
 
///////////////////////////////////////////////////////////////////////////////
 
static void DelNode(TREE_NODE* pNode)
{  
   TREE_NODE*    pParent = pNode->pParent;
   
   if (!pNode->pLeft && !pNode->pRight)
   {
      if (pParent->pLeft == pNode)
      {
         pParent->pLeft = NULL;
      }
 
      if (pParent->pRight == pNode)
      {
         pParent->pRight = NULL;
      }
 
      delete pNode;
      pNode = NULL;
 
      return;
   }
 
   if (pNode->pLeft && !pNode->pRight)
   {
      if (pParent->pLeft == pNode)
      {
         pParent->pLeft = pNode->pLeft;
      }
 
      if (pParent->pRight == pNode)
      {
         pParent->pRight = pNode->pLeft;
      }
 
      delete pNode;
      pNode = NULL;
 
      return;
   }
 
 
   if (!pNode->pLeft && pNode->pRight)
   {
      if (pParent->pLeft == pNode)
      {
         pParent->pLeft = pNode->pRight;
      }
 
      if (pParent->pRight == pNode)
      {
         pParent->pRight = pNode->pRight;
      }
 
      delete pNode;
      pNode = NULL;
 
      return;
   }
 
   if (pNode->pLeft && pNode->pRight)
   {
      TREE_NODE*    pFather = pNode;
   
      TREE_NODE*    pNext = pNode->pRight;
 
      while (pNext->pLeft)
      {  
         pFather = pNext;
         pNext = pNext->pLeft;
      }
 
      pNode->pData = pNext->pData;
      pNode = pNext;
      
      return;
   }
}
 
///////////////////////////////////////////////////////////////////////////////
 
static TREE_NODE* Search(TREE_NODE** pNode,const char* const pszStr)
{  
   if (!(*pNode) || !(*pNode)->pData)
   {
      return NULL;
   }
   
   int   iResult = strcmp(pszStr,(*pNode)->pData);
 
   if (!iResult)
   {
      return *pNode;
   }
   else if (iResult < 0)
   {
      Search(&((*pNode)->pLeft),pszStr);
   }
   else if (iResult > 0)
   {
      Search(&((*pNode)->pRight),pszStr);
   }
}
 
///////////////////////////////////////////////////////////////////////////////
 
static TREE_NODE* Maximum(TREE_NODE* pNode)
{
   while (pNode->pRight)
   {
      pNode = pNode->pRight;
   }
 
   return pNode;
}
 
///////////////////////////////////////////////////////////////////////////////
 
static TREE_NODE* Minimum(TREE_NODE* pNode)
{
   while (pNode->pLeft)
   {
      pNode = pNode->pLeft;
   }
 
   return pNode;
}
 
///////////////////////////////////////////////////////////////////////////////
 
static void Insert(TREE_NODE** pNode,TREE_NODE* pParent,const char* const pszStr)
{
   if (!(*pNode))
   {
      // Make New Node
      TREE_NODE*    pTemp = new TREE_NODE;
 
      if (!pTemp)
      {
         // Error !
         return;            
      }
 
      memset(pTemp,0,sizeof(TREE_NODE));
 
      pTemp->pData = new char[MAX_LINE + 1];
 
      if (!pTemp->pData)
      {
         // Error !
         delete pTemp;
         pTemp = NULL;
         return;            
      }
   
      memset(pTemp->pData,0,MAX_LINE + 1);
 
      strncpy(pTemp->pData,pszStr,MAX_LINE);
      pTemp->pData[MAX_LINE] = 0;  // ASCIIZ
      pTemp->pParent = pParent;
      ++pTemp->iCount; 
 
      (*pNode) = pTemp;
 
      return;
   }
 
   if (*pNode && (*pNode)->pData)
   {
      int   iResulr = strcmp(pszStr,(*pNode)->pData);
 
      if (iResulr < 0)
      {
         Insert(&((*pNode)->pLeft),*pNode,pszStr);
      }
      else if (iResulr > 0)
      {
         Insert(&((*pNode)->pRight),*pNode,pszStr);
      }
      else
      {
         ++(*pNode)->iCount;
      }
   }
}
 
///////////////////////////////////////////////////////////////////////////////
 
static void Walker(const TREE_NODE* const pNode)
{
   if (pNode)
   {
      Walker(pNode->pLeft);
 
      printf("%s (%d)\n",pNode->pData,pNode->iCount);
 
      Walker(pNode->pRight);
   }
}