杂谈; 打败自己的 往往不是敌人，而是自己。坚持不易，且行且珍惜。
键树的根节点不包含字符，除根节点外的非叶子节点都只包含一个字符，叶子节点存储具体信息。； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。并且 兄弟节点 按 按 字符大小 排序。
例如：
它的 键树形式如下：
键树的应用：（摘自百度）
串的快速检索
给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
串”排序
给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出
用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
最长公共前缀
对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。
键树 有 两种 表示 方法：1. 双链表 表示法 ，就是 树的 孩子链表 表示法 2.多重链表表示法（Trie树）
下面给出 键树的 双链表 表示法的 插入，删除，查找 等功能 代码：
完整源代码网盘地址：?shareid=582619924&uk=1208029266
// DSTree.cpp : 定义控制台应用程序的入口点。//键树的双链树表示法#include "stdafx.h"#include <cstdlib>#include <cstring>#include "queue.h"#include "stack.h"#define MAX_KEY_LEN16#define LEAF_END_CHAR '$'//叶子节点结束符struct KeyType{char key[MAX_KEY_LEN];int len;};void initKey(KeyType * kt,char * k){int len = strlen(k);strncpy(kt->key,k,len+1);kt->len = len;}enum E_Kind{E_Kind_Leaf,E_Kind_Branch,};typedef struct DLNode{char data;DLNode * nextSibling;//下一个兄弟节点E_Kind kind;;union{char * record;//叶子节点的信息DLNode * firstChild;//第一个孩子节点(分支节点）};}*DLTree;DLNode * makeNode(E_Kind kind){DLNode * node = (DLNode *)malloc(sizeof(DLNode));node->kind = kind;node->nextSibling = NULL;if (node->kind == E_Kind_Branch){node->firstChild = NULL;}else{node->record = (char *)malloc(sizeof(char)*MAX_KEY_LEN);node->data = LEAF_END_CHAR;}return node;}void initTree(DLTree * tree){*tree = NULL;}void destoryTree(DLTree * tree){DLTree p = *tree;if (p != NULL){if (p->kind == E_Kind_Leaf){free(p->record);}else{destoryTree(&p->firstChild);}destoryTree(&p->nextSibling);free(p);*tree = NULL;}}DLTree search(DLTree t,char * k){if (t != NULL){KeyType kt;initKey(&kt,k);int times = 0;t = t->firstChild;while (t && times < kt.len){while (t && t->data < kt.key[times]) t = t->nextSibling;if (t && t->data == kt.key[times]){t = t->firstChild;times++;}else{return NULL;}}if (times == kt.len && t->kind == E_Kind_Leaf){return t;}}return NULL;}//搜索结果.为插入 关键字 服务//是第一个孩子节点：tree:返回 父亲节点 ，不是 返回 兄弟节点.struct Result{bool isFind;//是不是找到了bool isFirst;//是不是第一个孩子节点DLTree tree;//插入位置int index;//需要插入的节点 的位置.};Result searchForInsert(DLTree tree,KeyType key){int times = 0;Result result;result.isFirst = false;result.isFind = false;while (tree && times < key.len){DLTree fatherNode = tree;result.index = times;tree = tree->firstChild;while (tree){if (tree->data > key.key[times]){if (fatherNode->firstChild == tree){result.isFirst = true;result.tree = fatherNode;}return result;}else if(tree->data == key.key[times]){result.tree = tree;times ++;break;}else{// $ 比 a ~ z 小result.tree = tree;tree = tree->nextSibling;}}}if ( times == key.len){//全部都相等if (tree && tree->firstChild && tree->firstChild->kind == E_Kind_Leaf){result.isFind = true;result.tree = tree->firstChild;}else{result.isFirst = true;result.index = times;}}return result;}void insert(DLTree t,KeyType kt,int index){for (int i = index; i < kt.len; i++){DLNode * node = makeNode(E_Kind_Branch);node->data = kt.key[i];t->firstChild = node;t = node;}//最后插入叶子节点DLNode * leaf = makeNode(E_Kind_Leaf);strncpy(leaf->record,kt.key,kt.len+1);t->firstChild = leaf;}void insertTree(DLTree * tree,char * key){KeyType kt;initKey(&kt,key);if (*tree == NULL){//空树，需要设置一个根节点*tree = makeNode(E_Kind_Branch);insert(*tree,kt,0);return;}Result result = searchForInsert(*tree,kt);if (result.isFind == false){//没找到，再插入.if (result.isFirst){//插入在头部DLTree fatherNode = result.tree;DLTree oldFirst = fatherNode->firstChild;insert(fatherNode,kt,result.index);fatherNode->firstChild->nextSibling = oldFirst;}else{DLTree leftBrother = result.tree;DLNode * node = makeNode(E_Kind_Branch);node->data = kt.key[result.index];node->nextSibling = leftBrother->nextSibling;leftBrother->nextSibling = node;insert(node,kt,result.index+1);}}}void deleteTree(DLTree * t,char * k){if (*t != NULL){KeyType kt;initKey(&kt,k);DLTree p = (*t)->firstChild;int times = 0;linkStack stack;stackInit(&stack);stackPush(&stack,*t);while (p && times < kt.len){while (p && p->data < kt.key[times]) p = p->nextSibling;if (p && p->data == kt.key[times]){stackPush(&stack,p);p = p->firstChild;times++;}else{return;//没找到}}if (p && p->kind == E_Kind_Leaf){DLTree f = NULL;while (!stackEmpty(stack)){stackPop(&stack,&f);if (f->firstChild == p && p->nextSibling == NULL){//父亲只有 一个孩子free(p);p = f;if (*t == f){//所有关键字都被删除了，空树..free(*t);*t = NULL;return;}}else{break;}}if (f->firstChild == p){f->firstChild = p->nextSibling;}else{DLTree pre = f->firstChild;while (pre != NULL && pre->nextSibling != p) pre = pre->nextSibling;pre->nextSibling = p->nextSibling;}free(p);}stackDestory(&stack);}}//层序遍历void levelTraverse(DLTree tree){if (tree != NULL){if (tree->firstChild != NULL){printf("—————-层序遍历—————-\n");LinkQueue queue;queueInit(&queue);enqueue(&queue,tree->firstChild);int count = 1;int level = 1;int nextCount = 0;while (!queueEmpty(queue)){printf("%d 层数据：",level);for (int i = 0; i < count; i++){DLTree t;dequeue(&queue,&t);while (t){printf("%c ",t->data);if (t->kind == E_Kind_Branch && t->firstChild != NULL){enqueue(&queue,t->firstChild);nextCount++;}t = t->nextSibling;}}printf("\n");count = nextCount;nextCount = 0;level++;}queueDestory(&queue);printf("\n");}}}static char testArray[][MAX_KEY_LEN] = {//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[]){DLTree root;initTree(&root);for (int i = 0; i < 16; i++){insertTree(&root,testArray[i]);}levelTraverse(root);for (int i = 0; i < 18; i++){char * s = testArray[i];DLTree t = search(root,s);if (t){printf("查找 %s后，，记录为：%s\n",s,t->record);}else{printf("查找 %s,没找到\n",s);}}for (int i = 0; i < 18; i++){char * s = testArray[i];deleteTree(&root,s);printf("————-删除%s后————–\n",s);levelTraverse(root);}destoryTree(&root);return 0;}
即将转出来的那一面，是快乐或痛苦，是爱还是恨。
