代码和思路参考自《数据结构》严老师版 P226-230

#include <stdio.h>
#include <malloc.h>

#define N 10		// 数据元素个数
#define Status int
#define true 1
#define false 0
typedef int KeyType;// 设关键字域为整型

typedef struct
{
	KeyType key;
	int others;
}ElemType;	// 数据元素类型

typedef ElemType TElemType;

typedef struct BiTNode
{
	// 二叉树的二叉链表存储表示 动态查找表(二叉排序树)
	TElemType data;
	struct BiTNode *lchild,*rchild;	// 左右孩子指针
}BiTNode,*BiTree;

Status InitDSTable(BiTree *DT)
{
	// 构造一个空的动态查找表DT
	*DT = NULL;
	return true;
}

void DestroyDSTable(BiTree *DT)
{
	// 销毁动态查找表
	if(*DT)// 非空树
	{
		if((*DT)->lchild)	// 有左孩子
			DestroyDSTable(&(*DT)->lchild);	// 销毁左孩子子树
		if((*DT)->rchild)	// 有右孩子
			DestroyDSTable(&(*DT)->rchild);	// 销毁右孩子子树
		free(*DT);	// 释放根结点
		*DT = NULL;	// 空指针赋0
	}
}

BiTree SearchBST(BiTree T,KeyType key)
{
	// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
	// 若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
	if((!T) || key == T->data.key)
		return T;
	else if (key < T->data.key)
		return SearchBST(T->lchild,key);
	else
		return SearchBST(T->rchild,key);
}

Status SearchBST1(BiTree T,KeyType key,BiTree f,BiTree *p)
{
	// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
	// 若查找成功,则返回指针p指向该数据元素指针结点,并返回TRUE,否则指针p
	// 指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL
	if (!T)
	{
		*p = f;
		return false;
	}
	else if (key == T->data.key)
	{
		*p = T;
		return true;
	}
	else if (key < T->data.key)
	{
		return SearchBST1(T->lchild,key,T,p);
	}
	else
	{
		return SearchBST1(T->rchild,key,T,p);
	}
}

int InsertBST(BiTree *T,ElemType e)
{
	BiTree p,s;

	if (!SearchBST1(*T,e.key,NULL,&p))	// 查找不成功
	{
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = e;
		s->lchild = s->rchild = NULL;
		if (!p)
		{
			*T = s;	// 被插结点*s为新的根结点
		}
		else if (e.key < p->data.key)
		{
			p->lchild = s;	// 被插结点*s为左孩子,值小的在左边
		}
		else
		{
			p->rchild = s;	// 被插结点*s为右孩子,值小的在右边
		}
		return true;
	}
	else
		return false;		// 书中已经有关键字相同的结点,不再插入
}

Status Delete(BiTree *p)
{
	// 从二叉排序树中删除结点p,并重接的左或右子树
	BiTree q,s;
	if (!(*p)->rchild)
	{
		// 右子树空则只需重接他的左子树
		q = (*p);
		*p = (*p)->lchild;
		free(q);
	}
	else if (!(*p)->lchild)
	{
		// 只需重接他的右子树
		q = (*p);
		*p = (*p)->rchild;
		free(q);
	}
	else
	{
		// 左右子树均不空	P230 方式d
		q = *p; s = (*p)->lchild;
		while(s->rchild){
			q = s;
			s = s->rchild;
		}
		(*p)->data = s->data;

		// s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值）
		if (q!=*p)
		{
			// 此种情况是指类似只有左右两个子结点的情况,类似情况下不需改变p->data = s->data已经完成所需改变
			q->rchild = s->lchild;
		}
		else
		{
			q->lchild = s->lchild;
		}
		free(s);
	}
	return true;
}

