1. 二叉树
一般地二叉树多用链式存储结构来描述元素的逻辑关系。通常情况下二叉树中的结点定义如下:
typedef struct btree_node { void *item; struct btree_node *left; struct btree_node *right; } btree_node_t;
在一些不同的实际应用中，还可以增加某些指针域或者线索化标志，例如增加指向父结点的指针、左右线索化的标志。
另外如果你想区分二叉树结点和二叉树这种结构，不妨定义如下的二叉树结构(类似于STL中分离定义数据结构和元素结点的方法):
typedef struct { btree_node_t *root; int n; int (*comp)(const void *,const void *); } btree_t; typedef void (*cb)(btree_node_t *);//定义访问结点的函数指针
其中n表示二叉树结点的个数，comp表示函数指针。使用函数指针comp因为数据类型使用的是通用指针，在进行查找等比较数据大小的操作时需要定义一个比较函数，在泛型数据结构的C实现中应用非常广泛。
1.1 二叉树的遍历
二叉树常见的遍历次序有先序、中序、后序三种，其中序表示根结点在何时被访问。每种遍历算法都有对应的递归解法和非递归解法。它的非递归解法中使用了栈这种数据结构。每个遍历都有自身的特点：
- 先序遍历序列的第一个结点和后序遍历的最后一个结点一定是根结点
- 在中序遍历序列中，根结点将序列分成两个子序列: 根结点左子树的中序序列和根结点右子树的中序序列
- 先序序列或者后序序列或者层次序序列结合中序序列可以唯一确定一棵二叉树
二叉树还有一种层次序遍历，它是按自顶向下、自左向右的访问顺序来访问每个结点，它的实现使用了队列这种数据结构。
此外二叉树还有一种Morris遍历方法，和上面使用O(n)空间复杂度的方法不同，它只需要O(1)的空间复杂度。这个算法跟线索化二叉树很像，不过Morris遍历是一边建立线索一边访问数据，访问完后直接销毁线索，保持二叉树的不变。Morris算法的原则比较简单：借助所有叶结点的右指针(空指针)指向其后继节点，组成一个环，但由于第二次遍历到这个结点时，由于左子树已经遍历完了，就访问该结点。
总结下来，遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，例如求二叉树的深度(高度)、二叉树的叶子结点个数、求某层结点个数(或者树的最大宽度、分层输出结点)、判断二叉树是否相同或者是否为完全二叉树或者二叉排序树、求二叉树中结点的最大距离、由遍历序列重建二叉树等。
1.2遍历的递归解法
递归代码比较简单，就不具体解释了，实现如下:
/*先序遍历，递归*/ void bt_preorder(btree_t *t, cb visit){ bt_preorder_rec(t->root,visit); } void bt_preorder_rec(btree_node_t *cur, cb visit) { if(cur==NULL) return ; visit(cur); bt_preorder_rec(cur->left,visit); bt_preorder_rec(cur->right,visit); } /*中序遍历，递归*/ void bt_inorder(btree_t *t, cb visit) { bt_inorder_rec(t->root,visit); } void bt_inorder_rec(btree_node_t *cur, cb visit) { if(cur==NULL) return ; bt_inorder_rec(cur->left,visit); visit(cur); bt_inorder_rec(cur->right,visit); } /*后序遍历，递归*/ void bt_postorder(btree_t *t, cb visit) { bt_postorder_rec(t->root,visit); } void bt_postorder_rec(btree_node_t *cur, cb visit) { if(cur==NULL) return ; bt_postorder_rec(cur->left,visit); bt_postorder_rec(cur->right,visit); visit(cur); }
1.3基于栈或队列的非递归解法
A 基于栈的VLR先序遍历
整体思路：先入栈根结点，然后再判断栈是否为空：不为空，出栈当前元素，并按照右左子树顺序分别入栈。该方法可借助栈的操作，如下的方法采用了类似于栈的实现方式,注意入栈顺序: VRL。
实现如下:
void bt_preorder_iter(btree_t *t, cb visit){ if(t->root){ btree_node_t **stack=malloc(sizeof(btree_node_t *)*(t->n)); stack[0]=t->root; int top=1; while(top>0){ //只要栈不为空 btree_node_t *cur=stack[--top];//出栈 visit(cur); if(cur->right) stack[top++]=cur->right; if(cur->left) stack[top++]=cur->left; } free(stack); } }
B 基于栈的LVR中序遍历
整体思路：判断条件有两个：栈是否为空或当前结点cur是否为空。根据中序遍历顺序LVR
- 如果栈为空，需不断压栈当前每个非空结点一直遍历到第一个没有左孩子的根结点
- 此时cur为空，top(栈中的元素大小)只要大于0，开始进行出栈，访问当前结点,再遍历右子树
实现如下:
void bt_inorder_iter(btree_t *t, cb visit){ btree_node_t **stack=malloc(sizeof(btree_node_t *)*(t->n)); btree_node_t *cur=t->root; int top=0; while(top>0|| cur!=NULL){ if(cur !=NULL){ stack[top++]=cur; cur=cur->left; } else{ cur=stack[--top];//出栈当前栈顶元素 visit(cur); cur=cur->right; } } free(stack); }
C 基于栈的LRV后序遍历
整体思路: 用栈存储结点时，必须分清返回根结点时：是从左子树返回的还是从右子树的返回的。这里用一个pre指针记录最近刚访问过的结点。当一直往左直到左孩子为空时,判断当前结点的右孩子是否为空或者是否已访问过
- 若右孩子为空或者已被访问过(LV或者LRV),则访问当前结点，并更新最近访问的结点，并重置当前指针为NULL
- 否则遍历右孩子(压栈)，再转向左
实现如下:
void bt_postorder_iter(btree_t *t, cb visit){ btree_node_t **stack=malloc(sizeof(btree_node_t *)*(t->n)); btree_node_t *cur=t->root; btree_node_t *pre=NULL; //指向最近访问过的结点 int top=0; while(cur!=NULL||top>0){ //当前结点不为空或者栈不为空 if(cur){ //压栈，一直往左走 stack[top++]=cur; cur=cur->left; } else { cur=stack[top-1];//取栈顶元素 if(cur->right&&cur->right!=pre){ //如果右子树存在，且未被访问过 cur=cur->right; stack[top++]=cur; //转向右，压栈 cur=cur->left;//再走向最左，始终保持LRV的遍历顺序 } else{ //要么右孩子为空，要么右孩子已经被访问过，弹出当前结点 cur=stack[--top]; visit(cur); pre=cur; //记录最近访问过的结点，结点访问完重置cur指针 cur=NULL; } } } free(stack); }
D 基于队列的层次序遍历
和先序遍历很类似，区别就是栈换成了队列。实现如下:
void bt_levelorder(btree_t *t,cb visit){ if(t->root){ int maxsize=t->n+1;//使用循环队列浪费1个空间 btree_node_t **queue=malloc(sizeof(btree_node_t *)*maxsize); btree_node_t *cur; int front=0; int rear=0; rear=(rear+1)%maxsize; queue[rear]=t->root; while(front!=rear){ //判断队列是否为空 front=(front+1)%maxsize; cur=queue[front];//出队 visit(cur); if(cur->left){ rear=(rear+1)%maxsize; queue[rear]=cur->left; //入队 } if(cur->right){ rear=(rear+1)%maxsize; queue[rear]=cur->right;//入队 } } free(queue); } }
1.4Morris遍历
A Morris中序遍历
步骤如下: 初始化当前节点cur为root节点
- 若当前cur没有左孩子，直接访问当前结点，cur转向右孩子
- 若cur有左孩子，先寻找到cur的前驱节点
- 如果前驱节点右孩子为空，记录前驱节点右孩子为当前结点，cur转向左孩子
- 如果前驱节点右孩子为当前节点，表明左孩子已被访问，将前驱节点右孩子重设为空;直接访问当前结点，cur转向右孩子
B Morris先序遍历
步骤如下: 初始化当前节点cur为root节点
- 若当前cur没有左孩子，直接访问当前结点，cur转向右孩子
- 若cur有左孩子，先寻找到cur的前驱节点
- 如果前驱节点右孩子为空，记录前驱节点右孩子为当前结点，访问当前节点，并将当前结点设置为已访问过的节点，cur转向左孩子
- 如果前驱节点右孩子为当前节点，表明左孩子已被访问，将前驱节点右孩子重设为空，cur转向右孩子
C Morris后序遍历
Morris后续遍历稍微麻烦点：它必须保证在访问某个当前节点时，左右子树的所有左孩子必须先被访问;而右孩子的输出从底部往顶部逆向访问就行
步骤如下：设置一个虚拟根结点，记它的左孩子为root,即当前cur为该虚拟根结点
- 如果cur的左孩子为空，先记录会被访问的当前节点再转向右孩子分支
- 如果cur的左孩子不为空，找到cur的前驱
- 如果前驱的右孩子为空，建立线索化，记录会被访问的当前节点再转向左孩子分支
- 如果前驱的右孩子为当前节点，表示已经线索化，因而逆向输出当前节点左孩子到该前驱节点路径上的所有节点,转向当前节点右孩子分支
实现如下:
void bt_morris_inorder(btree_t *t, cb visit){ if(t->root){ btree_node_t *cur=t->root; btree_node_t *pre; //前驱线索 while(cur){ if(cur->left==NULL){ visit(cur); pre=cur; //记录已被访问的前驱 cur=cur->right; } else{ /*先找到cur的前驱节点*/ btree_node_t *tmp=cur->left; while(tmp->right&&tmp->right!=cur) tmp=tmp->right; if(tmp->right==NULL){ //表明左子树未访问，先建立线索再访问左子树 tmp->right=cur; cur=cur->left;//没有访问，无需记录pre指针 } else { //左子树已被访问，则访问当前节点，恢复二叉树,遍历右子树 visit(cur); tmp->right=NULL; pre=cur; cur=cur->right; } } } } } void bt_morris_preorder(btree_t *t, cb visit){ if(t->root){ btree_node_t *cur=t->root; btree_node_t *pre; //前驱线索 while(cur){ if(cur->left==NULL){ visit(cur); pre=cur; cur=cur->right; //记录直接前驱，转向右孩子 } else{ btree_node_t *tmp=cur->left; while(tmp->right&&tmp->right!=cur) tmp=tmp->right; if(tmp->right==NULL){ //表明右子树未被访问，访问当前节点，更新线索，转向左孩子 visit(cur); //仅这一行位置与中序不同 tmp->right=cur; pre=cur;//标记当前节点被访问过(这个与visit函数在同一个代码段内) cur=cur->left; } else { //表明左子树已被访问，重置线索，转向右孩子 tmp->right=NULL; /*pre=cur; 不能有这句，因为cur早早被访问*/ cur=cur->right; } } } } } void bt_morris_postorder(btree_t *t, cb visit){ if(t->root){ btree_node_t *rec=malloc(sizeof(btree_node_t)); rec->left=t->root; //创建一个dummy结点，它的左孩子指向根结点 btree_node_t *cur=rec;//从虚拟根结点开始遍历 btree_node_t *pre; while(cur){ if(cur->left==NULL){ pre=cur;//和前两个morris遍历不同，这种方法是先线索化后保证一侧子树都被访问完后直接逆向输出 cur=cur->right;//一般是先访问后再记录被访问的节点，这次相反先记录将被访问的节点后再访问 } else { btree_node_t *tmp=cur->left; while(tmp->right&&tmp->right!=cur) tmp=tmp->right; if(tmp->right==NULL){ //还未线索化，未被访问，先建立线索 tmp->right=cur;//保证下一次循环时回到后继节点，此时已被线索化 pre=cur;//必须要有，先记录 cur=cur->left; } else{ //已建立线索 reverse_branch(cur->left,tmp,visit); pre->right=NULL; pre=cur; //必须要有 cur=cur->right; } } } free(rec); } }
2. 位示图
2. 1位示图相关操作
一个unsigned int数能表示32个整数,整数从0开始,针对整数i:
- i对应的无符号数组下标索引slot:
i/32 - i对应的索引内容里面的比特位数:
i%32(1<<(i&0x1F)
因而在位数组中，必须提供三个重要操作:
- 清除位图某位:
bm->bits[i/32] &= ~(1<<(i%32)) - 设置位图某位:
bm->bits[i/32] |= (1<<(i%32)) - 测试位图某位:
bm->bits[i/32] & (1<<(i%32))
这里采用位掩码运算的方法完成这些操作，避免取模和除数运算，效率更高。
2. 2位示图的数据结构定义
位示图的数据结构定义如下:
/*位示图数据结构定义*/ typedef struct bitmap{ unsigned int *bits; int size; //整数个数大小 } bitmap_t;
位示图函数的功能测试如下:
#include "bitmap.h" #include <stdio.h> #include <stdlib.h> #define MAX 10000 #define RAD_NUM 100 int main(){ /*接受大小为MAX的参数，创建一个位图*/ bitmap_t *bm=bitmap_alloc(MAX); unsigned int i; unsigned int arr[RAD_NUM]; for(i=0;i< RAD_NUM;i++){ arr[i]=RAD_NUM-i; } /** * 设置某些数在位图的位表示为1 * 生成RAD_NUM个不相同的随机数据 * 插入位图中，对应位则设置为1 */ printf("原始无序的数据:\n"); for(i=0;i< RAD_NUM;i++){ unsigned int j=i+rand()%(RAD_NUM-i); int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; printf("%d ",arr[i]); if(i%10==0&&i!=0) printf("\n"); bitmap_set(bm,arr[i]); } printf("\n"); printf("使用位图排序后的数据:\n"); /*查询该数是否在数组中，很容易保证有序输出*/ for(i=0;i< MAX;i++){ if(bitmap_query(bm,i)){ printf("%d ",i); if(i%10==0&&i!=0) printf("\n"); } } printf("\n"); /*释放位图的内存*/ bitmap_free(bm); return 0; }
2. 3位示图的核心实现
核心的实现还是清除、设置和测试某个位，代码如下:
/*分配指定size大小的位示图内存*/ bitmap_t *bitmap_alloc(int size){ bitmap_t *bm=malloc(sizeof(bitmap_t)); bm->bits=malloc(sizeof(bm->bits[0])*(size+BITS_LENGTH-1)/BITS_LENGTH); //计算合适的slot个数 bm->size=size; memset(bm->bits,0,sizeof(bm->bits[0])*(size+BITS_LENGTH-1)/BITS_LENGTH); return bm; } /*释放位图内存*/ void bitmap_free(bitmap_t *bm){ free(bm->bits); free(bm); } /** * 一个unsigned int数能表示32个整数,整数从0开始,针对整数i: * i对应的无符号数组下标索引slot: i/32 * i对应的索引内容里面的比特位数: i%32(1<<(i&MASK) * * 清除位图某位: bm->bits[i/32] &= ~(1<<(i%32)) * 设置位图某位: bm->bits[i/32] |= (1<<(i%32)) * 测试位图某位: bm->bits[i/32] & (1<<(i%32)) * 这里采用位掩码运算的方法完成这些操作，避免取模和除数运算，效率更高 */ /**/ void bitmap_clear(bitmap_t *bm,unsigned i){ if(i>=bm->size){ printf("Invalid integer\n"); return ; } bm->bits[i>>SHIFT] &= ~(1<<(i & MASK)); } /*设置位图中的某一位*/ void bitmap_set(bitmap_t *bm,unsigned i){ if(i>=bm->size){ printf("Invalid integer\n"); return ; } bm->bits[i>>SHIFT] |= (1<<(i & MASK)); } /*查询位图中的某一位,该位为1，返回true;否则返回false*/ bool bitmap_query(bitmap_t *bm,unsigned i){ if(i>= bm->size) return false; if( (bm->bits[i>>SHIFT]) & (1<<(i & MASK))) return true; return false; }
3. 并查集
在某些应用中，要将n个不同的元素分成一组不相交的集合。在这个集合上，有两个重要的操作: 找出给定的元素所属的集合和合并两个集合。再例如处理动态连通性问题，假定从输入中读取了一系列整数对，如果已知的数据可说明当前整数对是相连的，则忽略输出，因而需要设计一个数据结构来保存足够的的整数对信息，并用它们来判断一对新对象是否相连。
解决这种问题的数据结构称为并查集。下面我们将介绍4种不同的算法实现，它们均以对象标号为索引的id数组来确定两对象是否处在同一个集合中
3.1 quick-find和quick-union算法
A quick-find算法策略
find操作实现很快速，只需返回对象所在的集合标识；union操作即要遍历整个数组使得p所在的集合分量值都设置为q所在的集合分量值。
- find操作：id[p]不等于id[q],所有和id[q]相等的元素的值变为id[p]的值。find操作只需访问数组一次.
- union操作: 对于每一对输入都要扫描整个数组
quick-find算法的时间复杂度O(N^2),对于最终只能得到少数连通分量的一般应用都是平方级别的。
/*p所在的分量标识符，0-N-1*/ int find(int p){ return id[p]; } public void union(int p,int q){ int pId=find(p); int qId=find(q); if(pId==qId) return ; //已经在同一个分量中，无需采取任何行动 for(int i=0;i<id.length;i++){ if(id[i]==pId) id[i]=qId; } count--; //减少有触点对应的id值是id[p]的分量 }
B quick-union算法策略
union操作很快速，只需将某对象的集合分量标识指向另外一个对象的集合分量，通过父链接的方式表示了一片不相交集合的分量
find操作则需要通过链接的形式找到一个表示它所在集合的标识(p=id[p])
-
find操作: 通过链接由一个触点到另外一个触点，知道有个链接它必定指向自身的触点即id[x]=x，该触点必然存在。因而find方法则是通过不断链接遍历到id[x]==x的时为止，该触点为根触点
-
union操作: 只需把一个根触点连接到另一个分量的根触点上，通过一条语句就使一个根结点变成另一个根结点的父结点，快速归并了两棵树
它是quick-find方法的一种改良(union操作总是线性级别的)，但并不能保证在所有情况下都比quick-find算法快。quick-union算法的效率取决于树中结点的深度，最坏情况下动态连通性问题只有一个分量，则quick-union的复杂度也是平方级别的。原因: 最坏情况下树的深度为N，树的深度无法得到保证。
public int find(int p){ while(p!=id[p]) p=id[p]; return p; } public void union(int p,int q){//将p和q所在的集合合并 int pRoot=find(p); int qRoot=find(q); if(pRoot==qRoot) return ; id[pRoot]=qRoot; count--; }
3.2 加权quick-union算法和使用路径压缩算法
对于quick-union中出现的糟糕算法，我们的改进办法是: 记录每一棵树的大小并总是将较小的树连接到较大的树中，它能够大大改进算法的效率，这种称为加权quick-union。
A 加权quick-union算法策略
较小的树根总是指向较大的树根，使得它构造的树高度远远小于未加权的所有版本的树高度。这里添加的额外数组可以设计成记录分量中结点的个数，也可设计成每个分量的高度。建议使用高度，这种被称为按秩合并(union by rank)的启发式策略，用秩表示结点高度的一个上界，在union操作中具有较小秩的根要指向具有较大秩的根。
这种加权quick-union算法构造的森林中任意结点的深度最多为lgN，有了它就可以保证能够在合理的时间范围内解决实际中的大规模动态连通性问题，这比简单的算法快数百倍。
... private int[] sz; //记录每个分量的结点个数 ... public int find(int p){ while(p!=id[p]) p=id[p]; return p; } /*合并操作总是使小树连接到大树上*/ public void union(int p,int q){ int pRoot=find(p); int qRoot=find(q); if(pRoot==qRoot) return; if(sz[pRoot]<sz[qRoot]) { id[pRoot]=qRoot; sz[qRoot] +=sz[pRoot]; } else{ id[qRoot]=pRoot; sz[pRoot] +=sz[qRoot]; } this.count--; }
B 带路径压缩的加权quick-union算法策略
为find添加第一个循环，将查找路径上的每个结点都直接指向根结点，最后得到的结果几乎是完全扁平化的树。注意路径压缩并不改变结点的秩
按算法导论中的平摊分析方法，这种带路径压缩的加权quick-union算法中find、union操作的均摊成本控制在反Ackerman函数的范围内(增长极慢的函数，结果始终控制在4以内的范围)，树的高度一直很小，没有任何昂贵的操作
public int find(int p){ while(p!=id[p]){ id[p]=id[id[p]]; p=id[p]; } return p; } public void union(int p,int q){ int r1=find(p); int r2=find(q); if(r1==r2) return; if(rank[r1]< rank[r2]){ id[r1]=r2; } else if(rank[r1] > rank[r2]){ id[r2]=r1; } else { id[r2]=r1; //小根指向大根的根结点 rank[r1]++; //相等时，产生新的高度，根的秩才加1(秩才上升) } count--; }
C 总结各种union-find算法的性能特点
一般地，带路径压缩的加权quick-union算法在解决实际问题时能在常数时间内完成每个操作，性能最好。建议实际应用中使用该算法，它们的比较如下:
具体完整实现如下:
#include "uf.h" #include <stdio.h> #include <stdlib.h> /*分配并查集的内存并初始化,n-并查集数组的大小*/ uf_t *uf_alloc(int n){ uf_t *t=malloc(sizeof(uf_t)); t->count=n; t->id=malloc(n*sizeof(int)); //分配一个连续的堆内存 int i; for(i=0;i<n;i++){ t->id[i]=-1; } return t; } /*释放并查集内存*/ void uf_free(uf_t *t){ free(t->id); free(t); } /*查找包含元素p的树的根－集合标号，带路径压缩,并不改变秩*/ int uf_find(uf_t *t,int p){ int cur=p; while(t->id[p] >=0) p=t->id[p]; //找到根结点 while(cur !=p){ //遍历查找过程的所有结点，将其结点指向根结点 int temp=t->id[cur]; t->id[cur]=p; cur=temp; } return p; } /*合并包含两元素p和q的树集合*/ void uf_union(uf_t *t,int p,int q){ int r1=uf_find(t,p); int r2=uf_find(t,q); //返回的是索引下标，而不是id值 if(r1==r2) return; //已在同一集合内，无需再合并 /*id值作为负数时，它的相反数表示该树中结点的个数*/ if(t->id[r1] > t->id[r2]){ //r2作为根 t->id[r2] += t->id[r1]; t->id[r1]=r2; } else { t->id[r1] += t->id[r2]; t->id[r2]=r1; } t->count--; } /*返回并查集中不相交集合的分量个数*/ int uf_count(uf_t *t){ return t->count; } /*返回并查集中包含p元素的集合大小*/ int uf_set_size(uf_t *t,int p){ int root=uf_find(t,p); return -t->id[root]; }
3.3 应用举例
一般并查集在很多问题中应用广泛，如:
- Percolation（物理系统的渗透）
- Dynamic connectivity（网络中的动态连通性问题）
- Least Common Ancestors（最近公共祖先，Tarjan离线算法）
- Hoshen-Kopelman algorithm in physics
- Kruskal's 最小生成树
- 有限自动机的等价性证明
- Hinley-Milner polymorphic type inference
- Morphological attribute openings and closings
3.3.1 最近公共祖先问题-LCA算法和RMQ算法
3.3.2 求最多连续数子集
给一个整数数组， 找到其中包含最多连续数的子集，比如给：15, 7, 12, 6, 14, 13, 9, 11，则返回: 5:[11, 12, 13, 14, 15] 。最简单的方法是sort然后scan一遍，但是要o(nlgn). 有什么O(n)的方法吗？
4. 海量数据处理
海量数据，一般是指数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，无法一次性装入内存，从而导致传统的操作无法实现。一般处理海量数据通常应用到如下数据结构: hash table、trie树、堆、败者树、bitmap和bloom filter
- hash table通常可用作hash_map或者hash_set,它一般可以用来统计某字符串出现的次数或者将大文件中的元素映射到不同的小文件中
- trie树除了用于判断字符串的前缀，它还可以统计或排序大量的字符串(不限制于字符串)。
- 堆一般是用于排序和统计topK的高效数据结构，相比于快速排序的划分算法计算topK，它无需一次性将数据读入内存，特别适合于处理海量数据
- 败者树和二路归并程序适合将若干有序数组进行归并排序，二路归并比较次数一般为1次，而k路归并的败者树只需要比较k的对数次
- Bitmap适合判断某关键字是否在集合中，输出重复元素，输出出现几次的数字，处理的文件如果有海量的数据一般结合hash_map将大文件拆分为若干个不同的小文件，再依次处理
- Bloom filter是一种节省空间的随机化数据结构，是Bitmap的扩展。它在能容忍低错误率的应用场合下，通过极少的错误换取了存储空间的极大节省，在数据库和网络应用中应用非常广泛(具体细节参考后面bitmap的介绍)
__EOF__
