基于二叉查找树的字母查找程序

本文主要是介绍基于二叉查找树的字母查找程序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

记录下之前写的一个文件字母查找程序

数据结构采用二叉查找树，操作对象是文本文档中用户输入的字母

可以添加删除查找字母

二叉查找树会自动排序每个对象，检索起来很方便。对象越多，相对于遍历比较的优势越大。但是如果树根root设置的不好，会导致树的一侧很多节点，另一侧节点很少。

主程序：

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include "tree_17_7.h"

char * s_gets(char * st, int n);
void eatline(void);
void CountYourChar(Tree *pTree);
void PutInTree(FILE *fp,Tree *pTree);
void ShowAndCount(Tree *pTree);
void ShowCharInfo(Item item);
void AddChar(Tree *pTree,FILE *fp);

int main(void)
{
   Tree Tree,*pTree;
   pTree=&Tree;
   InitializeTree(pTree);

   FILE *fp;
   if((fp=fopen("Practice17_7.txt","at+"))==NULL)
   {
       puts("cannot open file");
       exit(EXIT_FAILURE);
   }
   PutInTree(fp,pTree);


   puts("Choose from the lists:");
   puts("a) add your char to tree and append to file");
   puts("s) show all the character and count the times they showing up");
   puts("f) enter a character and will count times this character shows up in this .txt");
   puts("q) quit");
   int8_t Choice;
   while((Choice = getchar())!=EOF && Choice != 'q')
   {
       eatline();
       switch(Choice)
       {
           case 'a':
                AddChar(pTree,fp);
               break;
           case 's':
                Traverse(pTree,ShowCharInfo);
               break;
           case 'f':
               CountYourChar(pTree);
               break;
           default:
               break;
       }
        puts("Choose from the lists:");
        puts("a) add your char to tree and append to file");
        puts("s) show all the character and count the times they showing up");
        puts("f) enter a character and will count times this character shows up in this .txt");
        puts("q) quit");
        eatline();
   }
    fclose(fp);

   return 0;
}

void AddChar(Tree *pTree,FILE *fp)
{
    Trnode * tempSeekResult;
    Item AddChar;
    AddChar.Char_Counter=0;
    puts("enter a character you want to add,enter 'q' to quit");
    while((AddChar.EnglishChar=getchar())!=EOF && AddChar.EnglishChar!='q')
    {
        eatline();
        if(TreeIsFull(pTree)==true)
        {
            puts("Tree is full now");
            break;
        }
        tempSeekResult = SeekItem(&AddChar, pTree).child;
        if(tempSeekResult != NULL)
        {
            tempSeekResult->item.Char_Counter++;
            puts("add item exist,update the numbers");
        }
        else
        {
            if(AddItem(&AddChar,pTree)==false)
            {
                puts("add item failed");
                break;
            }
            printf("Character %c has been successfully added\n",AddChar.EnglishChar);
        }
        fputc(AddChar.EnglishChar,fp);
        puts("enter a character you want to add,enter 'q' to quit");
    }

}

void ShowCharInfo(Item item)
{
    printf("%c %u\n",item.EnglishChar,item.Char_Counter);
}


void CountYourChar(Tree *pTree)
{
   Trnode * tempSeekResult;
   Item SearchChar;
   SearchChar.Char_Counter=0;
   puts("enter a character,enter 'q' to quit");
   while((SearchChar.EnglishChar=getchar())!=EOF && SearchChar.EnglishChar!='q')
   {
       eatline();
       tempSeekResult = SeekItem(&SearchChar, pTree).child;
        if(tempSeekResult == NULL)
        {
            puts("no such char");
            continue;
        }
        else
        {
            printf("there're %u %c\n",tempSeekResult->item.Char_Counter,tempSeekResult->item.EnglishChar);
        }
        puts("enter a character,enter 'q' to quit");

   }

}

void PutInTree(FILE *fp,Tree *pTree)
{
   Item Item,*MyItem;
   MyItem = &Item;
   while( ( (MyItem->EnglishChar) = getc(fp) ) != EOF)
   {
       MyItem->Char_Counter=1;
       if(TreeIsFull(pTree)==true)
       {
           puts("Tree is not big enough");
           break;
       }
       if(AddItem(MyItem,pTree)==false)
       {
           puts("add item failed");
           break;
       }
   }

}

