数据结构 第四天 （树#二叉树）
树与二叉树
一、树的定义：
1、定义：树（Tree）是n（n>=0）个节点的有限集，n=0时称为“空树”。在任意一棵非空树中：
⒈有且仅有一个特定的称为根（root）的节点。
⒉当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1、T2……Tm，其中每一个集合本身又是一棵树，并且称之为根的子树（SubTree）。
注意：
⒈n>0时根节点是唯一的，不可能存在多个根节点。
⒉m>0时，子树个数没有限制，但一定互不相交。
2、树的节点的分类：
树的节点包含一个数据元素以及若干个指向其子树的分支。节点拥有的子树个数称为节点的度（Degree）。度为0的节点称为叶节点（Leaf）；度不为0且不为根节点的节点称为“内部节点”。
3、节点间关系：
节点的子树的根称为该节点的孩子（Child），相应地，该节点称为孩子的父（Parent，或翻译成“双亲”）。同一个父节点的孩子之间互称兄弟（Sibling）。
4、层次：
节点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层，依次类推。树中节点的最大层次称为树的深度（Depth）或高度。
如果该树中节点的子树看成是从左到右有次序的，不能互换的，则称该树为有序树，否则称为无序树。
二、二叉树
1、定义：二叉树（Binary Tree）是n（n>=0）个节点的有限集合，该集合或者为空集（称为“空二叉树”），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
定理：任意一棵树都可以完全等价于一棵二叉树。
2、二叉树的特点：
⒈每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。注意不是“只有”，而是“最多有”，即可以没有子树或只有一棵子树。
⒉左子树和右子树有序，不能随意颠倒。
⒊即使树中某节点只有一棵子树，也要区分它是左子树还是右子树，不能混淆。
3、二叉树的基本形态：
二叉树具有五种基本形态
⒈空二叉树
⒉只有一个根节点
⒊根节点只有左子树
⒋根节点只有右子树
⒌根节点既有左子树又有右子树
4、满二叉树：
在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：
⒈叶子节点只能出现在最下面一层。出现在其他层就不可能达到平衡。
⒉非叶子节点的度一定是2。
⒊在同样深度的二叉树中，满二叉树的节点个数最多，叶子节点个数最多。
5、完全二叉树：
对一棵具有n个节点的二叉树按层序编号，如果编号为i（1<=i<=n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
需要注意区分满二叉树与完全二叉树，满二叉树一定是一棵完全二叉树，而完全二叉树不一定是满的。
判定一棵二叉树是否是完全二叉树需要对该二叉树进行层序编号。
层序编号：以根节点作为起点，从左至右对每一层的节点进行编号。对该层的所有节点编号完毕后再对下一层的节点进行编号。
从这里我们也可以得到一些完全二叉树的特点：
⒈叶子节点只能出现在最下两层
⒉最下层的叶子节点一定集中在左部的连续位置
⒊倒数二层，若有叶子节点，一定都在右部连续位置
⒋如果节点度为1，则该节点只有左孩子，不存在只有右子树的情况
⒌同样节点数的二叉树，完全二叉树的深度最小
注意：同样节点数的二叉树，深度最小的二叉树不一定是完全二叉树
三、二叉树的性质
关于二叉树，有一些需要理解并记忆的特性，以便我们更好使用它
1、性质1：在二叉树的第i层上至多有2^(i-1)个节点（i>=1）。
2、性质2：深度为k的二叉树至多有2^k-1个节点（k>=1）。注意不是2^(k-1)。
3、性质3：对于任何一棵二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。
性质3的推导：
二叉树的节点的度只有3种：0、1、2。我们设其对应的节点数分别为n0、n1、n2，则二叉树的节点总数为：
Tn=n0+n1+n2
二叉树的连线数应等于节点个数减1，即
Sn=Tn-1
另一方面，二叉树的连线数应等于2*n2+n1，即
Sn=2*n2+n1
我们可得到：
n0+n1+n2-1=2*n2+n1
整理可得
n0=n2+1
若事先已知叶子节点个数，使用性质3可以快速计算出一个二叉树的度为2的节点个数，进而推出度为1的节点个数。
例：假设一个完全二叉树的总节点个数为699个，则叶子节点有几个？
答：350个。（没有n1）
四、二叉树的存储
二叉树在内存中是无法形象存储的，通常情况下我们可以使用顺序存储和链式存储两种结构来模拟双亲与孩子的逻辑关系从而存储二叉树。
1、顺序存储结构
顺序存储结构就是利用一维数组存储二叉树中的节点。将一个完全二叉树按层序编号的方式，可以得到节点编号与该节点的数据的一一对应关系，这样我们就可以使用数组来存储该完全二叉树了。
对于非完全二叉树，我们需要先将其补全为完全二叉树，再进行存储。后补的节点存储时数据为空（NULL）。考虑到一种极端情况，若有一棵深度为k的右斜树，只有k个节点，但根据存储方式我们需要建立一个2^k-1个存储单元。因此顺序存储一般不常用，仅用于存储完全二叉树。
2、链式存储结构
既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个节点最多有两个孩子，所以为它涉及一个数据域和两个指针域。
lchild︱data︱rchild
其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。
typedef struct BiTNode
{
data_t data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
如果需要，我们还可以再增加一个指向其父节点的指针域，这里不再赘述。
五、二叉树的遍历
二叉树的遍历（traversing）是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被且仅被访问一次。
二叉树的遍历方式有很多，常用的有前序遍历、中序遍历、后序遍历3种。
1、前序遍历（PreOrderTraverse）
规则：
⒈若二叉树为空，则不进行操作，返回
⒉访问根节点
⒊前序遍历左子树
⒋前序遍历右子树
2、中序遍历（InOrderTraverse）
规则：
⒈若二叉树为空，则不进行操作，返回
⒉中序遍历左子树
⒊访问根节点
⒋中序遍历右子树
3、后序遍历（PostOrderTraverse）
规则：
⒈若二叉树为空，则不进行操作，返回
⒉后序遍历左子树
⒊后序遍历右子树
⒋访问根节点
无论是前序遍历、中序遍历还是后序遍历，都使用到了递归的定义方法。
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERR 0
typedef char bt_data_t;
typedef struct make_tree_t
{
bt_data_t data;
struct make_tree_t *lchild;
struct make_tree_t *rchild;
}Tree;
Tree *CreateProTree(int i, char a[], int len)
{
int j;
Tree *root = NULL;
root = (Tree *)malloc(sizeof(Tree));
if(NULL == root)
{
printf("The Root Create Was Failed\n");
exit(0);
}
if('\0' == a[i])
{
exit(0);
}
root->data = a[i]; //根节点
printf("a[%d] = %c\n",i,a[i]);
j = 2*i; //左子树
if('\0' != a[j] && j <= len)
{
root->lchild = CreateProTree(j,a,len);
}
else
{
root->lchild = NULL;
}
j = 2*i + 1; //右子树
if('\0' != a[j] && j <= len)
{
root->rchild = CreateProTree(j,a,len);
}
else
{
root->rchild = NULL;
}
return root;
}
Tree *CreateCenTree(int i, char a[], int len)
{
int j;
Tree *root = NULL;
root = (Tree *)malloc(sizeof(Tree));
if(NULL == root)
{
printf("The Root Create Was Failed\n");
exit(0);
}
j = 2*i; //左子树
if('\0' != a[j] && j <= len)
{
root->lchild = CreateCenTree(j,a,len);
}
else
{
root->lchild = NULL;
}
if('\0' == a[i])
{
exit(0);
}
root->data = a[i]; //根节点
printf("a[%d] = %c\n",i,a[i]);
j = 2*i + 1; //右子树
if('\0' != a[j] && j <= len)
{
root->rchild = CreateCenTree(j,a,len);
}
else
{
root->rchild = NULL;
}
return root;
}
//前序遍历
void PreOrder(Tree *root)
{
if(NULL == root)
{
return;
}
printf("%c\t",root->data); //根
PreOrder(root->lchild); //左子树
PreOrder(root->rchild); //右子树
}
//中序遍历
void CenOrder(Tree *root)
{
if(NULL == root)
{
return;
}
CenOrder(root->lchild); //左子树
printf("%c\t",root->data); //根
CenOrder(root->rchild); //右子树
}
//后序遍历
void PostOrder(Tree *root)
{
if(NULL == root)
{
return;
}
PostOrder(root->lchild); //左子树
PostOrder(root->rchild); //右子树
printf("%c\t",root->data); //根
}
int main()
{
Tree *root = NULL;
bt_data_t a[] = {0,
'A',
'B', 'C',
'D','E', 0, 'F',
0,0,'G','H',0,0,'I'
};
root = CreateCenTree(1,a,sizeof(a)/sizeof(bt_data_t));
PreOrder(root);
printf("\n");
CenOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
return 0;
}练习：写出该二叉树的前序遍历、中序遍历、后序遍历的结果。
思考：我们为什么要研究这么多种不同的遍历方法呢？
答：我们用图形来表现树的结构十分直观和容易理解，但是对于计算机来说，它只能处理循环、分支等问题，也就是说，它只能处理线性问题。以上3种遍历方法都是人为地将二叉树变成某个有意义的线性序列，方便计算机处理。
练习1：有一棵二叉树，其前序遍历结果为ABDC，中序遍历结果为BDAC，画出该二叉树。
练习2：有一棵二叉树，其中序遍历结果为ABCDEFG，后序遍历结果为BDCAFGE，画出该二叉树并求其前序遍历的结果。
练习3：已知一棵二叉树的前序遍历结果为ABC，后序遍历的结果为CBA，画出该二叉树。
由以上三个练习我们可以得出：
⒈已知前序遍历和中序遍历，可以唯一确定一棵二叉树。
⒉已知中序遍历和后序遍历，可以唯一确定一棵二叉树。
⒊但已知前序遍历和后序遍历，无法唯一确定一棵二叉树。
进阶练习：还原二叉树
1）前序：ABDEGHCFI 中序：DBGEHACIF
2）中序：HDBEAIFCGJ 后序：HDEBIFJGCA
3）中序：BFDGACEH 后序：FGDBHECA
六、二叉树的建立
有了遍历方法，我们就可以在遍历过程中来创建一棵二叉树。
若我们要创建一棵二叉树，首先我们要对这棵二叉树进行扩展，将每个节点都补上一个虚拟的孩子节点，数据为空。这样我们通过遍历这个扩展二叉树得到遍历序列就可以创建这棵二叉树了。
示例：创建练习1中的二叉树
⒈首先对这棵二叉树进行扩展，补全其所有节点的孩子节点，数据为空（以#代替）
⒉得到该扩展二叉树的前序遍历为AB#D##C##
⒊通过前序遍历的方法，边遍历边创建这棵二叉树
其实创建二叉树，也是利用了递归的原理，只不过在原来应该打印节点的操作替换为生成节点的操作而已。
当然我们也可以使用中序遍历和后序遍历来创建二叉树。若这棵二叉树使用中序遍历来创建，则需要的序列为#B#D#A#C#；若使用后序遍历来创建，则需要的序列为###DB##CA。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char data_t;
typedef struct BiTNode
{
//int num;节点编号(可选)
data_t data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
char btree[]="AB#D##C##";//给定的遍历
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
BiTree CreateBiTree()//给定遍历结果（以前序为例）创建二叉树。遍历结果在全局变量数组btree中
{
data_t data;
static int i=0;//使用静态变量才能让不同层次的递归共用一个变量i从而得到btree内存储的值
if(!strlen(btree))
{
printf("Can't Create Empty Bitree.\n");
return NULL;
}
data = btree[i++];
if(data=='#')//#表示此节点为空
return NULL;
else
{
BiTree T = (BiTree)malloc(sizeof(BiTNode));
if(!T)
{
printf("CreateBiTree Error\n");
exit(0);
}
T->data = data;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
return T;
}
}
int main()
{
BiTree root = CreateBiTree();
printf("Preorder:\n");
PreOrderTraverse(root);
printf("\n");
printf("Inorder:\n");
InOrderTraverse(root);
printf("\n");
printf("Postorder:\n");
PostOrderTraverse(root);
printf("\n");
return 0;
}七、二叉树的应用——赫夫曼树与赫夫曼编码
1、赫夫曼树
赫夫曼（David Huffman，也译为“哈夫曼”），美国数学家，他在1952年发明了赫夫曼树与赫夫曼编码。赫夫曼编码是当代压缩和解压缩技术的基础。
我们通过一个具体的示例来体会一下什么叫赫夫曼树（Huffman Tree）。
给定一个成绩（0~100），输出所对应的分数段。我们可以通过以下代码来实现：
if(a<60)
printf("不及格\n");
else if(a<70)
printf("及格\n");
else if(a<80)
printf("中等\n");
else if(a<90)
printf("良\n");
else
printf("优\n");粗略来看没什么问题，但在通常情况下，学生成绩大致都分布在“良”和“中等”的分数段，处于两端的“优”和“不及格”反而很少：
不及格：5%
及格：15%
中等：40%
良：30%
优：10%
在这种情况下，若采用上面的程序，则判断数量最大的“中等”和“良”分数段时，都需要至少3次的比较才能得出结果，大大影响了程序的执行效率。
如果我们改进算法，将比利最高的“中等”或“良”作为首个判断条件，则可大大加快程序的执行效率。
if(a<80)
{
if(a<70)
{
if(a<60)
printf("不及格\n");
else
printf("及格\n");
}
else
printf("中等\n");
}
else
{
if(a<90)
printf("良\n");
else
printf("优\n");
}2、赫夫曼树的定义
我们可以将上文中的程序画成二叉树的形式，每个if分支都作为二叉树的两个子树，将概率标记到父节点到子节点的路径上。这样的树叫做带权（Weight）树。
从树中一个节点到另一个节点之间的边构成了两点之间的路径，路径上的权值之和叫做路径长度。树的路径长度就是从根节点出发到每一个节点的路径长度之和。如果考虑带权的二叉树，节点的带权路径长度等于从该点到根节点的路径长度乘以该点的权值的乘积。带权二叉树的路径长度为所有叶子节点的带权路径长度之和。
针对同一问题，不同的二叉树画法路径长度也不同，其中最小路径长度的树就叫做赫夫曼树。
3、构造一棵赫夫曼树
构造一棵赫夫曼树的流程如下：
⒈将所有叶子节点按权值大小有序排列。例如上文的成绩占比，我们可以排列成：
A5 E10 B15 D30 C40
⒉取前面两个最小的叶子节点作为兄弟节点，权值小的做左孩子，权值大的做右孩子，它们两个共用一个父节点N1，其父节点的权值为两个叶子节点的权值的和。得到：
N115 B15 D30 C40
⒊重复步骤2，将N1与B作为新的两个子节点，其父节点为N2，权值为30
N230 D30 C40
⒋重复步骤2，将N2与D作为新的两个子节点，其父节点为N3，权值为60
C40 N360
⒌重复步骤2，将C与N3作为新的两个子节点，由于这时所有节点都已构造完毕，因此其父节点就是该二叉树的根节点。
最后得到构造完成的赫夫曼树如图：
此时该二叉树的带权路径长度为WPL=40*1+30*2+15*3+10*4+5*4=205。
4、赫夫曼编码
其实构造赫夫曼树可不是为了解决程序效率低的问题，赫夫曼树的主要作用是用来构造赫夫曼编码，而赫夫曼编码则是为了解决当年远距离通信（主要是电报）的数据传输最优化问题。
例如：若有一个编码规则：
A 000
B 001
C 010
D 011
E 100
F 101
可以看出是简单的以二进制的方式进行编码。
若有以下报文：BADCADFEED
则按照以上编码规则编码后，获得编码为：001000011010000011101100100011
对方接收到报文编码后，按编码规则3位一分来解码即可。
事实上，英语中字母的使用频率是不同的，常用字母（如a e i o u等）使用频率特别高，而不常用字母（如j v z等）使用频率就低得多。如果我们能人为减少常见字母的编码长度，则整个报文长度都会缩短，这样既方便传输又节省了存储空间。
假设上文的编码规则中，各字母出现的额频率如下：
可以看到，如果我们能缩短字母A和E的编码长度，则我们就可以大大缩短报文长度。这种压缩效果在文本长度很长时效果会更加明显。
但是我们看到，所有编码都是以二进制（0/1）进行编码的，贸然缩短字母A和E的编码长度很容易引起混淆，若要设计这种长短不等的编码，必须使得任意字符的编码不能是其他字符编码的前缀。
我们可以使用上文构造赫夫曼树的方法来构造一个赫夫曼树：
假设在一个报文中，6个字母的出现频率如下：
A 27%
B 8%
C 15%
D 15%
E 30%
F 5%
则我们可以构造出如下的赫夫曼树：
构造完毕后，若从根节点出发，规定走向左子树的边编码为0，走向右子树的边编码为1，则我们就可以得到每个字母新的编码：
A 01
B 1001
C 101
D 00
E 11
F 1000
则使用新的编码规则后，对报文BADCADFEED获得新的报文编码如下：
1001010010101001000111100（新）
001000011010000011101100100011（旧）
大概缩短了17%。
而且我们发现，通过赫夫曼树构造出的赫夫曼编码，不会存在因编码长短不一而混淆的情况。
现代计算机程序中大部分的压缩文件算法都是基于赫夫曼编码改进而来的。1977年，Lempel-Ziv在对赫夫曼编码进行深度研究后，发表了“顺序数据压缩的一个通用算法（A Universal Algorithm for Sequential Data Compression ）”的论文，论文中描述的算法被后人称为LZ77算法。LZ77算法以及后续的衍生算法是现在一些通行的压缩包模式（ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR，7z等）的编码基础算法。
下一篇： 数据结构实验完结撒花之内部排序比较