键树的c++代码实现.txt

键树的c++代码实现,主要是演示一下算法

// 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)
        {
            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;
            str++;
        }
        break;
    case SIBLING: /*insert node as sibling first,and then insert node as child for all rest characters*/
        tproot->sibling=new knode(*str,NULL,NULL);
        str++;
        tproot=tproot->sibling;
        while(*str != '\0')
        {
            tproot->child=new knode(*str,NULL,NULL);
            tproot=tproot->child;
            str++;
        }

        break;
    default: /*the branch is not reachable*/
        break;
    }
}

/*
*print all nodes of the tree in level order
*/
void printKTree(knode * root)
{
    queue<knode> Q;

    knode tnode;
    tnode=*root;
   
    Q.push(tnode);
    cout<<" char is "<<tnode.c;

    /*visit tree in level order*/
    while(!Q.empty())
    {
        /*retrive the first node from queue*/
        tnode=Q.front();
        cout<<" char is "<<tnode.c;
        Q.pop();   
       
        /*push all tnode's child into queue*/
        if(tnode.child !=NULL)
        {
            Q.push(*(tnode.child));/*add first child*/
            tnode=*(tnode.child);

            /*add the rest child*/
            while(tnode.sibling != NULL)
            {
            Q.push(*(tnode.sibling));           
            tnode=*(tnode.sibling);               
            }   
        }
               
        cout<<endl;
    }
}


int main(int argc, char* argv[])
{
    knode root;
    root.c=-1;
    root.child=NULL;
    root.sibling=NULL;

    char * str1="abc";
    char * str2="abd";
    char * str3="ac";
    char * str4="mn";
    insertKTree(&root,str1);
    insertKTree(&root,str2);
    insertKTree(&root,str3);
    insertKTree(&root,str4);
    printKTree(&root);

    printf("Hello World!\n");
    return 0;
}