9.1基本概念
结点的度——结点挂接的子树数；
树的度——所有结点度中的最大值；
树的深度——指所有结点中最大的层数；
注意区分完全二叉树与满二叉树。
完全二叉树：只有最后一层叶子不满，且全部集中在左边。
9.2二叉树性质
- 二叉树的第i层上至多有2i-1个结点。
- 深度为k的二叉树至多有2i-1个结点，至少有k个结点。
- 具有n个结点的完全二叉树的深度必为
+1。
- 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）。
例题：一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（ ）
解题过程：完全二叉树有5000个结点，则最后一个结点序号是5000，根据完全二叉树结点i和左右孩子关系知，左结点为2i必为偶数，右节点为2i+1必为奇数，所以本题中最后结点为左结点，其双亲结点为2500，且2500是最后一个非叶子结点，则二叉树度为2的结点有n2=2500-1个，叶子结点数n0=n2+1=2500个。故本题答案为2500。
9.3二叉树的存储
二叉树可以用顺序、链式两种存储方式，顺序存储浪费空间，适于存满二叉树和完全二叉树。方法为：现将二叉树转化为完全二叉树，再从根节点开始，按照层次依次将树中节点存储到数组即可。
一般二叉树建议用链式存储。特性：在n个结点的二叉链表中，必有2n个链域，有n+1个空指针域。
typedef struct BiNode{ //二叉链表
TElemType data;
struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;
9.4先序生成二叉树
int Create_BiTree(BTree &T){
char ch;
cin>>ch;
if(ch=='#'){
T=NULL;
return -1;
}else{
T=new BTNode;
T->data=ch;
Create_BiTree(T->lchild);
Create_BiTree(T->rchild);
}
return 0;
}
9.5遍历二叉树
三种遍历方式：
DLR—先序遍历，即先根再左再右
LDR—中序遍历，即先左再根再右
LRD—后序遍历，即先左再右再根
int PreTrav(BTree T){ //先序遍历举例
if(T) {
cout<<T->data<<' ';
PreTrav(T->lchild);
PreTrav(T->rchild);
}
return 0;
}
性质：由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
例题：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。
分析：
①由后序遍历特征，根结点必在后序序列尾部（A）；
②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（BDCE），其右部必全部是右子树子孙（FHG）；
③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。
9.6计算叶子结点个数
思路：二叉树的拓扑结构，涉及三种形式的结点（空点（树），叶子结点，中间结点）处理，算法还通常运用树左右孩子的递归，要考虑上述要素在不同场景中的运算逻辑。
如果将二叉树看成如下形式：
以A为根结点，左右孩子分别是B、F两棵子树。本例空点（树）返回0，叶结点返回1（计数为1），中间结点为做子树叶结点数+右子树叶结点数。
int CountBTLeafNode(BTree T){
int num;
if (!T){
return 0;
}else if(T->lchild==NULL && T->rchild==NULL){
return 1;
}else{
num=CountBTLeafNode(T->lchild)+CountBTLeafNode(T->rchild);
}
return num;
}
9.7求二叉树的深度
思路：同9.6的思想，空点返回0，叶结点返回1（深度为1），中间结点为左子树深度和右子树深度较大的那个。
int CountBTDepth(BTree T){
int mnum;
if(!T){return 0;
}else{
if(CountBTDepth(T->lchild)>CountBTDepth(T->rchild)){
mnum=CountBTDepth(T->lchild)+1;
}else{
mnum=CountBTDepth(T->rchild)+1;
}
}
return mnum;
}
二叉树深度算法是根据二叉树的拓扑结构结合递归而来。
9.8求二叉树的宽度
思路：二叉树的宽度是指二叉树各层结点个数的最大值。因为是统计各层，所以这里用到一种新的思路——层级遍历，并结合队列实现。队列暂存树父子结点，width记忆父节点的数量（也就是各层宽度）。初始化是根结点入队，随后就是不断出队直到队列为空，但是每次出队width都会减一，并将该结点的左右孩子入队，width减到0说明一个层级已遍历好，此时队列长度就是下一层的结点数（也就是宽度），更新width为队列长度，并进行下轮循环（直到队列为空）。maxwidth用来记忆最大的层级。
过程：
（1）初始根结点A层级为i=1，A入队，队列宽度width=1，maxwidth=1；
（2）出队A，width--，同时将A的左右孩子B和C入队，判断width=0，更新width为队列长度width=2，i（层级）自加为2，判断新width和maxwidth大小取大；
（3）出队B，width--，同时将B的左右孩子D和E入队，判断width=1不为零，继续出队C，width--，同时将C的左右孩子F入队，判读width=0，更新width为队列长度3，i自加为3，判断maxwidth取大；
（4）依次循环，直到队列为空；
int BTWidth(BTNode *b)
{
if(b == NULL) //为空树，返回宽度为0
return 0;
int width, max;
int i = 1, max_i; //初始化二叉树层次i，最大宽度所在层次max_i
BTNode *p;
SqQueue<BTree> qu;
Initial_SqQueue(qu); //初始化层次遍历需要借助的队列
Push_SqQueue(qu, b); //树不为空，根节点进队
width = 1; // 宽度置为1
max = width; //最大宽度为1
max_i = i; //最大宽度所在层次
while(!IfSqQueue_Empty(qu)) //队列为空，表明二叉树遍历完毕，退出循环
{
Pop_SqQueue(qu, p); //节点出队，赋给p
width --; //出队一次，width减1
if(p -> lchild != NULL) //出队节点的左孩子进队
Push_SqQueue(qu, p -> lchild);
if(p -> rchild != NULL)
Push_SqQueue(qu, p -> rchild); //出队节点的右孩子出队
if(width == 0) //width == 0，表示当前层次i所有节点已遍历完毕
{ //此时队列元素个数即为下一层次 i + 1 的节点个数
width = SqQueue_Length(qu); //更新宽度
i++; //层次变为下一层 i + 1
if(width > max) //如果层次 i + 1 宽度 > max
{
max = width; //更新max
max_i = i; //并记录最大宽度所在层次
}
}
}
printf("二叉树层次 %d 的宽度最大\n", max_i);
return max;
}
9.9复制二叉树
思路：先复制根结点，再复制左右子树。
int CopyBTree(BTree NT,BTree T){
if(!T){NT=NULL;return 0;
}else{
NT=new BTree;
NT->data=T->data;
CopyBTree(NT->lchild,T->lchild);
CopyBTree(NT->rchild,T->rchild);
}
}
9.10判断二叉树是否相等
思路：空点（树）只有同时为空时才相等，非空结点（树）先判断根结点data是否相等，然后是左子树是否相等，再是右子树是否相等（递归），也就是采用先序遍历的方式。
int IsSame(BTree T1,BTree T2){
if(T1==NULL&&T2==NULL){
return 1;
}else if(T1==NULL||T2==NULL){
return 0;
}else if(T1->data ==T2->data){
if(!IsSame(T1->lchild,T2->lchild)){
return 0;
}
if(!IsSame(T1->rchild,T2->rchild)){
return 0;
}
return 1;
}else{
return 0;
}
}
9.11交换二叉树每个结点的左右孩子
思路：要交换左右孩子（子树）前提是根结点要存在，此外对于叶子结点没有交换的必要。
int ChangeLR(BTree &T)
{
BTree temp;
if(T->lchild==NULL&&T->rchild==NULL)
return 0;
else
{
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}//交换左右孩子
ChangeLR(T->lchild); //递归交换左子树
ChangeLR(T->rchild); //递归交换右子树
}
9.12输出二叉树中从每个叶子结点到根结点的路径
思路：先序遍历二叉树，当发现叶子结点时输出路径序列。先序遍历一定是先遍历出最左端的叶子结点路径，用数组v[num]记录遍历中各结点的data，用len记忆遍历递归次数，当达到最左端叶子结点时，先输出其data，再输出数组中的序列。后面的遍历都是根据当前递归层级的len初始，去继续修改v[num]数组，当达到叶子结点时输出序列。
int LeafNodePath(BTree T,char *v,int len){
if(!T){
return 0;
}else if(T->lchild==NULL&&T->rchild==NULL){
printf("%c",T->data);
for(int i=len;i>=0;i--){
printf("%c",v[i-1]);
}
printf("\n");
return 0;
}else{
v[len]=T->data;len++;
LeafNodePath(T->lchild,v,len);
LeafNodePath(T->rchild,v,len);
}
return 0;
}
9.13求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值
思路：9.11我们已经实现各叶子结点路径遍历，只要再增加变量maxpath[num]和maxlen，当达到叶子结点时不是执行打印，而是比较v和maxpath的数组长度，若v大则将v数组复制到maxpath。
int MaxPath(BTree T,char *v,int len,char *maxpath,int &maxlen){
if(!T){
return 0;
}else if(T->lchild==NULL&&T->rchild==NULL){
v[len]=T->data;
if(len+1>maxlen){
maxlen=len+1;
for(int i=0;i<maxlen;i++){
maxpath[i]=v[len-i];
}
}
return 0;
}else{
v[len]=T->data;len++;
MaxPath(T->lchild,v,len,maxpath,maxlen);
MaxPath(T->rchild,v,len,maxpath,maxlen);
}
return 0;
}
9.14二叉树和树的相互转换
9.14.1树转换为二叉树
树转化为二叉树用的是孩子兄弟表示法，即二叉树结点的左孩子为树结点的第一个孩子，二叉树结点右孩子为树结点的第一个兄弟。
结构：
示例：
9.14.2二叉树转换为树
示例：
9.14.3森林转换为二叉树
森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
示例：
9.15哈夫曼树
带权路径长度最小的树。核心思想：使权大的结点靠近根。
性质：
一棵有n个叶子结点的Huffman树有2n-1个结点。因为从哈夫曼树形成来看，初始结点最终一定在叶子的位置，上面都是新增的结点，4个结点的哈夫曼树最终一定新增三个结点。
构造过程：
哈夫曼结点和哈夫曼树定义：
typedef struct HFNode{
int weight;
int lchild,rchild,parent;
}HFNode;
typedef struct HFTree{
HFNode *v;
int len;
}HFTree;
哈夫曼树的构建：
HFTree Create_HFTree(int V[],int num){//V[]为权值序列
HFTree HF;int i;
HF.len=2*num-1;
HF.v=new HFNode[HF.len];
//第一步，构造num棵树，初始化
for (i=0;i<num;i++){
HF.v[i].weight=V[i];
HF.v[i].lchild=HF.v[i].rchild=HF.v[i].parent=0;
}
//第二步，选择权值最小两棵树，形成新的树
int s1,s2;
for (i;i<HF.len;i++){
SelectNode(HF,i,s1,s2);
HF.v[i].lchild=s1;
HF.v[i].rchild=s2;
HF.v[s1].parent=i;
HF.v[s2].parent=i;
HF.v[i].weight=HF.v[s1].weight+HF.v[s2].weight;
}
return HF;
}
说明1：SelectNode()有两个返回值s1和s2，C语言不支持两个返回值的写法s1,s2=SelectNode(HF,i)，只能用示例传参引用的方式实现。
说明2：C语言二维数组定义时必须指定第二维的大小，当函数形参为二维数组时也是如此，传参和形参在第二维定义同样大小才能正常传值。
此外，C语言二维数组不能像一维数组那样返回，较易出错，遇到需要返回尽量避免使用二维数组。
第二步选择权值最小两棵树SelectNode()的实现：
int SelectNode(HFTree HF,int len,int &s1,int &s2){
int j;
//把遇到第一个树(parent==0)序号设为s1
for(j=0;j<len;j++){
if(HF.v[j].parent==0){
s1=j;break;
}
}
//把遇到第二个树序号设为s2
for(j=j+1;j<len;j++){
if(HF.v[j].parent==0){
s2=j;break;//易错
}
}
//比较s1和s2，把s1置为权重较小那个
int swap;
if(HF.v[s1].weight>HF.v[s2].weight){
swap=s1;
s1=s2;
s2=swap;
}
//继续遍历树，如果权重小于s1，将s1置于该树，s2置于s1；
//如果权重大于s1小于s2，将s2置于该树；如果大于s2则继续遍历
for(j=j+1;j<len;j++){
if(HF.v[j].parent==0){
if(HF.v[j].weight<HF.v[s1].weight){
s2=s1;s1=j;
}else if(HF.v[j].weight>HF.v[s1].weight&&HF.v[j].weight<HF.v[s2].weight){
s2=j;
}
}
}
return 0;
}
哈夫曼树构建好后，哈夫曼编码同9.12输出各叶子结点路径，但实现过程中发现教科书上哈夫曼树并不是严格按左子树比右子树小，或左子树比右子树大来的，而我的算法是严格限定的，所以不知道这里有什么问题，对哈夫曼树的定义也产生疑问。
哈夫曼树其实就是实现下面这张表：
哈夫曼译码就是依次读入文件的二进制码，从根结点触发，若遇0走向左子树，遇1走向右子树，若达到叶子节点则输出叶子字符，再从根结点开始读入二进制码。
9.16线索化二叉树
含n个结点的二叉链表共有2n个链域，其中非空链域为n-1个，空链域n+1，因此，提出了一种方法，利用原来的空链域存放指针（线索），指向树中其他结点，这样二叉树不用递归就可以完成前序、中序、后续遍历，快速找到某结点的前驱和后继，方便插入、删除操作，而且不采用[堆栈]处理，速度较一般二叉树的遍历速度更快，且节约存储空间。
