trinhert.cpp

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

// 用不同的类实现分支结点和叶结点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* Attr;
typedef char* 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, CharTreeNode* r)
    { 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为要找的关键码，返回值为空则查找失败，
// 否则为属性值。
// 查找普通的关键码，关键码并不需要以“*”结尾
Attr doubletree_search(CharTreeNode* rt, char* val) {
    int i = 0, len;    CharTreeNode *p;
    p = rt;   len = strlen(val);
    while (p != NULL && i < len)  {
        while (p != NULL && p->symbol < val[i]) // 查找关键码的第i位
            p = ((IntlNode *)p)->rightchild( );
        if (p == NULL || p->symbol > val[i])
            return NULL;
     //   if (i < len - 1)   // p->symbol == val[i]
        p = ((IntlNode *)p)->leftchild( );
        i++;     // 继续查找下一位
    }
    if (p == NULL)
        return NULL;
    else if (p->isLeaf())
            return(((LeafNode *)p)->value());   // 存在此关键码
         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( );
}

// 插入val从i开始的子串到字符树中结点p之前，其中rt为根，q为p的前驱，
// attribute为要插入的属性。
Attr insertSubtree(CharTreeNode* &rt, CharTreeNode *q, CharTreeNode *p, char *val, 
                int i, Attr attribute) {
    CharTreeNode *s;
    int len;
    len = strlen(val);
    s = new IntlNode(val[i], NULL, p);
    if (q == NULL) rt = s;
    else {
        if (((IntlNode *)q)->leftchild() == p)
	       ((IntlNode *)q)->setleft(s);
        else ((IntlNode *)q)->setright(s);
//        ((IntlNode *)s)->setright(p);
    }
    for (int j=i+1; j<len; j++)  {
       p = new IntlNode(val[j], NULL, NULL);
       ((IntlNode *)s)->setleft(p);
       s = ((IntlNode *)s)->leftchild();
    }
    return insertLeaf(rt, s, NULL, attribute); 
}

// 插入双链树中结点，rt为根，val为要插入的关键码，
// 返回值为属性值(地址)。字符树是有序的。
// 插入普通的关键码，关键码并不需要以“*”结尾
Attr doubletree_insert(CharTreeNode* &rt, char* val, Attr attribute) {
    int i = 0, len;   CharTreeNode *p, *q;
    p = rt;  q = NULL;
    len = strlen(val);
    if (rt == NULL) return insertSubtree(rt, q, p, val, i, attribute);
    while (p != NULL && i < len)  {
        while (p != NULL && p->symbol < val[i]) { // 查找关键码的第i位
            q = p;
            p = ((IntlNode *)p)->rightchild( );
        }
        if (p != NULL && p->symbol == val[i])  {            
            q = p;   p = ((IntlNode *)p)->leftchild( );
            if (i < len-1)    i++;     // 继续查找下一位
            else {
                if (p->isLeaf())
                    return ((LeafNode *)p)->value();  // 不需要插入
                else  return insertLeaf(rt, q, p, attribute); 
            }
        }   // of if (p != NULL && p->symbol == val[i])
        else return insertSubtree(rt, q, p, val, i, attribute);
    }  // of while (p != NULL && i < len)
    return NULL;
}

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

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