Status DeleteBST(BiTree *T,KeyType key)
{
	// 若二叉排序树T存在关键字等于key的数据元素的时候,则删除该数据元素结点
	// 并返回true,否则返回false
	if (!*T)
	{
		return false;
	}
	else
	{
		if (key == (*T)->data.key)
		{
			return Delete(T);
		}
		else if (key < (*T)->data.key)
		{
			return DeleteBST(&(*T)->lchild,key);
		}
		else
		{
			DeleteBST(&(*T)->rchild,key);
		}
		return 1;
	}
}

void TraverseDSTable(BiTree DT,void(*Visit)(ElemType))
{
	if (DT)
	{
		TraverseDSTable(DT->lchild,Visit);	// 先中序遍历左子树
		Visit(DT->data);					// 再访问根结点
		TraverseDSTable(DT->rchild,Visit);	// 最后中序遍历右子树
	}
}

void print(ElemType c)
{
	printf("(%d,%d)",c.key,c.others);
}

int main()
{
	BiTree dt,p;
	int i;
	KeyType j;

	ElemType r[N]={
		{45,1},{12,2},{53,3},{3,4},{37,5},{24,6},
		{100,7},{61,8},{90,9},{78,10}
	}; // 以教科书P227图9.7(a)为例 

	InitDSTable(&dt); // 构造空表

	for(i=0;i<N;i++)
		InsertBST(&dt,r[i]); // 依次插入数据元素 

	TraverseDSTable(dt,print);
	printf("\n请输入待查找的值:");
	scanf("%d",&j);
	p = SearchBST(dt,j);

	if (p)
	{
		printf("表中存在此值:");
		DeleteBST(&dt,j);
		printf("删除此值后:\n");
		TraverseDSTable(dt,print);
		printf("\n");
	}

	return 0;

}

思路参考自《数据结构》严老师版 P150
这版代码使用链表实现的 插入和删除的时候有优势 但是计算长度的时候就比较麻烦了。

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW   -2

#define ElemType int
#define Status   int

#define LIST_INIT_SIZE 100      // 线性表存储空间的初始分配量
#define LISTINCREMENT  10       // 线性表存储空间的分配增量

typedef struct LNode
{
	ElemType data;              // 存储的数据
	struct LNode *next;         // 后继的结点指针
}LNode,*LinkList;

void InitList(LinkList *L)
{
	// InitList_L即CreateList_L
	// 顺序(头插法)n个元素的值,建立带表头结点的单链线性表L
	int i;
	LNode *p;
	(*L) = (LinkList)malloc(sizeof(LNode));
	(*L)->next = NULL;      // 先建立一个带头结点的单链表

} // InitList

int ListLength(LinkList L)
{
	// 计算链表长度
	int i=0;
	LinkList p = L->next;
	while(p)
	{
		i++;            // 存在加1
		p = p->next; // 指向下一个结点
	}
	return i;
} // ListLength

Status GetElem(LinkList L,int i,ElemType *e)
{
	LNode *p;
	int j;
	// L为带头结点的单链表的头指针
	// 当第i个元素存在时，其值赋给e并返回OK,否则返回false
	p = L->next; j = 1;          // 初始化,p指向第一个结点,j为计数器

	while(p && j < i)
	{
		p = p->next; ++j;
	}

	if(!p || j>i)
		return ERROR;           // 第i个元素不存在

	*e = p->data;             // 取第i个元素
	return OK;
} // GetElem

Status ListInsert(LinkList *L,int i,ElemType e)
{
	LinkList p; int j;
	LinkList s = (LinkList)malloc(sizeof(LNode));   // 生成新结点
	// 在带头结点的单链线性表L中第i个位置之前插入元素e
	p = (*L); j = 0;
	while(p && j < i-1)
	{
		p = p->next; ++j;        // 寻找第i-1个结点
	}

	if(!p||j>i-1)
		return ERROR;           // i小于1或者大于表长+1

	s->data = e; s->next = p->next;                // 插入L中
	p->next = s;

	return OK;

} // ListInsert

