【数据结构】字典树T树

---

引言：为什么需要字典树？

• 实现类似搜索引擎的效果，当输入“西安”关键字时，下面出现的联想词（如下图）

  

  一、字典树逻辑图

  

• T字典树功能，只能插入结点、暂不能删除结点（删除过程比较复杂）、根据关键码进行查询

  二、数据结点的设计

  （1）逻辑图

  

  （2）详细类型

  const int MaxChSize = 26;	//最长关键码
  const int LinkSize = 27;	//分支结点的指针个数
  //T树结点的类型
  typedef enum {ELEM = 1, BRCH = 2} NodeType;	//1元素结点，2分支结点
  //关键码类型
  typedef struct 
  {
  	char ch[MaxChSize];	//关键字符
  	int CurSize;		//当前的字符长度
  }KeyType;
  
  //元素类型(关键码 + 相关信息)
  typedef struct
  {
  	KeyType key;	//关键码
  	void* InfoPtr;	//相关信息
  }ElemType;
  
  //声明TrieNode
  struct TrieNode;
  //分支结点
  typedef struct
  {
  	TrieNode* Link[LinkSize];	//分支链
  }BranchNode;
  
  //T树结点
  typedef struct TrieNode
  {
  	NodeType Ttype;	//结点类型
  	union {
  		ElemType elem;
  		BranchNode brchNode;
  	};
  }TrieNode;

  三、T树的详细实现

#include<iostream>
using namespace std;
const int MaxChSize = 26;	//最长关键码
const int LinkSize = 27;	//分支结点的指针个数
//T树结点的类型
typedef enum { ELEM = 1, BRCH = 2 } NodeType;	//1元素结点，2分支结点
//关键码类型
typedef struct
{
	char ch[MaxChSize];	//关键字符
	int CurSize;		//当前的字符长度
}KeyType;

//元素类型(关键码 + 相关信息)
typedef struct
{
	KeyType key;	//关键码
	void* InfoPtr;	//相关信息
}ElemType;


//声明TrieNode
struct TrieNode;
//分支结点
typedef struct
{
	TrieNode* Link[LinkSize];	//分支链
}BranchNode;

//T树结点
typedef struct TrieNode
{
	NodeType Ttype;	//结点类型
	union {
		ElemType elem;
		BranchNode brchNode;
	};
}TrieNode;

//T字典树
class TrieTree
{
private:
	TrieNode* root;	//根节点
public:
	TrieTree() : root(nullptr) {}
	~TrieTree() {}
private:
	//第k个元素的下标
	int TransIndex(const KeyType& kch, int k)
	{
		int index = 0;	//默认0下标
		if (k < kch.CurSize)
		{
			index = kch.ch[k] - 'a' + 1;
		}
		return index;
	}
	//申请TrieNode结点
	TrieNode* BuyTrieNode()
	{
		TrieNode* p = (TrieNode*)malloc(sizeof(TrieNode));
		if (nullptr == p) exit(-1);
		memset(p, 0, sizeof(TrieNode));
		return p;
	}
	//申请元素类型结点
	TrieNode* MakeElemNode(const ElemType& item)
	{
		TrieNode* s = BuyTrieNode();
		s->Ttype = ELEM;
		s->elem = item;
		return s;
	}
	//申请分支类型结点
	TrieNode* MakeBrchNode(TrieNode* ptr, int k)
	{
		//返回值作为改变root的ptr指向的元素结点
		TrieNode* s = BuyTrieNode();
		s->Ttype = BRCH;
		int index = TransIndex(ptr->elem.key, k);
		s->brchNode.Link[index] = ptr;
		return s;
	}
	//插入结点
	void Insert_item(TrieNode*& ptr, const ElemType& item, int k)
	{
		//ptr指向是nullptr
		if (nullptr == ptr)
		{
			ptr = MakeElemNode(item);
		}
		//ptr指向是分支结点
		else if (ptr->Ttype == BRCH)
		{
			//寻找第k个字符的分支位置
			int index = TransIndex(item.key, k);
			Insert_item(ptr->brchNode.Link[index], item, k + 1);
		}
		//ptr指向是元素结点
		else if (ptr->Ttype == ELEM)
		{
			//增加分支, 指向元素结点的ptr重新指向分支
			ptr = MakeBrchNode(ptr, k);

			//计算当前elem的k个字母的下标
			int index = TransIndex(item.key, k);

			//继续搜寻k+1个字符对应的位置
			Insert_item(ptr->brchNode.Link[index], item, k + 1);
		}
	}
public:
	//通过关键码进行查询
	TrieNode* FindTrieNode(const KeyType& key)
	{
		TrieNode* p = root;
		int k = 0;
		while (p != nullptr && p->Ttype == BRCH)
		{
			int index = TransIndex(key, k);
			p = p->brchNode.Link[index];
			++k;
		}
		if (p != nullptr && strcmp(p->elem.key.ch, key.ch) != 0)
		{
			p = nullptr;
		}
		return p;
	}

	bool Insert(const ElemType& item)
	{
		//去重,存在则插入失败
		TrieNode* res = FindTrieNode(item.key);
		if (nullptr != res) return false;

		int k = 0;
		Insert_item(root, item, k);
		return true;
	}
};

四、插入、查询测试

int main()
{
	//给定关键码
	KeyType keySet[] = { "cao", 3, "cai", 3, "feng", 4, "fengt", 5 };
	int size = sizeof(keySet) / sizeof(keySet[0]);
	//构建T树(是在插入元素结点的过程中不断的扩充、分裂)
	TrieTree Tt;
	for (int i = 0; i < size; ++i)
	{
		ElemType node = { keySet[i], nullptr };
		Tt.Insert(node);
	}

	//查询
	for (int i = 0; i < size; ++i)
	{
		TrieNode* res = Tt.FindTrieNode(keySet[i]);
		if (res == nullptr) continue;
		cout << "found it! " << res->elem.key.ch << endl;
	}
	return 0;
}

---