二叉排序树（字符串）

二叉排序树（字符串）

时间： 1ms        内存：128M

描述：

设计一个程序，读入一个字符串，统计该字符串中出现的字符以及出现次数然后输出。要求用一个二叉树来保存处理结果，字符串中的各个不同的字符用节点描述，每个节点包含四个域：

1、字符

2、该字符的出现次数

3、指向ASCII码小于该字符的左子树指针

4、指向ASCII码大于该字符的右子树指针

输入：

输入数据只有一行，为一行字符串，中间没用空格。

输出：

按照题意创建的二叉树。层序输出，二叉树中每个节点输出一行，每行包含两个元素，字符本身和它出现的次数。

示例输入：

bcabd

示例输出：

b 2
a 1
c 1
d 1

提示：

参考答案（内存最优[1776]）：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct node
{
    char key;
    int count;
    struct node *lchild,*rchild;
} BSTNode;
int InsertBST(BSTNode *&p,char k)
{
    if(p==NULL)
    {
        p=(BSTNode *)malloc(sizeof(BSTNode));
        p->key=k;
        p->count=1;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if(k==p->key)
    {
        p->count++;
        return 0;
    }
    else if(k<p->key)
        return InsertBST(p->lchild,k);
    else return InsertBST(p->rchild,k);
}
BSTNode * CreateBST(char s[1000],int n)
{
    BSTNode *bt = NULL;
    int i=0;
    while(i<n)
    {
        InsertBST(bt,s[i]);
        i++;
    }
    return bt;
}
void LevelOrder(BSTNode *b)
{
    BSTNode *p;BSTNode *qu[1000];
    int front,rear;
    front=rear=-1;
    rear++;
    qu[rear]=b;
    while(front!=rear)
    {
        front++;
        p=qu[front];
        printf("%c %d\n",p->key,p->count);
        if(p->lchild!=NULL)
        {
            rear++;
            qu[rear]=p->lchild;
        }
        if(p->rchild!=NULL)
        {
            rear++;
            qu[rear]=p->rchild;
        }
    }
}
int main()
{
    char s[1000];
    gets(s);
    BSTNode *bt=CreateBST(s,strlen(s));
    LevelOrder(bt);
    return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct node
{
    char key;
    int count;
    struct node *lchild,*rchild;
} BSTNode;
int InsertBST(BSTNode *&p,char k)
{
    if(p==NULL)
    {
        p=(BSTNode *)malloc(sizeof(BSTNode));
        p->key=k;
        p->count=1;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if(k==p->key)
    {
        p->count++;
        return 0;
    }
    else if(k<p->key)
        return InsertBST(p->lchild,k);
    else return InsertBST(p->rchild,k);
}
BSTNode * CreateBST(char s[1000],int n)
{
    BSTNode *bt = NULL;
    int i=0;
    while(i<n)
    {
        InsertBST(bt,s[i]);
        i++;
    }
    return bt;
}
void LevelOrder(BSTNode *b)
{
    BSTNode *p;BSTNode *qu[1000];
    int front,rear;
    front=rear=-1;
    rear++;
    qu[rear]=b;
    while(front!=rear)
    {
        front++;
        p=qu[front];
        printf("%c %d\n",p->key,p->count);
        if(p->lchild!=NULL)
        {
            rear++;
            qu[rear]=p->lchild;
        }
        if(p->rchild!=NULL)
        {
            rear++;
            qu[rear]=p->rchild;
        }
    }
}
int main()
{
    char s[1000];
    gets(s);
    BSTNode *bt=CreateBST(s,strlen(s));
    LevelOrder(bt);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。