Status ListDelete(LinkList *L,int i,ElemType *e)
{
	LinkList p,q; int j;
	// 在带头结点的单链线性表L中,删除第i个元素，并由e返回其值
	p = (*L); j = 0;
	while(p->next && j<i-1)
	{
		// 寻找第i个结点,并令p指向其前趋
		p = p->next; ++j;
	}

	if((!p->next) || j > i-1)
		return ERROR;           // 删除位置不合理

	q = p->next; p->next = q->next;    // 删除并释放结点
	*e = q->data; free(q);

	return OK;

} // ListDelete

void Output(LinkList L){
	int e,i = 1;

	int length = ListLength(L);

	for( i;i<=length;++i)
	{
		GetElem(L,i,&e);
		printf("%d ",e);
	}

	// 输出空集
	if (!length)
	{
		printf("Empty");
	}

	printf("\n");

	return OK;
}

// 算法6.15 P150
// 线性表A表示集合A，线性表B表示幂集ρ(A)的一个元素。
// 局部量k为进入函数时表B的当前长度。
// 第一次调用本函数时，B为空表，i＝1。
void GetPowerSet(int i, LinkList A, LinkList *B) {
   ElemType x;
   int k;
   if (i > ListLength(A))
	   Output(*B); // 输出当前B值，即ρ(A)的一个元素
   else {
      GetElem(A, i, &x);
	  k = ListLength(*B);
      ListInsert(B, k+1, x);
	  GetPowerSet(i+1, A, B);
      ListDelete(B, k+1, &x);
	  GetPowerSet(i+1, A, B);
   }
}

int main(){
	int n,i;
	ElemType e;
	LinkList a,b;

	printf("请输入集合A的元素个数:\n");
	scanf("%d",&n);
	InitList(&a);

	printf("请输入集合中的元素:\n");
	for(i=1;i<=n;i++){
		scanf("%d",&e);
		ListInsert(&a,i,e);
	}
	InitList(&b);
	printf("进行冥集合运算!\n");
	GetPowerSet(1, a, &b);
	return 0;
}
/*
请输入集合A的元素个数：
3
请输入集合A的元素：(空格区分)
1 2 3
*/

思路参考自《数据结构》严老师版 P144-149
实现了两种建树的算法
1.从叶子到根逆向求每个字符的赫夫曼编码
2.从根到叶子正向求每个字符的赫夫曼编码

#include <stdio.h>
#include <memory.h>
#include <limits.h>

