C++中二叉树如何实现词频分析功能

小编给大家分享一下C++中二叉树如何实现词频分析功能，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

创新互联自2013年创立以来，是专业互联网技术服务公司，拥有项目成都网站设计、做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元衡山做网站,已为上家服务,为衡山各地企业和个人服务,联系电话:18980820575

通过二叉树存单词，并且对总共的单词数量进行计数，二叉树自适应的将出现频率高的单词往上移动以减少二叉树的搜索时间。
代码如下

/***********************genSplay.h***********************/
#ifndef _GENSPLAY_H_
#define _GENSPLAY_H_

#include 
using namespace std;

//树节点
template
class SplayingNode
{
public:
  T info;
  SplayingNode *left, *right, *parent;  //节点指针
  SplayingNode(){
    left = right = parent = 0;
  }
  SplayingNode(const T &el, SplayingNode *l = 0,
         SplayingNode *r = 0, SplayingNode *p = 0)
         :info(el), left(l), right(r), parent(p){ }
};
//二叉树
template
class SplayTree
{
protected:
  SplayingNode *root;
  void rotateR(SplayingNode *);  //向右旋转
  void rotateL(SplayingNode *);  //向左旋转
  void continueRotation(SplayingNode *gr, SplayingNode *par,
             SplayingNode *ch, SplayingNode *desc); //重新定义父节点指针
  void semisplay(SplayingNode *); //更改树结构，将权值大的向上移动
  void inorder(SplayingNode *);  //中序遍历
  void virtual visit(SplayingNode *){ } //虚函数
public:
  SplayTree(){
    root = 0;
  }
  void inorder(){
    inorder(root);
  }
  T *search(const T &);
  void insert(const T &);
};

template
void SplayTree::continueRotation(SplayingNode *gr, SplayingNode *par,
    SplayingNode *ch, SplayingNode *desc)
{
  if(gr != 0){
    if(gr->right == ch->parent)
      gr->right = ch;
    else
      gr->left = ch;
  }
  else
    root = ch;
  if(desc != 0)
    desc->parent = par;
  par->parent = ch;
  ch->parent = gr;
}

template
void SplayTree::rotateR(SplayingNode *p)
{
  p->parent->left = p->right;
  p->right = p->parent;
  continueRotation(p->parent->parent, p->right, p, p->right->left);
}

template
void SplayTree::rotateL(SplayingNode *p)
{
  p->parent->right = p->left;
  p->left = p->parent;
  continueRotation(p->parent->parent, p->left, p, p->left->right);
}
template
void SplayTree::semisplay(SplayingNode *p)
{
  while(p != root){
    if(p->parent->parent == NULL){
      if(p->parent->left == p)
        rotateR(p);
      else
        rotateL(p);
    }
    else if(p->parent->left == p){
      if(p->parent->parent->left == p->parent){
        rotateR(p->parent);
        p = p->parent;
      }
      else{
        rotateR(p);
        rotateL(p);
      }
    }
    else{
      if(p->parent->parent->right == p->parent){
        rotateL(p->parent);
        p = p->parent;
      }
      else{
        rotateL(p);
        rotateR(p);
      }
    }
    if(root == NULL)
      root = p;
  }
}

template
T *SplayTree::search(const T &el)
{
  SplayingNode *p = root;
  while(p != NULL){
    if(p->info == el){
      semisplay(p);
      return &p->info;
    }
    else if(el < p->info)
      p = p->left;
    else
      p = p->right;
  }
  return 0;
}

template
void SplayTree::insert(const T &el)
{
  SplayingNode *p = root, *prev = NULL, *newNode;
  while(p != 0){
    prev = p;
    if(el < p->info)
      p = p->left;
    else
      p = p->right;
  }
  if((newNode = new SplayingNode(el, 0, 0, prev)) == 0){
    cerr << "no room for new node.\n";
    exit(1);
  }
  if(root == 0)
    root = newNode;
  else if(el < prev->info)
    prev->left = newNode;
  else
    prev->right = newNode;
}

template
void SplayTree::inorder(SplayingNode *p)
{
  if(p != 0){
    inorder(p->left);
    visit(p);
    inorder(p->right);
  }
}

#endif // _GENSPLAY_H_

/***********************Splay.cpp***********************/
#include 
#include 
#include 
#include 
#include  //exit(0)
#include "genSplay.h"
using namespace std;

//用作计数对象的类
class Word
{
private:
  char *word;
  int freq;
  friend class WordSplay;
  //friend ostream & operator<<(ostream &out, const Word &wd);
public:
  Word(){
    freq = 1;
  }
  int operator==(const Word &ir) const{
    return strcmp(word, ir.word) == 0;
  }
  int operator<(const Word &ir) const{
    return strcmp(word, ir.word) < 0;
  }
};

class WordSplay : public SplayTree
{
private:
  int differentWords, wordCnt;
  void visit(SplayingNode *);
public:
  WordSplay(){
    differentWords = wordCnt = 0;
  }
  void run(ifstream &, char *);
};

void WordSplay::visit(SplayingNode *p)
{
  differentWords++;
  wordCnt += p->info.freq;
}

void WordSplay::run(ifstream &fin, char *filename)
{
  char ch = ' ', i;
  char s[100];
  Word rec;
  while(!fin.eof()){
    while(1){
      if(!fin.eof() && !isalpha(ch))
        fin.get(ch);
      else
        break;
    }
    if(fin.eof())
      break;
    for(i = 0; !fin.eof() && isalpha(ch); i++){
      s[i] = toupper(ch);
      fin.get(ch);
    }
    s[i] = '\0';
    if(!(rec.word = new char[strlen(s) + 1])){
      cerr << "no room for new words.\n";
      exit(1);
    }
    strcpy(rec.word, s);
    Word *p = search(rec);
    if(p == 0)
      insert(rec);
    else
      p->freq++;
  }
  inorder();
  cout << "\n\nFile " << filename
     << " contains " << wordCnt << " words among which "
     << differentWords << " are different.\n";
}

int main()
{
  char Filename[80];
  WordSplay SplayTree;
  cout << "enter a filename: ";
  cin >> Filename;
  ifstream fin(Filename);
  if(fin.fail()){
    cerr << "cannot open " << Filename << endl;
    return 1;
  }
  SplayTree.run(fin, Filename);
  fin.close();

  return 0;
}

以上是“C++中二叉树如何实现词频分析功能”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！

网站栏目：C++中二叉树如何实现词频分析功能
链接地址：http://6mz.cn/article/jcphee.html