在一个嵌入式项目中，要存储100万条电话号码，同时电话号码的长度最长为11位，为了提高查找的速度，笔者采用11叉树的方式进行存储电话号码，并且支持电话号码的包含关系，所谓包含关系，即要支持1234, 12345这种包含关系。
#pragma once
#include <string>
#include <stack>
using namespace std;
#define MAX_WAY 11
#define HAS_CHILDREN_NO 0x01
#define HAS_CHILDREN_YES 0x02
#define HASNO_CHILDREN_NO 0x03
#define HASNO_CHILDREN_YES 0x04
class Threewaytree
{
public:
Threewaytree(void);
~Threewaytree(void);
private:
Threewaytree* m_ptree[MAX_WAY];
unsigned char m_symbol;
static int m_nodecount;
public:
void output(int indent = -1);
bool insertphonenumber(string phonenumber);
bool deletephonenumber(string phonenumber);
void generatephonelist(string& prefix);
void getphonecount(int& count);
bool findphonenumber(string phonenumber);
private:
void destroy();
int wetherornotdelete();
bool islegalphonenumber(string phonenumber);
};
#include "Threewaytree.h"
#include "stdio.h"
int Threewaytree::m_nodecount = 0;
Threewaytree::Threewaytree(void)
{
//printf("new %08x\n", this);
m_nodecount++;
m_symbol = 0x00;
for(int i = 0; i < MAX_WAY; i++)
{
m_ptree[i] = NULL;
}
}
Threewaytree::~Threewaytree(void)
{
printf("delete %08x\n", this);
m_nodecount--;
destroy();
}
void Threewaytree::getphonecount(int& count)
{
for(int i = 0; i < MAX_WAY; i++)
{
if (m_ptree[i] != NULL)
{
if (m_ptree[i]->m_symbol == 1)
{
count++;
}
m_ptree[i]->getphonecount(count);
}
}
}
void Threewaytree::generatephonelist(string& prefix)
{
for(int i = 0; i < MAX_WAY; i++)
{
string temp = prefix;
if (m_ptree[i] != NULL)
{
temp += i + 48;
if (m_ptree[i]->m_symbol == 1)
{
printf("%s\n", temp.c_str());
}
m_ptree[i]->generatephonelist(temp);
}
}
}
void Threewaytree::output(int indent)
{
indent++;
for(int i = 0; i < MAX_WAY; i++)
{
if (m_ptree[i] != NULL)
{
for(int j = 0; j < indent; j++)
{
printf("|--");
}
printf("%d [0x%08x] [%d] \n", i, m_ptree[i], m_ptree[i]->m_symbol);
m_ptree[i]->output(indent);
}
}
}
bool Threewaytree::insertphonenumber(string phonenumber)
{
bool result = false;
if (!islegalphonenumber(phonenumber)) return false;
const char *pchar = phonenumber.c_str();
int index = 0;
int length = phonenumber.length();
Threewaytree *parenttreenode = this;
int order = 0;
while(index < length)
{
order = *pchar - 48;
if (parenttreenode->m_ptree[order] == NULL)
{
Threewaytree *treenode = new Threewaytree;
parenttreenode->m_ptree[order] = treenode;
parenttreenode = treenode;
}
else
{
parenttreenode = parenttreenode->m_ptree[order];
}
index++;
pchar++;
}
if (parenttreenode->m_symbol == 1)
{
return result;
}
else if(parenttreenode->m_symbol == 0)
{
result = true;
parenttreenode->m_symbol = 1;
}
return result;
}
bool Threewaytree::islegalphonenumber(string phonenumber)
{
bool result = true;
int length = phonenumber.length();
if (length > MAX_WAY)
{
result = false;
return result;
}
const char *pchar = phonenumber.c_str();
int index = 0;
while(index < length)
{
if ((*pchar) < '0' || (*pchar > '9'))
{
result = false;
break;
}
index++;
pchar++;
}
return result;
}
int Threewaytree::wetherornotdelete()
{
int result = 0x00;
bool haschildren = false;
for(int i = 0; i < MAX_WAY; i++)
{
if (m_ptree[i] != NULL)
{
haschildren = true;
break;
}
}
if(haschildren == true && m_symbol == 1)
{
result = HAS_CHILDREN_YES;
}
else if(haschildren == false && m_symbol == 1)
{
result = HASNO_CHILDREN_YES;
}
else if(haschildren == true && m_symbol == 0)
{
result = HAS_CHILDREN_NO;
}
else if(haschildren == false && m_symbol == 0 )
{
result = HASNO_CHILDREN_NO;
}
return result;
}
bool Threewaytree::findphonenumber(string phonenumber)
{
bool result = false;
if (!islegalphonenumber(phonenumber)) return result;
const char *pchar = phonenumber.c_str();
int length = phonenumber.length();
int index = 0;
Threewaytree *node = this;
while(index < length)
{
int order = *pchar - 48;
//不存在号码退出, 号码还没有遍历完，但指针已经到头了。
if (node->m_ptree[order] == NULL) return result;
//为下次循环准备
node = node->m_ptree[order];
pchar++;
index++;
}
if (node->m_symbol == 1)
{
result = true;
}
return result;
}
bool Threewaytree::deletephonenumber(string phonenumber)
{
typedef struct
{
int index;
Threewaytree* ptree;
}ELEM;
typedef stack<ELEM> STACK;
STACK mystack;
bool result = false;
if (!islegalphonenumber(phonenumber)) return result;
const char *pchar = phonenumber.c_str();
int length = phonenumber.length();
int index = 0;
Threewaytree *node = this;
//都元素入栈
ELEM elem;
elem.index = 0xFFFFFFFF;
elem.ptree = node;
mystack.push(elem);
while(index < length)
{
int order = *pchar - 48;
//不存在号码退出, 号码还没有遍历完，但指针已经到头了。
if (node->m_ptree[order] == NULL) return result;
//普通元素开始入栈
ELEM elem;
elem.index = order;
elem.ptree = node->m_ptree[order];
mystack.push(elem);
//为下次循环准备
node = node->m_ptree[order];
pchar++;
index++;
}
printf("----------------------------- stack size = %d ---------------------------------\n", mystack.size());
for(int i= 0; i < length; i++)
{
ELEM elem1 = mystack.top();
mystack.pop();
int result = elem1.ptree->wetherornotdelete();
printf("pop order=%d elem=%08x symbol=%d result=%d\n", elem1.index, elem1.ptree, elem1.ptree->m_symbol, result);
if (result == HAS_CHILDREN_NO)
{
break;
}
else if(result == HAS_CHILDREN_YES)
{
if (i == 0)
{
elem1.ptree->m_symbol = 0;
printf("set symbol = 0\n");
break;
}
}
else if(result == HASNO_CHILDREN_NO)
{
delete elem1.ptree;
elem1.ptree = NULL;
ELEM elem2 = mystack.top();
elem2.ptree->m_ptree[elem1.index] = NULL;
}
else if(result == HASNO_CHILDREN_YES)
{
if (i== 0)
{
delete elem1.ptree;
elem1.ptree = NULL;
ELEM elem2 = mystack.top();
elem2.ptree->m_ptree[elem1.index] = NULL;
}
else
{
break;
}
}
}
result = true;
printf("------------------------------------------------------------------------------\n");
return result;
}
void Threewaytree::destroy()
{
for(int i = 0; i < MAX_WAY; i++)
{
if (m_ptree[i] != NULL)
{
m_ptree[i]->destroy();
delete m_ptree[i];
m_ptree[i] = NULL;
}
}
}
主函数测试：
// Tree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "Threewaytree.h"
#include "math.h"
int _tmain(int argc, _TCHAR* argv[])
{
Threewaytree tree;
tree.insertphonenumber("123");
tree.insertphonenumber("123");
tree.insertphonenumber("12");
tree.insertphonenumber("1234");
tree.insertphonenumber("123567");
tree.insertphonenumber("125");
tree.insertphonenumber("18");
tree.insertphonenumber("2");
tree.output();
string phonelist = "";
tree.generatephonelist(phonelist);
bool result = tree.deletephonenumber("2");
if (result)
{
printf("delete true\n");
}
else
{
printf("delete false\n");
}
tree.generatephonelist(phonelist);
tree.output();
/*tree.output();
printf("-------------- phone number count ----------------\n");
int count = 0;
tree.getphonecount(count);
printf("count=%d\n", count);
printf("-------------- phone number list ----------------\n");
string phonelist = "";
tree.generatephonelist(phonelist);
printf("-------------- find phone number ----------------\n");
string phonenumber = "18";
if (tree.findphonenumber(phonenumber))
{
printf("find\n");
}
else
{
printf("not find\n");
}*/
getchar();
return 0;
}