typedef struct
{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;	// 动态分配数组存储赫夫曼数

typedef char** HuffmanCode;	// 动态分配数组存储赫夫曼编码树

// 函数void select()调用
int min1(HuffmanTree t,int i)
{
	int j,flag;
	unsigned int k=UINT_MAX; // 取k为不小于可能的值
	for(j = 1; j <= i; j++)
	{
		if(t[j].weight < k && t[j].parent == 0)
			k = t[j].weight,flag = j;
	}
	t[flag].parent=1;
	return flag;
}

// s1为最小的两个值中序号小的那个
void Select(HuffmanTree t,int i,int *s1,int *s2)
{
	int j;
	*s1=min1(t,i);
	*s2=min1(t,i);
	if(*s1 > *s2)
	{
		j=*s1;
		*s1=*s2;
		*s2=j;
	}
}

void HuffmanCoding_FromLeaf(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
{
	// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
	int m,s1,s2,i,start;
	unsigned int c,f;
	HuffmanTree p;
	char * cd;

	if (n <= 1)
		return;

	m = 2*n-1;
	*HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));	// 0号单元未用

	for (p = *HT+1,i=1;i<=n;++i,++p,++w)
	{
		(*p).weight=*w;
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}

	for(;i<=m;++i,++p)	//初始化双亲位置
		(*p).parent=0;

	for (i = n+1;i <=m;++i)
	{	// 建赫夫曼树
		// 在HT[1...i-1]
		Select(*HT,i-1,&s1,&s2);
		(*HT)[s1].parent = i; (*HT)[s2].parent = i;
		(*HT)[i].lchild = s1; (*HT)[i].rchild = s2;
		(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
	}

	// 从叶子到根逆向求每个字符的赫夫曼编码
	*HC = (HuffmanCode)malloc((n+1)*sizeof(char *));// 分配n个字符编码的头指针向量
	cd = (char *)malloc(n*sizeof(char));			// 分配求编码的工作空间
	cd[n-1] = '\0';
	for (i=1;i<=n;++i)
	{
		start = n-1;
		for (c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)	// 从叶子到根逆向求编码
		{
			if((*HT)[f].lchild == c) cd[--start] = '0';
			else cd[--start] = '1';
		}

		(*HC)[i] = (char *)malloc((n-start)*sizeof(char));		// 为第i个字符分配空间
		strcpy((*HC)[i],&cd[start]);
	}
	free(cd);	// 释放工作空间
}

void HuffmanCoding_FromRoot(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
{
	// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
	int m,s1,s2,i,start,cdlen,index;
	unsigned int c,f;
	HuffmanTree p;
	char * cd;

	if (n <= 1)
		return;

	m = 2*n-1;
	*HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));	// 0号单元未用

	for (p = *HT+1,i=1;i<=n;++i,++p,++w)
	{
		(*p).weight=*w;
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}

	for(;i<=m;++i,++p)	//初始化双亲位置
		(*p).parent=0;

	for (i = n+1;i <=m;++i)
	{	// 建赫夫曼树
		// 在HT[1...i-1]
		Select(*HT,i-1,&s1,&s2);
		(*HT)[s1].parent = i; (*HT)[s2].parent = i;
		(*HT)[i].lchild = s1; (*HT)[i].rchild = s2;
		(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
	}

	// 从根到叶子正向求每个字符的赫夫曼编码
	*HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
	// 分配n个字符编码的头指针向量([0]不用)
	cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
	index = m; cdlen = 0;
	for (i=1;i<=m;++i)	(*HT)[i].weight = 0;	// 遍历赫夫曼树时用作结点状态标识

	while (index)
	{
		if ((*HT)[index].weight == 0)	// 向左
		{
			(*HT)[index].weight = 1;
			if ((*HT)[index].lchild != 0)
			{
				index = (*HT)[index].lchild;
				cd[cdlen++] = '0';
			}
			else if ((*HT)[index].rchild == 0)
			{
				// 等级叶子结点的字符的编码
				(*HC)[index] = (char *)malloc((cdlen+1)*sizeof(char));
				cd[cdlen] = '\0';
				strcpy((*HC)[index],cd);	// 复制编码(串)
			}
		}
		else if ((*HT)[index].weight == 1)	// 向右
		{
			(*HT)[index].weight = 2;
			if ((*HT)[index].rchild != 0)
			{
				index = (*HT)[index].rchild;
				cd[cdlen++]="1";
			}
		}
		else
		{
			// HT[p].weight == 2 退回
			(*HT)[index].weight = 0;
			index = (*HT)[index].parent; --cdlen;// 退回到父结点,编码长度减1
		}
	}
	free(cd);
}

int main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int *w,n,i;
	freopen("1.txt","r",stdin);

	printf("请输入权值的个数(>1):");
	scanf("%d",&n);
	w=(int*)malloc(n*sizeof(int));
	printf("请依次输入%d个权值(整型):\n",n);
	for(i=0;i<=n-1;i++)
		scanf("%d",w+i);
	HuffmanCoding_FromRoot(&HT,&HC,w,n);
	for(i=1;i<=n;i++)
		puts(HC[i]);

	return 0;
}
/*
测试数据
8
5 29 7 8 14 23 3 11

*/

代码参考自: 《数据结构》严蔚敏版 P132-135

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TElemType char
#define Status int
#define OVERFLOW -2
#define true	1
#define OK		1
#define false	0
#define ERROR	-1

typedef enum PointerTag { Link,Thread};	// Link == 0:指针,Thread == 1:线索

