二叉树是一种树形结构，它的特点是每个结点之多只有二棵子树，并且，二叉树子树有左右之分，其次序不能任意颠倒。
1、二叉树的存储结构
(1) 顺序存储
#define MAX_TREE_SIZE 100 // 二叉树最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点
SqBiTree bt;
(2) 链式存储
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
2、获得二叉树的深度
(1) 顺序结构
返回二叉树的深度
int BiTreeDepth( SqBiTree T )
{
int i, j = -1;
for(i = MAX_TREE_SIZE-1; i >= 0; i--) // 找最后一个结点
{
if(T[i] != 0) // 0表示空结点
break;
}
i++; // 完全二叉树的结点总数
do{
j++;
}while(i >= pow(2,j)); // 计算2的j次幂
return j;
}
注意：pow(int a, int b)表示a的b次方。空树的深度为0。
(2)链式结构
返回二叉树的深度
int BiTreeDepth( BiTree T )
{
int i, j;
if(!T) // 树为空，深度为0
return 0;
if(T -> lchild) // 左子树存在，则返回左子树的深度
i = BiTreeDepth(T -> lchild);
else
i = 0; // 左子树不存在
if(T -> rchild) // 右子树存在，则返回右子树的深度
j = BiTreeDepth(T -> rchild);
else // 右子树不存在
j = 0;
return i > j ? i + 1 : j + 1; // 比较左右子树深度，返回较大值+1
}
注意：本程序采用递归方式，先计算左子树深度，再计算右子树深度，选一个较大的值，然后加上根的深度1，得到树的深度。
3、中序遍历二叉树
(1)递归形式
void InOrderTraverse( BiTree T, Status(*Visit)(TElemType) )
{
if(T)
{
InOrderTraverse(T -> lchild, Visit); // 先中序遍历左子树
Visit(T -> data); // 再访问根结点
InOrderTraverse(T -> rchild, Visit); // 最后中序遍历右子树
}
}
(2)非递归形式
算法一：
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
InitStack(S); Push(S, T); // 根指针进栈
while(!StackEmpty(S))
{
while(GetTop(S,p) && p) // 指针不空则一直向左走
Push(S, p -> lchild); // 左子树不断压栈，直到左子树为空
Pop(S, p); // 将空指针退栈
if(!StackEmpty(S)) // 栈不空则出栈访问
{
Pop(S, p); // p指向当前要遍历的根结点
if(!Visit(p -> data)); // 访问栈顶元素
return ERROR;
Push(S, p -> rchild); // 将栈顶元素的右子树压栈
}
}
return OK;
}
算法二：
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
InitStack(S); p = T;
while(p || !StackEmpty(S))
{
if(p) // 根指针进栈，遍历左子树
{
Push(S, p);
p = p -> lchild;
}
else // 根指针退栈，访问根结点，遍历右子树
{
Pop(S, p);
if(!Visit(p -> data))
return ERROR;
p = p -> rchild;
}
}
return OK;
}
4、层次遍历二叉树
(1)顺序结构
void LevelOrderTraverse(SqBiTree T, Status (*Visit)(TElemType))
{
int i = MAX_TREE_SIZE - 1, j;
while(T[i] == 0) // 找到最后一个非空结点的序号
i --;
for(j = 0; j <= i; j ++) // 从根结点起，按层次遍历二叉树
if(T[j] != 0) // 只遍历非空结点
Visit(T[j]);
}
(2)链式结构
typedef struct BiTNode // 二叉树结点
{
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
typedef struct QNode // 链队结点
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct // 链队
{
QueuePtr front,rear; // 队头、队尾指针
}LinkQueue;
void LevelOrderTraverse(BiTree T, Status (*Visit)(TElemType))
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q); // 初始化空队
EnQueue(&q, T); // 根指针入队
while(!QueueEmpty(q))
{
DeQueue(&q, &a);
Visit(a -> data); // 访问结点
if(a -> lchild != NULL) // 当前结点左孩子不空，则左孩子入队
EnQueue(&q, a -> lchild);
if(a -> rchild != NULL) // 当前结点右孩子不空，则右孩子入队
EnQueue(&q, a -> rchild);
}
}
}
5、建立二叉树
输入结点序列建立二叉树。
Status CreateBiTree(BiTree &T)
{
scanf("%c", &ch);
if(ch == ' ') T = NULL;
else
{
if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T -> data = ch; // 生成根结点
CreateBiTree(T -> lchild); // 构造左子树
CreateBiTree(T -> rchild); // 构造右子树
}
return OK;
}
6、统计叶子结点数
void CountLeaf(BiTree T, int *count)
{
if(T != NULL)
{
if((T -> lchild == NULL) && (T -> rchild == NULL)) // 左右孩子为空的结点
(*count)++;
CountLeaf(T -> lchild, count);
CountLeaf(T -> rchild, count);
}
}
7、二叉树的二叉线索存储表示
typedef enum{ Link, Thread } PointerTag; // Link == 0:指针，Thread == 1:线索
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild, *rchild; // 左右孩子指针
PointerTag LTag, RTag; // 左右标志
}BiThrNode， *BiThrTree;
8、中序遍历线索二叉树
T指向头结点，头结点的lchild指向根结点。
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e))
{
p = T -> lchild; // p指向根结点
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; // 由于RTag为线索，所以rchild指向后继结点
Visit(p -> data);
}
p = p -> rchild; // 当RTag不是线索时，rchild指向右子树
}
return OK;
}
注意：遍历线索二叉树即是一个不多找后继的线性过程，类似于双向链表的遍历。
9、中序线索化二叉树
中序遍历二叉树，并将其线索化，Thrt指向头结点。令其lchild指向二叉树的根结点，rchild指向中序遍历时访问的最后一个结点。
BiThrTree pre; // 全局变量,始终指向刚刚访问过的结点
Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{
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; // pre指向头结点
InThreading(T); // 中序遍历进行中序线索化
pre -> rchild = Thrt; // 最后一个结点的右指针指向头结点
pre -> RTag = Thread; // 最后一个结点线索化
Thrt -> rchild = pre; // 头结点的右指针指向最后一个结点
}
return OK;
}
void InThreading(BiThrTree p)
{
if(p) // p指向当前结点
{
InThreading(p -> lchild); // 左子树线索化
if(!p -> lchild) // 左孩子为空
{
p -> LTag = Thread; // 左指针为线索，指向前驱结点
p -> lchild = pre;
}
if(!pre -> rchild) // 右孩子为空
{
pre -> RTag = Thread; // 右指针为线索，指向后继结点
pre -> rchild = p;
}
pre = p;
InThreading(p -> rchild); // 右子树线索化
}
}
注意：InThreading()函数为中序线索化函数。即，先线索化左子树，再线索化根结点，最后线索化右子树。
10、Huffman树和Huffman编码的存储表示
typedef struct
{
unsigned int weight; // 叶子结点的权值
unsigned int parent, lchild, rchild; //双亲、孩子结点的编号
}HTNode, *HuffmanTree; // 动态分配数组存储Huffman树
typedef char **HuffmanCode; // 动态分配数组存储Huffman编码表
11、Huffman编码算法一
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n)
{ // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
// n为赫夫曼树的叶子结点数
int m, i, s1, s2, start;
unsigned int c, f;
HuffmanTree p;
char *cd;
if(n <= 1) return;
m = 2 * n - 1; // m为赫夫曼树的总结点数
// 建立一张二维表，列字段为weight,parent,lchild,rchild。每行为一个结点信息，共m+1行，第0行未用
*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
for(p = *HT + 1, i = 1; i <= n; ++i, ++p, ++w) // 初始化赫夫曼树
{
(*p).weight = *w; // w存放n个字符的权值
(*p).parent = 0; // parent,lchild,rchild初始值为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]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(*HT, i-1, &s1, &s2);
(*HT)[s1].parent=(*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)); // 分配求编码的工作空间
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]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
注意：本算法首先根据所给结点和权值构造赫夫曼树，然后根据这个赫夫曼树从下至上进行编码。
12、Huffman编码算法二
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n)
{ // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
// n为赫夫曼树的叶子结点数
int m, i, s1, s2, start;
unsigned int c, f;
HuffmanTree p;
char *cd;
if(n <= 1) return;
m = 2 * n - 1; // m为赫夫曼树的总结点数
// 建立一张二维表，列字段为weight,parent,lchild,rchild。每行为一个结点信息，共m+1行，第0行未用
*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
for(p = *HT + 1, i = 1; i <= n; ++i, ++p, ++w) // 初始化赫夫曼树
{
(*p).weight = *w; // w存放n个字符的权值
(*p).parent = 0; // parent,lchild,rchild初始值为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]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(*HT, i-1, &s1, &s2);
(*HT)[s1].parent=(*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)); // 分配求编码的工作空间
c = m; cdlen = 0;
for(i = 1; i <= m; ++i)
(*HT)[i].weight = 0; // 遍历赫夫曼树时用作结点状态标志
while(c)
{
if((*HT)[c].weight == 0)
{ // 向左
(*HT)[c].weight = 1;
if((*HT)[c].lchild != 0)
{
c = (*HT)[c].lchild;
cd[cdlen++] = '0';
}
else if((*HT)[c].rchild == 0)
{ // 登记叶子结点的字符的编码
(*HC)[c] = (char *)malloc((cdlen + 1) * sizeof(char));
cd[cdlen] = '\0';
strcpy((*HC)[c], cd); // 复制编码(串)
}
}
else if((*HT)[c].weight == 1)
{ // 向右
(*HT)[c].weight = 2;
if((*HT)[c].rchild != 0)
{
c = (*HT)[c].rchild;
cd[cdlen++] = '1';
}
}
else
{ // HT[c].weight == 2,退回
(*HT)[c].weight = 0;
c = (*HT)[c].parent;
--cdlen; // 退到父结点,编码长度减1
}
}
free(cd);
}
注意：赫夫曼树构造完成后，遍历整个赫夫曼树，求各个叶子结点所表示的字符的赫夫曼编码。