void ShowAndCount(Tree *pTree)
{
   Tree *ForSearch;
   ForSearch=pTree;
   while(ForSearch->root->left!=NULL)
   {
       printf("%c %u\n",ForSearch->root->item.EnglishChar,ForSearch->root->item.Char_Counter);
       ForSearch->root=ForSearch->root->left;
   }
   ForSearch=pTree;
   while(ForSearch->root->right!=NULL)
   {
       printf("%c %u\n",(ForSearch->root->item).EnglishChar,(ForSearch->root->item).Char_Counter);
       ForSearch->root=ForSearch->root->right;
   }
}

void eatline(void)
{
   while (getchar() != '\n')
       continue;
}
char * s_gets(char * st, int n)
{
   char * ret_val;
   char * find;
   ret_val = fgets(st, n, stdin);
   if (ret_val)
   {
       find = strchr(st, '\n'); // 查找换行符
       if (find) // 如果地址不是 NULL,
           *find = '\0'; // 在此处放置一个空字符
       else
           while (getchar() != '\n')
               continue; // 处理输入行的剩余字符
   }
   return ret_val;
}

tree.c

/* tree.c -- 树的支持函数 */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree_17_7.h"


/* 局部函数的原型 */
static Trnode * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode(Trnode * new_node, Trnode * root);
static void InOrder(const Trnode * root, void(*pfun)(Item item));
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode * ptr);

/* 函数定义 */
void InitializeTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
    if (ptree->root == NULL)
        return true;
    else
        return false;
}

bool TreeIsFull(const Tree * ptree)
{
    if (ptree->size == MAXITEMS)
        return true;
    else
        return false;
}

int TreeItemCount(const Tree * ptree)
{
    return ptree->size;
}

bool AddItem(const Item * pi, Tree * ptree)
{
    Trnode * new_node;
    Pair tempSeekBack;
    if (TreeIsFull(ptree))
    {
        fprintf(stderr, "Tree is full\n");
        return false; /* 提前返回 */
    }
    tempSeekBack = SeekItem(pi, ptree);
    if (tempSeekBack.child != NULL)
    {
        tempSeekBack.child->item.Char_Counter++;
        return true; /* 提前返回 */
    }
    new_node = MakeNode(pi); /* 指向新节点 */
    if (new_node == NULL)
    {
        fprintf(stderr, "Couldn't create node\n");
        return false; /* 提前返回 */
    }
    /* 成功创建了一个新节点 */
    ptree->size++;
    if (ptree->root == NULL) /* 情况1：树为空 */
        ptree->root = new_node; /* 新节点为树的根节点 */
    else /* 情况2：树不为空 */
        AddNode(new_node, ptree->root);/* 在树中添加新节点 */
    return true; /* 成功返回 */
}

