trinstar.cpp

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

// 用不同的类实现分支结点和叶结点trherit.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;
typedef ELEM* Keytype;

class CharTreeNode {                   // Node base class
public:
  char symbol;                     // symbol of character tree
  // isLeaf is a "pure" virtual function, which means CharTreeNode
  // contains no definition.  Each derived class must define isLeaf.
  virtual bool isLeaf() = 0;
};

class LeafNode : public CharTreeNode { // Leaf node subclass
private:
  Attr attribute;                          // attribute value
  CharTreeNode *right;
public:
  LeafNode(const Attr& val, CharTreeNode *rightsib = NULL) { // Constructor
     attribute = val; symbol = '*';
     right = rightsib;
  }
  bool isLeaf() { return TRUE; }     // Version for this subclass
  Attr& value() { return attribute; }      // Return node value
  CharTreeNode* rightchild() { return right; } // Right child
};

class IntlNode : public CharTreeNode { // Internal node subclass
private:
  CharTreeNode* left;                  // Left child
  CharTreeNode* right;                 // Right child
public:
  IntlNode(const char& sym, CharTreeNode* l=NULL, CharTreeNode* r=NULL)
    { symbol = sym; left = l; right = r; } // Constructor
  bool isLeaf() { return FALSE; }    // Version for this subclass
  CharTreeNode* leftchild() { return left; }   // Left child
  CharTreeNode* rightchild() { return right; } // Right child
  void setleft(CharTreeNode* leftval) { left = leftval; } // set left child
  void setright(CharTreeNode* rightval) { right = rightval; } // set right
  char value() { return symbol; }          // Value
};

void traverse(CharTreeNode *rt) {      // Preorder traversal
  if (rt == NULL) return;            // Nothing to visit
  if (rt->isLeaf()) {                 // Do leaf node
    cout << "Leaf: " << ((LeafNode *)rt)->value() << "\n";
    traverse(((LeafNode *)rt)->rightchild());
  }
  else {                             // Do internal node
    cout << "Internal: " << ((IntlNode *)rt)->value() << "\n";
    traverse(((IntlNode *)rt)->leftchild());
    traverse(((IntlNode *)rt)->rightchild());
  }
}

// 查找双链树中结点，rt为根，val为要找的关键码，返回值为空则查找失败，
// 否则为属性值。i为查找失败时所比较到的字符串下标位置，
// q,p之间是为比较失败，应该插入的位置。
// 查找普通的关键码，关键码需要以“*”结尾
Attr doubletree_search(CharTreeNode* rt, char* val, CharTreeNode* &q, 
                       CharTreeNode* &p, int &i) {
    int len; 
    i = 0;
    q = NULL; p = rt;   len = strlen(val);
    while (p != NULL && i < len-1)  {
        while (p != NULL && p->symbol < val[i])  { // 查找关键码的第i位
            q = p;
            p = ((IntlNode *)p)->rightchild( );
        }
        if (p == NULL || p->symbol > val[i])
            return NULL;
        q = p;
        p = ((IntlNode *)p)->leftchild( );		
        // 继续查找下一位
		i++;
    }
   if (p != NULL && p->isLeaf())  
        return(((LeafNode *)p)->value());   // i=len-1, p->symbol='*',存在此关键码
   else return NULL;   // 虽然查到最后一位，但没有此关键码，即没有“*”
}

// 插入值为'*'的结点到字符树中结点p之前，其中rt为根，q为p的前驱，
// attribute为要插入的属性。
Attr insertLeaf(CharTreeNode* &rt, CharTreeNode *q, CharTreeNode *p,
                Attr attribute) {
    CharTreeNode *s;
    Attr tempattr;

    tempattr = new char [strlen(attribute)];
    strcpy(tempattr, attribute);
    s = new LeafNode(tempattr, p);
    if (q == NULL)
       rt = s;
    else if (((IntlNode *)q)->leftchild() == p)
             ((IntlNode *)q)->setleft(s);
         else ((IntlNode *)q)->setright(s);
    return ((LeafNode *)s)->value();
}

// 插入双链树中结点，rt为根，val为要插入的关键码，
// 返回值为属性值(地址)。字符树是有序的。
// 插入普通的关键码，关键码需要以“*”结尾
Attr doubletree_insert(CharTreeNode* &rt, ELEM* val, Attr attribute) {
    int i = 0, len;   CharTreeNode *p, *q, *s;
    
    if (doubletree_search(rt, val, q, p, i) != NULL)
        return NULL;
    len = strlen(val);
    if (i == len-1)
        s = new LeafNode(attribute, p);
    else s = new IntlNode(val[i], NULL, p);
    if (rt == NULL || q == NULL) rt = s;
    else {
        if (((IntlNode *)q)->leftchild( ) == p)
 	       ((IntlNode *)q)->setleft(s);
        else ((IntlNode *)q)->setright(s);
    }
    for (int j=i+1; j<len-1; j++)  {
       p = new IntlNode(val[j], NULL, NULL);
       ((IntlNode *)s)->setleft(p); 
       s = ((IntlNode *)s)->leftchild();
    }
    if (i != len-1) return insertLeaf(rt, s, NULL, attribute); 
    else return ((LeafNode *)s)->value();
}

int main()
{
  CharTreeNode* root, *q, *p;
  char *str, *attr;
  int i;

  root = NULL;
  str = "hero*";   attr = "hero";
  doubletree_insert(root, str, attr);
  str = "aeo*";    attr = "aeo";
  doubletree_insert(root, str, attr);
  str = "here*";   attr = "here";
  doubletree_insert(root, str, attr);
  str = "heri*";   attr = "heri";
  doubletree_insert(root, str, attr);
  str = "her*";    attr = "her";
  doubletree_insert(root, str, attr);
  traverse(root);
  str = "he*";
  cout << str;
  if (doubletree_search(root, str, q, p, i) != NULL)
	  cout << "OK\n";
  else cout << "NO\n";
  return(0);
}