动态查找树 || 键树的c++实现(双链树)

概念：

键树又称为数字查找树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字为数值，则结点中只包含一个数位；若关键字为单词，则结点中只包含一个字母字符。这种树会给某种类型关键字的表的查找带来方便。

举例：

{CAI,CAO,LI,LAN,CHA,CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,WU,CHEN}

我们先针对首字母将其分配：

• {CAI,CAO,CHA,CHANG,CHAO,CHEN}

• {WEN,WANG,WU}

• {ZHAO}

• {LI,LAN,LONG,LIU}

• {YUN,YANG}

然后对其中4个关键字大于1的子集再按照第二个字符不同进行分割，直到分割到每个子集包含一个关键字为止。如下图所示：

这种键数的查找速度和HashTable基本相当，但是内存用量却只有HashTable的一半不到。这个对于大容量的数据查找还是一种可行的方法。比如计费系统中的用户资料在计费过程中使用非常频繁，如果id作为关键字的键树的话，会大大提高查询速度。

c++实现：

• hpp:

//
//  DLTree.hpp
//  DLTree
//
//  Created by peiyu wang on 2019/3/26.
//  Copyright © 2019 peiyu wang. All rights reserved.
//

#ifndef DLTree_hpp
#define DLTree_hpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;

/* 类型定义 */
typedef enum {LEAF, BRANCH} NodeKind;

typedef string KeyType;
typedef char Record;
struct DLTNode
{
    NodeKind kind;
    char symbol; //存储关键字的第一个字符
    DLTNode *next; //指向兄弟结点
    union
    {
        Record *infoptr; //叶子结点指针
        DLTNode *first; //分支结点的孩子链指针
    }Ptr;
};

typedef DLTNode *DLTree;

/* 函数列表 */
// 创建树
int CreateDLTree(DLTree &DT);
// 查找返回指向key的指针
Record* SearchDLTree(DLTree DT, KeyType key);
// 将关键字key插入到双链树中
int InsertDLTree(DLTree &DT, KeyType key);
//输出双链树中关键字
void PrintKeys(DLTree DT);

#endif /* DLTree_hpp */

• cpp

//
//  DLTree.cpp
//  DLTree
//
//  Created by peiyu wang on 2019/3/26.
//  Copyright © 2019 peiyu wang. All rights reserved.
//

#include "DLTree.hpp"
#include <stack>
// 创建树
int CreateDLTree(DLTree &DT)
{
    DT = new DLTNode;
    DT->kind = BRANCH;
    DT->symbol = '\0';
    DT->next = NULL;
    DT->Ptr.first = NULL;
    KeyType tmp = "";
    int n = 0;
    cout << "请输入你想输入字符串个数：" << endl;
    cin >> n;
    cout << "请输入你想输入的字符串：" << endl;
    while (n--)
    {
        cin >> tmp;
        //cout << tmp.length();
        InsertDLTree(DT, tmp);
    }
    return 1;
}

// 查找返回指向key的指针
Record* SearchDLTree(DLTree DT, KeyType key)
{
    DLTree p = DT->Ptr.first;
    int i = 0;
    while (p && i < key.length())
    {
        while (p && p->symbol < key[i])
        {
            p = p->next;
        }
        if (p && p->symbol == key[i])
        {
            p = p->Ptr.first;
            i++;
        }
        else
        {
            p = NULL;
        }
    }
    if (p && p->kind == LEAF)
    {
        return p->Ptr.infoptr;
    }
    return NULL;
}

// 将关键字key插入到双链树中
int InsertDLTree(DLTree &DT, KeyType key)
{
    DLTree p = DT;
    DLTree q = DT->Ptr.first;
    DLTNode *tmp = NULL;
    int i = 0;
    while (i < key.length())
    {
        while (q && q->symbol < key[i])
        {
            p = q;
            q = q->next;
        }
        if (q && q->symbol == key[i])
        {
            p = q;
            q = q->Ptr.first;
            i++;
        }
        else
        {
            tmp = new DLTNode;
            tmp->kind = BRANCH;
            tmp->symbol = key[i];
            tmp->Ptr.first = NULL;
            tmp->next = NULL;
            if (p->Ptr.first == q)
            {
                p->Ptr.first = tmp;
                tmp->next = q;
            }
            else
            {
                p->next = tmp;
                tmp->next = q;
            }
            p = tmp;
            i++;
            while (i < key.length())
            {
                tmp = new DLTNode;
                tmp->kind = BRANCH;
                tmp->symbol = key[i];
                tmp->Ptr.first = NULL;
                tmp->next = NULL;
                p -> Ptr.first = tmp;
                p = p->Ptr.first;
                i++;
            }
            tmp = new DLTNode;
            tmp->kind = LEAF;
            tmp->symbol = '$';
            char *t_c = new char[key.length() + 1];
            tmp->Ptr.infoptr = strcpy(t_c, key.c_str());
            tmp->next = NULL;
            p->Ptr.first = tmp;
            p = p->Ptr.first;
            i++;
        }
    }
    
    return 1;
}

//输出双链树中关键字
void PrintKeys(DLTree DLT)
{
    if(DLT)
    {
        if(DLT->symbol=='\0')
            PrintKeys(DLT->Ptr.first);
        else if(DLT->symbol=='$')
            cout << DLT->Ptr.infoptr << endl;
        else
        {
            PrintKeys(DLT->Ptr.first);
        }
        PrintKeys(DLT->next);
    }
}

• main:

//
//  main.cpp
//  DLTree
//
//  Created by peiyu wang on 2019/3/26.
//  Copyright © 2019 peiyu wang. All rights reserved.
//

#include <iostream>
#include "DLTree.hpp"
int main(int argc, const char * argv[]) {
    DLTree DT = NULL;
    CreateDLTree(DT);
    PrintKeys(DT);
    char *k = NULL;
    k = SearchDLTree(DT, "li");
    if (k)
        cout << "OK" << endl;
    else
        cout << "No";
    return 0;
}