// --------------二叉树的二叉链表存储表示------------------
typedef struct BiThrNode
{
	TElemType		 data;
	struct BiThrNode *lchild,*rchild;	// 左右孩子指针
	enum PointerTag	 LTag,RTag;			// 左右标志
}BiThrNode,*BiThrTree;

TElemType Nil = '-';
BiThrTree pre; // 全局变量,始终指向刚刚访问过的结点 

//--------------各种visit()--------------------------------
Status PrintOrderTraverse(TElemType e)
{
	printf("%c ",e);
	return OK;
} // PrintOrderTraverse

//---------------二叉线索树的基本操作函数原型说明--------------
Status CreateBiThrTree(BiThrTree *T)
{
	// 按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
	// 构造二叉链表表示的二叉树
	TElemType ch;
	scanf("%c",&ch);
	if(ch == Nil)
		*T = NULL;
	else
	{
		if(!(*T = (BiThrNode *)malloc(sizeof(BiThrNode))))	exit(OVERFLOW);
		(*T)->data = ch;	// 生成根结点

		CreateBiThrTree(&(*T)->lchild);	// 构造左子树
		if((*T)->lchild) // 有左孩子
			(*T)->LTag=Link;
		else
			(*T)->LTag=Thread;

		CreateBiThrTree(&(*T)->rchild);	// 构造右子树
		if((*T)->rchild) // 有右孩子
			(*T)->RTag=Link;
		else
			(*T)->RTag=Thread;
	}

	return OK;
} // CreateBiTree

Status InOrderTraverse_Thr(BiThrTree T,Status (*Visit)(TElemType e))
{
	// T 指向头结点,头结点的左链lchild指向根结点,可参见线索化算法
	// 中序遍历二叉线索树T的非递归算法,对每个数据元素调用函数Visit
	BiThrTree p;
	p = T->lchild;	// 带有头结点,左子树指向根结点

	while(p!=T)		// 空树或者遍历结束时 p == T
	{
		while(p->LTag == Link)
			p = p->lchild;
		if(!Visit(p->data)) return ERROR;	// 访问其左子树为空的结点
		while(p->RTag == Thread && p->rchild != T)
		{
			p = p->rchild;	Visit(p->data);	// 访问后继结点
		}
		p = p->rchild;
	}

	return OK;
} // InOrderTraverse_Thr

void InThreading(BiThrTree p)
{
	if(p)
	{
		InThreading(p->lchild);		// 左子树线索化
		if(!p->lchild)
		{
			// 前缀线索
			p->LTag = Thread;
			p->lchild = pre;
		}
		if(!pre->rchild)
		{
			// 后继线索
			pre->RTag = Thread;
			pre->rchild = p;
		}
		pre = p;					// 保持pre指向p的前驱
		InThreading(p->rchild);		// 右子树线索化
	}
} // InThreading

Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{
	// 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点
	if(!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
	(*Thrt)->LTag = Link;	(*Thrt)->RTag = Thread;		// 建头结点
	(*Thrt)->rchild = *Thrt;							// 右指针回指
	if(!T)
		(*Thrt)->lchild = *Thrt;						// 若二叉树为空,则左指针回指
	else
	{
		(*Thrt)->lchild = T;	pre = (*Thrt);
		InThreading(T);									// 中序遍历进行中序线索化
		pre->rchild  = (*Thrt);pre->RTag = Thread;		// 最后一个结点线索化
		(*Thrt)->rchild  = pre;
	}
	return OK;
} // InOrderThreading

int main()
{
	BiThrTree bitree1,bitree2;
//	freopen("1.txt","r",stdin);
	CreateBiThrTree(&bitree2);
	// 二叉树线索化
	InOrderThreading(&bitree1,bitree2);
	// 中序线索遍历
	InOrderTraverse_Thr(bitree1,PrintOrderTraverse);
	printf("\n");

	return 0;
}

测试数据:

ABC--DE-G--F---