一般地二叉树多用链式存储结构来描述元素的逻辑关系。通常情况下二叉树中的结点定义如下:
typedefstruct btree_node {void *item;struct btree_node *left;struct btree_node *right; } btree_node_t;
在一些不同的实际应用中，还可以增加某些指针域或者线索化标志，例如增加指向父结点的指针、左右线索化的标志。
另外如果你想区分二叉树结点和二叉树这种结构，不妨定义如下的二叉树结构(类似于STL中分离定义数据结构和元素结点的方法):
typedefstruct { btree_node_t*root;int n;int (*comp)(constvoid *,constvoid *); } btree_t; typedefvoid (*cb)(btree_node_t *);//定义访问结点的函数指针
其中n表示二叉树结点的个数，comp表示函数指针。使用函数指针comp因为数据类型使用的是通用指针，在进行查找等比较数据大小的操作时需要定义一个比较函数，在泛型数据结构的C实现中应用非常广泛。
二叉树常见的遍历次序有先序、中序、后序三种，其中序表示根结点在何时被访问。每种遍历算法都有对应的递归解法和非递归解法。它的非递归解法中使用了栈这种数据结构。每个遍历都有自身的特点：
二叉树还有一种层次序遍历，它是按自顶向下、自左向右的访问顺序来访问每个结点，它的实现使用了队列这种数据结构。
此外二叉树还有一种Morris遍历方法，和上面使用O(n)空间复杂度的方法不同，它只需要O(1)的空间复杂度。这个算法跟线索化二叉树很像，不过Morris遍历是一边建立线索一边访问数据，访问完后直接销毁线索，保持二叉树的不变。Morris算法的原则比较简单：借助所有叶结点的右指针(空指针)指向其后继节点，组成一个环，但由于第二次遍历到这个结点时，由于左子树已经遍历完了，就访问该结点。
总结下来，遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，例如求二叉树的深度(高度)、二叉树的叶子结点个数、求某层结点个数(或者树的最大宽度、分层输出结点)、判断二叉树是否相同或者是否为完全二叉树或者二叉排序树、求二叉树中结点的最大距离、由遍历序列重建二叉树等。
递归代码比较简单，就不具体解释了，实现如下:
/*先序遍历，递归*/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); }
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
实现如下:
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指针记录最近刚访问过的结点。当一直往左直到左孩子为空时,判断当前结点的右孩子是否为空或者是否已访问过
实现如下:
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); } }
A Morris中序遍历
步骤如下: 初始化当前节点cur为root节点
B Morris先序遍历
步骤如下: 初始化当前节点cur为root节点
C Morris后序遍历
Morris后续遍历稍微麻烦点：它必须保证在访问某个当前节点时，左右子树的所有左孩子必须先被访问;而右孩子的输出从底部往顶部逆向访问就行
步骤如下：设置一个虚拟根结点，记它的左孩子为root,即当前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); } }
一个unsigned int数能表示32个整数,整数从0开始,针对整数i:
i/32i%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))这里采用位掩码运算的方法完成这些操作，避免取模和除数运算，效率更高。
位示图的数据结构定义如下:
/*位示图数据结构定义*/ typedefstruct bitmap{ unsignedint *bits;int size;//整数个数大小 } bitmap_t;
位示图函数的功能测试如下:
#include"bitmap.h" #include<stdio.h> #include<stdlib.h>#define MAX 10000#define RAD_NUM 100int main(){/*接受大小为MAX的参数，创建一个位图*/ bitmap_t*bm=bitmap_alloc(MAX); unsignedint i; unsignedint 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++){ unsignedint 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);return0; }
核心的实现还是清除、设置和测试某个位，代码如下:
/*分配指定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)returnfalse;if( (bm->bits[i>>SHIFT]) & (1<<(i & MASK)))returntrue;returnfalse; }
在某些应用中，要将n个不同的元素分成一组不相交的集合。在这个集合上，有两个重要的操作: 找出给定的元素所属的集合和合并两个集合。再例如处理动态连通性问题，假定从输入中读取了一系列整数对，如果已知的数据可说明当前整数对是相连的，则忽略输出，因而需要设计一个数据结构来保存足够的的整数对信息，并用它们来判断一对新对象是否相连。
解决这种问题的数据结构称为并查集。下面我们将介绍4种不同的算法实现，它们均以对象标号为索引的id数组来确定两对象是否处在同一个集合中
A quick-find算法策略
find操作实现很快速，只需返回对象所在的集合标识；union操作即要遍历整个数组使得p所在的集合分量值都设置为q所在的集合分量值。
不等于id[q],所有和id[q]相等的元素的值变为id