BST应用--字典顺序输出字符串

题意就是输入几组字符串，按照字典顺序输出，并且输出每个字符串在总字符串中的比例。由于题目中处理了大量的字符串，这里采用了二叉查找树(BST)来解决本题。

 

本题的具体过程是: 建立二叉查找树，向树中加入结点，其中每个结点有一个name，一个times(出现的次数),还有指向左孩子，右孩子的指针，向二叉查找树插入元素，如果没有该元素就加入，否则就对times加一，最后中序遍历，中序遍历的结果即是排好序的结果，同时输出占总数的百分比。

两种情况，直接从根结点插入（为空），从子结点插入（根结点不为空，子结点为空）

其实在插入时，先判断根结点是否为空
1、如果为空则直接生成一个新的结点，把数据插入（）
2、如果不为空，则判断它的左子树是否为空，如果为空，则直接生成一个，把数据插入，
                                                                        如果不为空，则递归插入
      

#include<stdio.h>
#include<malloc.h>
#include<iostream>
#include<string>
using namespace std;
const int NameLen=40;
long total;
typedef char ElemType;//假定关键字类型为整数
typedef struct node
{
    ElemType name[NameLen];
    int count;
    struct node * left,* right;
} BSTNode;


void insert(BSTNode *&root,ElemType * name)      //注意这里为什么用指针的引用
{
    if(root==NULL)               //如果该树为空,生成根结点count为1
    {
        root=(BSTNode*)malloc(sizeof(BSTNode));
        strcpy(root->name,name);
        root->count=1;
        root->left=NULL;
        root->right=NULL;
    }
    else
       {
        int cmp=strcmp(name,root->name);//name小于root为负
        if(cmp == 0) //1、如果已经存在，则直接返回
        {
            (root->count)++;
            return;
        }
        else if(cmp<0)  //2、传入key小于根结点的权值
             {
                if(root->left==NULL)   //root的左孩子为空，则创建一个结点作为root的左孩子
                {
                    BSTNode*p=(BSTNode *)malloc(sizeof(BSTNode));
                    strcpy(p->name,name);
                    p->count=1;
                    p->left=NULL;
                    p->right=NULL;
                    root->left=p;//直接挂在它的左子树
                }
                else
                    insert(root->left,name);  //递归插入到左子树中
            }
        else                    //3、key大于根结点的权值
        {
            if(root->right==NULL)   //root的右孩子为空，则创建一个结点作为root的右孩子
            {
                BSTNode*p=(BSTNode *)malloc(sizeof(BSTNode));
                strcpy(p->name,name);
                p->count=1;
                p->left=NULL;
                p->right=NULL;
                root->right=p;
            }
            else
                insert(root->right,name);  //递归插入到右子树中
        }
    }
}

void InorderTravel(BSTNode *root)
{
   if(root)
   {
    InorderTravel(root->left);
    printf("%s %.4lf\n",root->name,root->count*100.0/total);
    InorderTravel(root->right);
   }
}

int main()
{
 char name[NameLen];
 BSTNode * root=NULL;//root在输入第一次之后就不再是NULL了
 while(gets(name) && name[0]!='\0')//不输入直接一个Enter,那个这个字符串相当'\0';
 {
  insert(root,name);
  total++;
 }

 InorderTravel(root);

return 0;
}

Sample Input

Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow

以一空行结束
Sample Output

Ash 13.7931
Aspen 3.4483
Basswood 3.4483
Beech 3.4483
Black Walnut 3.4483
Cherry 3.4483
Cottonwood 3.4483
Cypress 3.4483
Gum 3.4483
Hackberry 3.4483
Hard Maple 3.4483
Hickory 3.4483
Pecan 3.4483
Poplan 3.4483
Red Alder 3.4483
Red Elm 3.4483
Red Oak 6.8966
Sassafras 3.4483
Soft Maple 3.4483
Sycamore 3.4483
White Oak 10.3448
Willow 3.4483
Yellow Birch 3.4483