二叉排序树(字符串)

时间: 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;
}

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