Question

利用二叉排序树，统计随机从键盘上输入的字符个数，然后输出字符和对应的个数

Answer 1

1、统计字符串中字符出现的次数
编写一个程序，由键盘输入一个字符串，统计该字符串中出现的字符及其次数。然后输出结果。要求用一个二叉树来保存处理结果，字符串中每个不同的字符用树的结点表示，结点应该包含四个域：该字符、该字符出现的次数、左子树指针、右子树指针；其中左子树的字符的ASCII码均小于该字符，右子树的字符的ASCII码均大于该字符。

提示：
ü 从字符串中依次读取字符，在二叉树中查找该字符是否存在。
ü 如果存在，则该字符的出现次数加1；如果不存在，则按照二叉排序树的要求插入该字符结点，同时设置出现次数为1。
ü 全部字符读完以后，调用二叉树的中序遍历，有序的输出每个字符及其出现的次数。

Code:
/**
* Author: XadillaX
* Data: 2010-12-27
*/
#include <iostream>
using namespace std;

struct BSTreeCH {
char ch;
int time;
BSTreeCH *lc, *rc;

/** 构造函数 */
BSTreeCH(char _ch)
{
lc = rc = NULL;
ch = _ch;
time = 1;
}
};

/**
* @brief 对字符统计二叉树插入节点
*/
void InsertBST_CH(BSTreeCH *t, char ch)
{
/** 若已存在 */
if(ch == t->ch)
{
t->time++;
return;
}

/** 直接插入或者递归插入 */
if(ch < t->ch && NULL == t->lc) t->lc = new BSTreeCH(ch);
else
if(ch > t->ch && NULL == t->rc) t->rc = new BSTreeCH(ch);
else
if(ch < t->ch) InsertBST_CH(t->lc, ch);
else
if(ch > t->ch) InsertBST_CH(t->rc, ch);
}

/**
* @brief 删除字符统计二叉树
*/
void DelBST_CH(BSTreeCH *t)
{
if(NULL != t->lc) DelBST_CH(t->lc);
if(NULL != t->rc) DelBST_CH(t->rc);

delete t;
}

/**
* @brief 中序遍历字符统计二叉树
*/
void TraBST_CH(BSTreeCH *t)
{
if(NULL != t->lc) TraBST_CH(t->lc);
printf("'%c'(%4d): %4d/n", t->ch, t->ch, t->time);
if(NULL != t->rc) TraBST_CH(t->rc);
}

/**
* @brief 统计字符
*/
void BST_CH()
{
FILE *fp;
BSTreeCH *root = NULL;

if(NULL == (fp = fopen("a.txt", "r")))
{
printf("Error on opening file./n");
return;
}

/** 读文件 */
while(!feof(fp))
{
char ch;
ch = fgetc(fp);
if(-1 == ch) break;

/** 建根 */
if(NULL == root)
{
root = new BSTreeCH(ch);
continue;
}

/** 插入 */
InsertBST_CH(root, ch);
}

fclose(fp); ///< 关闭文件

TraBST_CH(root); ///< 遍历树
DelBST_CH(root); ///< 删除树
root = NULL;
}

int main()
{
BST_CH();

return 0;
}