重头开始嵌入式第四十一天（数据结构 树 哈希表）
树
目录
树
树的定义
二叉树，binary tree
特殊的二叉树
二叉树的特性
层序遍历
1.创建树CreateBiTree();
2.销毁树DestroyBiTree();
3.前序遍历void PreOrderTraverse();
4.中序遍历void InOrderTraverse(BiTree T);
5.后序遍历void PostOrderTraverse(BiTree T);
哈夫曼树
一、基本概念
二、构建过程
三、应用场景
哈希表
一、基本原理
二、主要特点
三、应用场景
如何解决哈希表冲突
一、选择合适的哈希函数
二、增大哈希表的容量
三、采用冲突解决方法
四、优化数据存储方式
哈希表的编程
1.创建
2.哈希函数
3.插入
4.查找
5.销毁
树的定义
树：n（n>=0）个结点的有限集合。n = 0 ,空树。
在任意一个非空树中，
1，有且仅有一个特定的根结点
2，当n>1 时，其余结点可分为m个互不相交的有限集合T1,T2,T3.。。。。Tm，其中每一个
集合又是一个树，并且称谓子树。
结点拥有子树的个数称谓结点的度。度为0的结点称谓叶结点。度不为0，称谓分支结点。
树的度数是指，这棵树中，最大的结点的度数，称谓树的度数。
树的深度或高度，从根开始，根为第一层，根的孩子为第二层。
树的存储，顺序结构，链式结构。
二叉树，binary tree
n个结点的有限集合，集合要么为空树，要么由一个根结点和两棵互不相交，分别称谓根结点的左子树和右子树的二叉树组成。。
特点，
1，每个结点最多两个子树。
2，左子树和右子树是有顺序的，次序不能颠倒。
3，如果某个结点只有一个子树，也要区分左，右子树。
特殊的二叉树
1，斜树，所有的结点都只有左子树，左斜树，所有结点都只有右子树，右树。
2，满二叉树，所有的分支结点都存在左右子树，并且叶子都在同一层上。
3，完全二叉树，对于一颗有n个结点的二叉树按层序编号，如果编号i（1<=i<=n）的结点于同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可树为完全二叉树。
二叉树的特性
1，在二叉树的第i层上最多有2^(i-1)个结点 i>=1
2,深度为k的二叉树至多有2^k -1 个结点 k>=1
3,任意一个二叉树T，如果其叶子结点的个数是n0,度数为2的结点数为n2， n0 = n2 +1;
4,有n个结点的完全二叉树深度为(logn/log 2) +1;
层序遍历
前序，根左右，先访问根，然访问左，访问右。
中序，左根右，先从根开始（不是先访问根），从左开始访问，在访问根，在访问右结点。
后序，左右根，先从根开始（不是先访问根），先访问左，在访问右。在访问根。
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
1.创建树CreateBiTree();
char data[]="abd##eg###cf#h###";
int inx;
void CreateBiTree(BiTNode** root)
{char c = data[inx++];if('#'==c){*root= NULL;return ;}else {*root =(BiTNode*)malloc(sizeof(BiTNode));if(NULL == *root){return ;}(*root)->data = c;CreateBiTree(&(*root)->lchild);CreateBiTree(&(*root)->rchild);}return ;
}2.销毁树DestroyBiTree();
void DestroyBiTree(BiTNode* root)
{if(NULL == root){return ;}DestroyBiTree(root->lchild);DestroyBiTree(root->rchild);free(root);return ;
}3.前序遍历void PreOrderTraverse();
void PreOrderTraverse(BiTNode * root)
{if(NULL == root){return ;}printf("%c",root->data);PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);
}4.中序遍历void InOrderTraverse(BiTree T);
void InOrderTraverse(BiTNode* root)
{ if(NULL == root){return ;}InOrderTraverse(root->lchild);printf("%c",root->data);InOrderTraverse(root->rchild);}5.后序遍历void PostOrderTraverse(BiTree T);
void PostOrderTraverse(BiTNode*root)
{ if(NULL == root){return ;}PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c",root->data);
}
哈夫曼树
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
一、基本概念
1. 带权路径长度：树中所有叶节点的带权路径长度之和。叶节点的带权路径长度为该叶节点的权值与从根节点到该叶节点的路径长度之积。
2. 权值：可以理解为某个数据的重要程度或者出现的频率等数值。
二、构建过程
1. 首先，将给定的一组权值看作是 n 个孤立的二叉树，每棵树只有一个带权值的叶节点。
2. 然后，从这些二叉树中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，新二叉树的根节点权值为左右子树根节点权值之和。
3. 重复上述步骤，直到只剩下一棵树，这棵树就是哈夫曼树。
三、应用场景
1. 哈夫曼编码：在数据通信和数据压缩领域广泛应用。通过为不同的字符分配不同长度的编码，使得经常出现的字符编码较短，不常出现的字符编码较长，从而实现数据的高效压缩。
2. 决策树：在机器学习和数据分析中，哈夫曼树的思想可以用于构建决策树，帮助进行分类和预测等任务。
哈希表
哈希表（Hash Table），也叫散列表，是一种根据关键码值（Key value）而直接进行访问的数据结构。
一、基本原理
1. 哈希函数：通过一个特定的哈希函数，将关键码映射到一个有限的连续地址空间中，这个地址空间通常被称为哈希表。例如，一个简单的哈希函数可以是对关键码取余，即 hash(key) = key % table_size ，其中 table_size 是哈希表的大小。
2. 冲突解决：由于不同的关键码可能会映射到相同的地址，这就会产生冲突。解决冲突的方法有很多种，常见的有开放地址法（如线性探测、二次探测等）和链地址法（将冲突的元素存储在一个链表中）。
二、主要特点
1. 快速查找：哈希表能够在平均情况下以接近常数时间的复杂度进行查找、插入和删除操作，这使得它在处理大量数据时非常高效。
2. 空间效率：哈希表可以根据实际需求动态调整大小，在存储大量数据时能够有效地利用内存空间。
三、应用场景
1. 数据库索引：可以快速定位数据库中的记录，提高查询效率。
2. 缓存：用于存储最近使用的数据，以便快速访问，减少对底层存储的访问次数。
3. 编程语言的实现：许多编程语言内部使用哈希表来实现集合、字典等数据结构。
如何解决哈希表冲突
可以通过以下几种方法来避免或减少哈希表的冲突：
一、选择合适的哈希函数
1. 均匀性好：哈希函数应尽可能使不同的关键码均匀地分布在哈希表中，减少冲突的可能性。例如，使用除留余数法时，选择一个与关键码集合大小互质的除数，可以提高均匀性。
2. 随机性强：一些哈希函数通过引入随机因素，使得不同输入产生的哈希值更加随机，从而降低冲突概率。
二、增大哈希表的容量
1. 直接扩容：增加哈希表的大小，可以使每个关键码有更多的可能地址，从而减少冲突。当哈希表的负载因子（已存储的元素数量与表的大小之比）过高时，可以考虑扩容。
2. 动态调整：设计哈希表时，可以实现动态调整大小的功能。当负载因子超过一定阈值时自动扩容，当负载因子过低时可以适当缩小表的大小以节省空间。
三、采用冲突解决方法
1. 开放地址法：
- 线性探测：当发生冲突时，依次探测下一个地址，直到找到一个空位置。这种方法简单，但容易产生聚集现象，即连续的地址被占用，进一步增加冲突的可能性。
- 二次探测：探测的地址不是线性的，而是通过一个二次函数来计算，例如 hash(key) + i^2 和 hash(key) - i^2 （其中 i 是探测次数）。这种方法可以减少聚集现象。
2. 链地址法：将哈希到同一地址的所有元素存储在一个链表中。这种方法不会产生聚集现象，但在查找时需要遍历链表，可能会影响性能。当链表过长时，可以考虑将其转换为其他更高效的数据结构，如红黑树。
四、优化数据存储方式
1. 对关键码进行预处理：例如，对字符串类型的关键码进行大小写统一、去除空格等操作，确保不同形式的关键码在哈希之前具有一致性，减少因输入形式不同而导致的冲突。
2. 组合多个哈希函数：使用多个哈希函数对关键码进行计算，然后将结果组合起来得到最终的哈希值。这样可以增加哈希值的随机性，降低冲突概率。
哈希表的编程
1.创建
HStable* CreateHStable(int len)
{HStable* hs = (HStable*)malloc(sizeof(HStable));if(NULL ==hs){perror("create hs malloc");return NULL;}hs->head =(DATATYPE*) malloc(sizeof(DATATYPE)*len);if(NULL == hs->head){perror("create CreateHStable malloc2 ");return NULL;}int i = 0 ;for(i=0;i<len;i++){hs->head[i]=-1;}hs->tlen = len;return hs;
}2.哈希函数
int HStableFun(HStable*hs ,DATATYPE*data)
{return *data % hs->tlen;
}3.插入
int HStableInsert(HStable*hs,DATATYPE* data)
{int inx = HStableFun(hs,data);while(-1 != hs->head[inx]){inx = (inx+1)%hs->tlen;}hs->head[inx] = *data;return 0;}4.查找
int HStableSearch(HStable*hs,DATATYPE*data)
{int inx = HStableFun(hs,data);int old_inx = inx;while(hs->head[inx]!=*data){inx = (inx+1)%hs->tlen;if(inx == old_inx){return -1;}}return inx;}5.销毁
int HStableDestroy(HStable*hs)
{free(hs->head);free(hs);return 0;
}