一 概述
1
2
3
4
| 1.键树的存储结构
2.双链树构成
3.双链树图示
4.示例代码
|
二 键树的存储结构
1
2
3
| 键树的存储结构有两种：
一种是通过使用树的孩子兄弟表示法来表示键树，即双链树；
另一种是以树的多重链表表示键树，即 Trie 树，又称字典树。
|
三 双链树构成
3.1 构成
1
2
3
4
| 当使用孩子兄弟表示法表示键树时，树的结点构成分为 3 部分：
1.symbol 域：存储关键字的一个字符；
2.first 域：存储指向孩子结点的指针；
3.next 域：存储指向兄弟结点的指针；
|
3.2 注意事项
1
2
3
| 注意：对于叶子结点来说，由于其没有孩子结点，在构建叶子结点时，
将 first 指针换成 infoptr 指针，用于指向该关键字。
当叶子结点（结束符 ‘$’所在的结点）中使用 infoptr 域指向该自身的关键字时，此时的键树被称为双链树。
|
四 双链树图示
如图 1 中的键树用孩子兄弟表示法表示为双链树时，如图 2 所示：
1
| 提示：每个关键字的叶子结点 $ 的 infoptr 指针指向的是各自的关键字，通过该指针就可以找到各自的关键字的首地址
|
五 示例代码
5.1 思路
1
2
3
| 在使用孩子兄弟表示法表示的键树中做查找操作，从树的根结点出发，依次同被查找的关键字进行比对，
如果比对成功，进行下一字符的比对；
反之，如果比对失败，则跳转至该结点的兄弟结点中去继续比对，直至比对成功或者为找到该关键字。
|
5.2 示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <stdio.h>
typedef enum {LEFT,BRANCH} NodeKind; //定义结点的类型，是叶子结点还是其他类型的结点
typedef struct {
char a[20];//存储关键字的数组
int num;//关键字长度
} KeysType;
//定时结点结构
typedef struct DLTNode {
char symbol;//结点中存储的数据
struct DLTNode *next;//指向兄弟结点的指针
NodeKind *kind;//结点类型
union { //其中两种指针类型每个结点二选一
struct DLTNode* first;//孩子结点
struct DLTNode* infoptr;//叶子结点特有的指针
};
}*DLTree;
//查找函数，如果查找成功，返回该关键字的首地址，反则返回 NULL。T 为用孩子兄弟表示法表示的键树，K 为被查找的关键字。
DLTree SearchChar(DLTree T, KeysType k) {
int i = 0;
DLTree p = T->first;//首先令指针 P 指向根结点下的含有数据的孩子结点
//如果 p 指针存在，且关键字中比对的位数小于总位数时，就继续比对
while (p && i < k.num) {
//如果比对成功，开始下一位的比对
if (k.a[i] == p->symbol) {
i++;
p = p->first;
}
//如果该位比对失败，则找该结点的兄弟结点继续比对
else {
p = p->next;
}
}
//比对完成后，如果比对成功，最终 p 指针会指向该关键字的叶子结点 $，通过其自有的 infoptr 指针找到该关键字。
if ( i == k.num) {
return p->infoptr;
} else {
return NULL;
}
}
|
六 参考