bool InTree(const Item * pi, const Tree * ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

bool DeleteItem(const Item * pi, Tree * ptree)
{
    Pair look;
    look = SeekItem(pi, ptree);
    if (look.child == NULL)
        return false;
    if (look.parent == NULL) /* 删除根节点项 */
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else
        DeleteNode(&look.parent->right);
    ptree->size--;
    return true;
}

void Traverse(const Tree * ptree, void(*pfun)(Item item))
{
    if (ptree != NULL)
        InOrder(ptree->root, pfun);
}

void DeleteAll(Tree * ptree)
{
    if (ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree->root = NULL;
    ptree->size = 0;
}

/* 局部函数 */
static void InOrder(const Trnode * root, void(*pfun)(Item item))
{
    if (root != NULL)
    {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}

static void DeleteAllNodes(Trnode * root)
{
    Trnode * pright;
    if (root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

static void AddNode(Trnode * new_node, Trnode * root)
{
    if (ToLeft(&new_node->item, &root->item))
    {
        if (root->left == NULL) /* 空子树 */
            root->left = new_node; /* 把节点添加到此处 */
        else
            AddNode(new_node, root->left); /* 否则处理该子树 */
    }
    else if (ToRight(&new_node->item, &root->item))
    {
        if (root->right == NULL)
            root->right = new_node;
        else
            AddNode(new_node, root->right);
    }
    else /* 不允许有重复项 */
    {
        fprintf(stderr, "location error in AddNode()\n");
        exit(1);
    }
}

static bool ToLeft(const Item * i1, const Item * i2)
{
    if ( i1->EnglishChar < i2->EnglishChar)
        return true;
    else
        return false;
}

static bool ToRight(const Item * i1, const Item * i2)
{
    if ( i1->EnglishChar > i2->EnglishChar)
        return true;
    else
        return false;
}

static Trnode * MakeNode(const Item * pi)
{
    Trnode * new_node;
    new_node = (Trnode *) malloc(sizeof(Trnode));
    if (new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

Pair SeekItem(const Item * pi, const Tree * ptree)
{
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;
    if (look.child == NULL)
        return look; /* 提前返回 */
    while (look.child != NULL)
    {
        if (ToLeft(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if (ToRight(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else /* 如果前两种情况都不满足，则必定是相等的情 况 */
            break; /* look.child 目标项的节点 */
    }
    return look; /* 成功返回 */
}

static void DeleteNode(Trnode **ptr) /* ptr 是指向目标节点的父节点指针成员的地址 */
{
    Trnode * temp;
    if ((*ptr)->left == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->right;
        free(temp);
    }
    else if ((*ptr)->right == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
    else /* 被删除的节点有两个子节点 */
    {
        /* 找到重新连接右子树的位置 */
        for (temp = (*ptr)->left; temp->right != NULL;temp = temp->right)
            continue;
        temp->right = (*ptr)->right;
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
}

tree.h

/* tree.h -- 二叉查找数 */
#ifndef _TREE_17_7_H_
#define _TREE_17_7_H_

#include <stdbool.h>
#include <stdint.h>

/* 根据具体情况重新定义 Item */
typedef struct item {
    char EnglishChar;
    uint8_t Char_Counter;
}Item;

#define MAXITEMS 300

typedef struct trnode {
    Item item;
    struct trnode * left; /* 指向左分支的指针 */
    struct trnode * right; /* 指向右分支的指针 */
}Trnode;

typedef struct tree{
    Trnode * root;/* 指向根节点的指针 */
    int size; /* 树的项数 */
}Tree;

typedef struct pair{
    Trnode * parent;
    Trnode * child;
}Pair;


Pair SeekItem(const Item * pi, const Tree * ptree);


/* 函数原型 */
/* 操作： 把树初始化为空*/
/* 前提条件： ptree指向一个树 */
/* 后置条件： 树被初始化为空 */
void InitializeTree(Tree * ptree);\

/* 操作： 确定树是否为空 */
/* 前提条件： ptree指向一个树 */
/* 后置条件： 如果树为空，该函数返回true */
/* 否则，返回false */
bool TreeIsEmpty(const Tree * ptree);

/* 操作： 确定树是否已满 */
/* 前提条件： ptree指向一个树 */
/* 后置条件： 如果树已满，该函数返回true */
/* 否则，返回false */
bool TreeIsFull(const Tree * ptree);

/* 操作： 确定树的项数 */
/* 前提条件： ptree指向一个树 */
/* 后置条件： 返回树的项数 */
int TreeItemCount(const Tree * ptree);

/* 操作： 在树中添加一个项 */
/* 前提条件： pi是待添加项的地址 */
/* ptree指向一个已初始化的树 */
/* 后置条件： 如果可以添加，该函数将在树中添加一个项 */
/* 并返回true；否则，返回false */
bool AddItem(const Item * pi, Tree * ptree);

/* 操作： 在树中查找一个项 */
/* 前提条件： pi指向一个项 */
/* ptree指向一个已初始化的树 */
/* 后置条件： 如果在树中添加一个项，该函数返回true */
/* 否则，返回false */
bool InTree(const Item * pi, const Tree * ptree);

/* 操作： 从树中删除一个项 */
/* 前提条件： pi是删除项的地址 */
/* ptree指向一个已初始化的树 */
/* 后置条件： 如果从树中成功删除一个项，该函数返回true*/
/* 否则，返回false */
bool DeleteItem(const Item * pi, Tree * ptree);

/* 操作： 把函数应用于树中的每一项 */
/* 前提条件： ptree指向一个树 */
/* pfun指向一个函数， */
/* 该函数接受一个Item类型的参数，并无返回值*/
/* 后置条件： pfun指向的这个函数为树中的每一项执行一次*/
void Traverse(const Tree * ptree, void(*pfun)(Item item));

/* 操作： 删除树中的所有内容 */
/* 前提条件： ptree指向一个已初始化的树 */
/* 后置条件： 树为空 */
void DeleteAll(Tree * ptree);



#endif

这篇关于基于二叉查找树的字母查找程序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

基于二叉查找树的字母查找程序

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