// test.cpp : Defines the entry point for the console application.
// #include \"stdafx.h\"
#include <iostream>
#include <queue>
using namespace std; /*define the movement direction*/
#define CHILD 1
#define SIBLING 2
#define NOMOVE 3 /*
*keyword tree node
*we use a structure left child-right sibling
*to store the tree’s nodes
*/
class knode
{
public:
knode()
{
c=0;
child=NULL;
sibling=NULL;
}
knode(int cc,knode* pc, knode* ps)
{
c=cc;
child=pc;
sibling=ps;
}
char c;
knode * child;
knode * sibling;
}; /*
*insert pattern to keyword tree
*root is keyword tree’s root node
*str is the string inserted to the tree
*/
void insertKTree(knode* const root,char* str)
{
knode* troot=root;
knode* tproot=root; /*save the previous node when move in the tree*/
troot=root->child;
int moveDir=NOMOVE; /*
find the matched portion of substring in str as soon as possiable,
meanwhile,move the pointer str.
*/
while(troot != NULL)
{
if(troot->c == *str) [Page]
{
str++;
tproot=troot;
troot=troot->child;
moveDir=CHILD;/*move to child*/
}
else
{
tproot=troot;
troot=troot->sibling;
moveDir=SIBLING; /*move to sibling*/
}
} /*ready to insert the rest string pointed to by str into the tree*/
switch(moveDir)
{
case NOMOVE: /*tree only has a node(root node)*/
case CHILD: /*insert node as child*/
while(*str != ’\\0’)
{
tproot->child=new knode(*str,NULL,NULL);
tproot=tproot->child; | 