trie.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 154 行

// 使用联合实现不同的分支结点和叶结点，union.cpp
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include "..\include\book.h"
typedef char ELEM;

typedef ELEM* Attr;
const base = 26;
const start = 'a';

enum Nodetype {leafnode, internal};  // Enumerate possible node types

class TrieNode {       // Generic node class
public:
  Nodetype mytype;       // Stores the type for this particular node
  char symbol;      // Internal node value
  union {
       struct {
          TrieNode* trieptr[base+1];    // Structure for internal node
       } intl;
       struct {
           ELEM *data;
           Attr attribute;         // Leaves just store a value
       } leaf;
  };
  TrieNode(const Attr val) // Constructor: leaf
    { mytype = leafnode;  leaf.attribute = val; }
  // Constructor: Internal
  TrieNode(void) {
      mytype = internal;
      for (int i=0; i<base+1; i++)
          intl.trieptr[i] = NULL;
  }
  bool isLeaf() { return mytype == leafnode; }
};

void traverse(TrieNode* rt) { // Preorder traversal
  if (rt == NULL) return;
  if (rt->isLeaf()) cout << "Leaf: " << rt->leaf.attribute << "\n";
  else {
    // cout << "Internal: " << rt->symbol << "\n";
	for (int i=0; i<base+1; i++)
       traverse(rt->intl.trieptr[i]);
  }
}


// 插入值为'*'的结点到字符树，其中rt为根，q为前驱
// attribute为要插入的属性。
Attr insertLeaf(TrieNode *q, Attr attribute) {
    TrieNode *s;
    s = new TrieNode(attribute);  
    q->intl.trieptr[0] = s;
    s->leaf.attribute = new char [strlen(attribute)];
    strcpy(s->leaf.attribute, attribute);
    return s->leaf.attribute;
}

// 插入val从k开始的子串到字符树中, q为前驱(q为空是表示新插入当根)，
// attribute为要插入的属性。
Attr insertSubtree(TrieNode* &q, ELEM *val, 
                int k, Attr attribute) {
    TrieNode *s;
    int len;
    len = strlen(val);
    s = new TrieNode;
    if (q == NULL)
        q = s;
    else q->intl.trieptr[val[k]-start+1] = s;  
    for (int j=k+1; j<len; j++)  {
       s->intl.trieptr[val[j]-start+1] = new TrieNode;
       s = s->intl.trieptr[val[j]-start+1];
    }
    return insertLeaf(s, attribute); 
}

// 查找双链树中结点，rt为根，val为要找的关键码，返回值为空则查找失败，
// 否则为属性值。
// 查找普通的关键码，关键码并不需要以“*”结尾
Attr trietree_insert(TrieNode *rt, char *val, Attr attribute) {
    int i = 0, len;    TrieNode *p, *q;
    p = rt;  q = NULL;  len = strlen(val);
    while (p != NULL && i < len)  {
        q = p;
        p = p->intl.trieptr[val[i]-start+1];  // 查找关键码的第i位
        i++;
    }
    if (p != NULL)  { 
        q = p;
        p = p->intl.trieptr[0];
        if (p == NULL)
            insertLeaf(q, attribute);
        else  return p->leaf.attribute;  // 存在此关键码
    }
    else return insertSubtree(q, val, i-1, attribute);
	return NULL;
}

// 查找双链树中结点，rt为根，val为要找的关键码，返回值为空则查找失败，
// 否则为属性值。
// 查找普通的关键码，关键码并不需要以“*”结尾
Attr trietree_search(TrieNode* rt, char* val) {
    int i = 0, len;    TrieNode *p, *q;
    p = rt;   len = strlen(val);
    while (p != NULL && i < len)  {
        p = p->intl.trieptr[val[i]-start+1];  // 查找关键码的第i位
        i++;
    }
    if (p != NULL)  { 
        q = p;
        p = p->intl.trieptr[0];
        if (p == NULL)
            return NULL;
        else  return p->leaf.attribute;  // 存在此关键码
    }
    else return NULL;
}

int main()
{
  TrieNode* root;
  char *str;

  str = "hero";    root = new TrieNode;
  trietree_insert(root, str, str);
  str = "aeo";
  trietree_insert(root, str, str);
  str = "here";
  trietree_insert(root, str, str);
  str = "her";
  trietree_insert(root, str, str);
  str = "heri";
  trietree_insert(root, str, str);
  /*
  //while (!EOF)  {
  cin >> str;
  while (str[0] != 'X') {
      trietree_insert(root, str, str);
      cin >> str;
  }
  */
  traverse(root);
  str = "herh";
  cout << str;
  if (trietree_search(root, str) != NULL)
	  cout << "OK\n";
  else cout << "NO\n";
  return(0);
}