[置頂] 看數據結構寫代碼（60 ） 鍵樹的多重鏈表表示（Trie樹）
來源：程序員人生 發布時間：2015-07-29 07:42:17 閱讀次數：4024次
trie樹，是用 樹的 多重鏈表來表示 樹的。每一個節點 有 d 個指針域。若從鍵樹中的某個節點到葉子節點的路徑上每一個節點都只有1個孩子，則可以把 路徑上的所有節點緊縮成1個葉子節點，且在葉子節點中 存儲 關鍵字 和 根關鍵字相干的信息。
當節點的度 比較大時，選擇 Trie樹，要比 雙鏈表樹更加適合。
tire樹的 數據 緊縮 是 挺與眾不同的。
下面 給出 具體的 代碼：
源代碼工程文件網盤地址：http://pan.baidu.com/s/1cyTg6
// TrieTree.cpp : 定義控制臺利用程序的入口點。
//
#include "stdafx.h"
#include <cstdlib>
#include <cstring>
#include "stack.h"
#define BRANCH_MAX_SIZE 27//分支節點最大指針數
#define MAX_SIZE 16
#define LEAF_END_CHAR '$'
enum E_Kind{
E_Kind_Branch,
E_Kind_Leaf,
};
struct KeyType{
char k [MAX_SIZE];
int len;
};
void initKey(KeyType * kt,char *k){
kt->len = strlen(k);
strncpy(kt->k,k,kt->len+1);
}
typedef struct TrieNode{
E_Kind kind;
union {
struct {
TrieNode * ptr[BRANCH_MAX_SIZE];
int num;
}branch;
struct {
char record[MAX_SIZE];
}leaf;
};
}* TrieTree;
TrieNode * makeNode(E_Kind kind){
TrieNode * node = (TrieNode*) malloc(sizeof(TrieNode));
node->kind = kind;
if (kind == E_Kind_Branch){
for (int i = 0; i < BRANCH_MAX_SIZE; i++){
node->branch.ptr[i] = NULL;
}
node->branch.num = 0;
}
return node;
}
TrieNode * makeLeafNode(char * key){
TrieNode * leaf = makeNode(E_Kind_Leaf);
strncpy(leaf->leaf.record,key,strlen(key)+1);
return leaf;
}
void initTree(TrieTree* t){
*t = NULL;
}
void destoryTree(TrieTree * t){
if (*t != NULL)
{
TrieTree p = *t;
if (p->kind == E_Kind_Branch){
for (int i = 0; i < BRANCH_MAX_SIZE; i++){
if (p->branch.ptr[i] != NULL){
destoryTree(&p->branch.ptr[i]);
}
}
}
free(*t);
*t = NULL;
}
}
int getIndex(char * k,int i){
KeyType kt;
initKey(&kt,k);
int index = 0;
if(i != kt.len){
index = kt.k[i] - 'a' + 1;
}
return index;
}
struct Result{
bool isFind;
TrieNode * t;
int index;
};
//找到了返回 保存記錄的 葉子節點；
//否則返回插入位置
Result search(TrieTree t,char * k){
KeyType kt;
initKey(&kt,k);
Result r;
for (int i = 0; t && t->kind == E_Kind_Branch && i<= kt.len; i++){
int index = getIndex(k,i);
r.t = t;
r.index = i;
t = t->branch.ptr[index];
}
if (t && t->kind == E_Kind_Leaf && strcmp(t->leaf.record,k) == 0){//節點可以緊縮，所以沒有 == kt.len的條件.
r.isFind = true;
r.t = t;
}
else{
r.isFind = false;
}
return r;
}
void insertTree(TrieTree *t,char * key){
if (*t == NULL){
*t = makeNode(E_Kind_Branch);
}
Result r = search(*t,key);
if (r.isFind == false){
int index = getIndex(key,r.index);
TrieTree p = r.t->branch.ptr[index];
TrieNode * leaf = makeLeafNode(key);
if (p == NULL){
r.t->branch.ptr[index] = leaf;
r.t->branch.num ++;
}
else{
TrieTree q = r.t;
int times = r.index+1;
int len = strlen(key);
while (times <= len){//為字符 相同的節點 建立 分支
int index1 = getIndex(key,times);
int index2= getIndex(p->leaf.record,times);
TrieNode * branch = makeNode(E_Kind_Branch);
q->branch.ptr[index] = branch;
if (index1 != index2){
branch->branch.ptr[index1] = leaf;
branch->branch.ptr[index2] = p;
branch->branch.num += 2;
break;
}
else{
branch->branch.num = 1;
q = branch;
index = index1;
times++;
}
}
}
}
}
void deleteTrie(TrieTree * t,char * k){
if(*t != NULL){
linkStack stack;
stackInit(&stack);
stackPush(&stack,*t);
KeyType kt;
initKey(&kt,k);
TrieTree p = *t;
int i = 0;
for (; p && p->kind == E_Kind_Branch && i <= kt.len; i++){
int index = getIndex(k,i);
stackPush(&stack,p);
p = p->branch.ptr[index];
}
if (p && p->kind == E_Kind_Leaf && strcmp(p->leaf.record,k) == 0){
TrieTree brotherNode = NULL;
while (!stackEmpty(stack)){
TrieTree f;
stackPop(&stack,&f);
free(p);
int index = getIndex(k,i);
f->branch.ptr[i] = NULL;
f->branch.num --;
if (f->branch.num == 0){
p = f;
i--;
if (f == *t){//空樹了..
free(*t);
*t = NULL;
}
}
else{
break;
}
}
}
else{//沒找到
return;
}
}
}
static char testArray[][MAX_SIZE] = {//18 個
"cao","cai","chang","chao","cha","chen",//6
"wen","wang","wu",//3
"zhao",//1
"li","lan","long","liu",//4
"yun","yang",//2
"zha","l",
};
int _tmain(int argc, _TCHAR* argv[])
{
TrieTree root;
initTree(&root);
for (int i = 0; i < 18; i++){
insertTree(&root,testArray[i]);
}
for (int i = 0; i < 18; i++){
char * s = testArray[i];
Result r = search(root,s);
if (r.isFind){
printf("查找%s ,結果為：%s
",s,r.t->leaf.record);
}
else{
printf("查找%s ,未找到
",s);
}
}
destoryTree(&root);
return 0;
}
運行截圖：
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
