trunion.cpp

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

// 使用联合实现不同的分支结点和叶结点，trunion.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;

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

class CharTreeNode {       // Generic node class
public:
  Nodetype mytype;       // Stores the type for this particular node
  char symbol;      // Internal node value
  union {
    struct {             // Structure for internal node
      CharTreeNode* left;  // Left child
      CharTreeNode* right; // Right sibling
    } intl;
    struct {
      Attr attribute;         // Leaves just store a value
      CharTreeNode* right;      // leaf node's brother
    } leaf;
  };
  // Constructor: leaf
  CharTreeNode(const Attr& val, CharTreeNode* rightsib = NULL) {
      mytype = leafNode; symbol = '*'; 
      leaf.attribute = val;
      leaf.right = rightsib;
  }
  // Constructor: Internal
  CharTreeNode(const char& sym, CharTreeNode* l=NULL, CharTreeNode* r=NULL) {
    mytype = internal; symbol = sym; intl.left = l; intl.right = r;
  }
  bool isLeaf() { return mytype == leafNode; }
  CharTreeNode* leftchild() { return intl.left; }
  CharTreeNode* rightchild() { return intl.right; }
};

void traverse(CharTreeNode* rt) { // Preorder traversal
  if (rt == NULL) return;
  if (rt->isLeaf()) {
    cout << "Leaf: " << rt->leaf.attribute << "\n";
    traverse(rt->leaf.right);
  }
  else {
    cout << "Internal: " << rt->symbol << "\n";
    traverse(rt->leftchild());
    traverse(rt->rightchild());
  }
}

// 查找双链树中结点，rt为根，val为要找的关键码，返回值为空则查找失败，
// 否则为属性值。
// 查找普通的关键码，关键码并不需要以“*”结尾
Attr doubletree_search2(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 = p->rightchild( );
        if (p == NULL || p->symbol > val[i])
            return NULL;
     //   if (i < len - 1)   // p->symbol == val[i]
            p = p->leftchild( );
        i++;     // 继续查找下一位
    }
    if (p == NULL)
        return NULL;
    else if (p->isLeaf())
            return(p->leaf.attribute);   // 存在此关键码
         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 CharTreeNode(tempattr, p);
    if (q == NULL)
       rt = s;
    else if (q->intl.left == p)
             q->intl.left = s;
         else q->intl.right = s;
    return s->leaf.attribute;
}

// 插入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 CharTreeNode(val[i], NULL, p);
    if (q == NULL) rt = s;  // (rt == NULL) is OK
    else {
       if (q->intl.left == p)
	 q->intl.left = s;
       else q->intl.right = s;
       s->intl.right = p;
    }
    for (int j=i+1; j<len; j++)  {
       s->intl.left = new CharTreeNode(val[j], NULL, NULL);
       s = s->intl.left;
    }
    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 = p->rightchild( );
        }
        if (p != NULL && p->symbol == val[i])  {            
            q = p;   p = p->leftchild( );
            if (i < len-1)    i++;     // 继续查找下一位
            else {
                if (p->isLeaf())
                    return p->leaf.attribute;  // 不需要插入
                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 = "aeo";
  cout << str;
  if (doubletree_search2(root, str) != NULL)
	  cout << "OK\n";
  else cout << "NO\n";
  return(0);
}