目录

• 第五章 树和二叉树
  • 5.1树和二叉树的定义
    • 5.1.1树的定义
    • 5.1.2树的基本术语
    • 5.1.3二叉树的定义
      • 二叉树的五种基本形态
  • 5.2案例引入
  • 5.3 树和二叉树的抽象数据类型定义
    • 具体实现
  • 5.4二叉树的性质和存储结构
    • 5.4.1二叉树的性质
      • 两种特殊的二叉树
  • 5.4二叉树的存储结构
    • 5.4.1顺序存储结构
    • 5.4.2链式存储结构
  • 5.5遍历二叉树和线索二叉树
    • 5.5.1遍历二叉树
      • 先序遍历的顺序建立二叉链表
      • 复制二叉树
      • 计算二叉树的深度
      • 统计二叉树中结点的个数
  • 附本节代码
    • 5.5.2线索二叉树
      • 概念
      • 构造线索二叉树
      • 遍历线索二叉树
  • 5.6树和森林
    • 5.6.1树的存储结构
      • 双亲表示法
      • 孩子表示法
      • 孩子兄弟法（二叉树表示法）
    • 5.6.2森林与二叉树的转换
    • 5.6.3树和森林的遍历
      • 树的遍历
      • 森林的遍历
  • 5.7哈夫曼树及其应用
    • 5.7.1哈夫曼树的基本概念
    • 5.7.2哈夫曼树的构造算法
      • 哈夫曼树的构造过程
      • 哈夫曼树的实现
      • 构造哈夫曼树
    • 5.7.3哈夫曼编码

第五章 树和二叉树

5.1树和二叉树的定义

5.1.1树的定义

树是一种非线性结构，有一个前驱，但可能有多个后继结点，树是n个结点的有限集，当n=0的时候称为空树

1. 有且仅有一个称为根的结点
2. 除根节点以外的其余结点可分为m个互不相交有限集，其中每一个集合本身又是一棵树，称为根的子树，所以树的定义是递归的定义
3. 树可以用嵌套集合(a)，广义表(b)，凹入表示法(c)来表示

5.1.2树的基本术语

1. 结点：树中的一个独立单元，包含数据元素和指向子树的分支，根节点没有前驱结点
2. 结点的度：结点拥有子树的数目，分支的数目
3. 树的度：树内结点度的最大值
4. 叶子：度为0的结点，叶子结点也叫作终端结点
5. 非终端结点：有分支的结点，度不为0的结点，非终端结点也叫作内部结点
6. 双亲和孩子：结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲；一个结点的分支直接接着的那个就是孩子，自己就是双亲
7. 兄弟：同一个双亲的孩子之间互称兄弟，
8. 祖先：从根到该结点经过的所有结点叫做该结点的祖先
9. 堂兄弟：双亲在同一层的结点
10. 子孙：从某结点为根的子树中的任意结点都是他的子孙
11. 层次：结点的层次从根开始定义，根为第一层，以此类推
12. 树的深度：树中结点的最大层次叫做树的深度或者高度
13. 有序树和无序树：如果树中的结点的格子树看成从左至右是有次序的，即换了顺序就是另一个树，这就是有序树，反之为无序树
14. 森林：m棵互不相交的树的集合，一棵树是一个特殊的森林

线性结构		树结构
第一个数据元素	无前驱	根节点（只有一个）	无双亲
最后一个数据元素	无后继	叶子结点（可以有多个）	无孩子
其他数据元素	一个前驱一个后继	其他结点——中间结点	一个双亲多个孩子

5.1.3二叉树的定义

对二叉树的操作比普通树简单，且可以相互转换

1. 有且仅有一个根节点
2. 一个左子树一个右子树（两边树可以为空，也可以一边为空）
3. 左右子树是有顺序的，不能颠倒，尽管只有一边有子树
4. 和树是两个概念，二叉树不是树的特殊情况，有两个结点的时候树只有一种情况，而二叉树有两种情况，二叉树不是树

二叉树的五种基本形态

5.2案例引入

表达式的二叉树表示

5.3 树和二叉树的抽象数据类型定义

具体实现

1. 构造空二叉树
2. 判断二叉树是否为空
3. 返回二叉树的根

#include<iostream>
using namespace std;
typedef int ElemType;
typedef string Status;
#define OK "OK"
#define ERROR "ERROR"
typedef struct BtNode          //定义二叉树结构体
{
    BtNode *leftchild;//左孩子
    BtNode *rightchild;//右孩子
    ElemType data;//数据
}BtNode,*BinaryTree;
Status InitBiTree(BinaryTree &T)//初始化一个二叉树
{
    T=new BtNode;
    T->data=0;
    T->leftchild= nullptr;
    T->rightchild= nullptr;
    return OK;
}
bool BiTreeEmpty(BinaryTree T)//判断二叉树是否为空
{
    if(!T)
        return true;
    else
        return false;
}
int Root(BinaryTree T)//返回根结点
{
    if(!BiTreeEmpty(T))
        return T->data;
}
int main()
{
    BinaryTree T;
    cout << InitBiTree(T) << endl;
    cout << BiTreeEmpty(T) << endl;
    cout << Root(T);
    return 0;
}

5.4二叉树的性质和存储结构

5.4.1二叉树的性质

1. 二叉树的第i层最多有2^(i-1)个结点，至少有一个结点
2. 深度为K的二叉树至多有2^K-1个结点，至少有K个结点
3. 对任意一棵二叉树，如果叶子数有n0个。度为2的结点数为n2，则n0=n2+1，叶子数是度为2结点数加1

两种特殊的二叉树

1. 满二叉树：一个数达到最大结点数(2^K-1)，就叫做满二叉树，它的叶子结点都在最底层，每一层都是最大结点数
   对满二叉树进行编号，自上而下，从左至右编号，每一个结点都有元素
   
2. 完全二叉树：该树与其同深度的满二叉树结点一一对应，这个树就叫做完全二叉树，其叶子只看分布在层次最大的两层上

判断方法：

1. 可以通过编号来确定是否为完全二叉树，编号一一对应

2. 也可以通过连续去掉最后的结点来判断，连续去掉最后的结点，这些树一定是完全二叉树

满二叉树一定是完全二叉树，反过来就不一定

完全二叉树的性质

1. 如图
   
2. 对完全二叉树按照上面的规则进行编号则有（双亲结点和孩子结点编号的关系）
   (1) 若i=1,则结点i是二叉树的根，无双亲，如果i>1则双亲是结点[i/2]
   (2) 如果2i>n,则结点i为叶子结点，无左孩子，否则，其左孩子是结点2i
   (3) 如果2i+1>n,则结点i无右孩子，否则，其右孩子是结点2i+1

5.4二叉树的存储结构

二叉树的存储结构也可以是顺序或者是链式

5.4.1顺序存储结构

#define MAXSIZE 100//二叉树的最大结点数
typedef int TElemType;
typedef TElemType SqBiTree[MAXSIZE];//0号单元存储根节点
SqBiTree bt;

• 对于完全二叉树，从根结点开始，依次自上而上，从左至右编号当做数组下标，存储在数组中
• 对于一般的二叉树，则也相应的按照完全二叉树的存储方式来存储，不存在的结点就用0来表示

由此可见这种方法仅仅适用于完全二叉树，当是一般的二叉树的时候就会造成存储空间的极大浪费

5.4.2链式存储结构

分为二叉链表和三叉链表，其中三叉链表比二叉链表多一个指向双亲的指针域

二叉树二叉链表存储表示

typedef int TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

5.5遍历二叉树和线索二叉树

5.5.1遍历二叉树

遍历二叉树是指按某条搜索路径寻访树中的每个结点，使得每个结点均被访问一次且仅被访问一次

遍历二叉树分为三种情况，分别是先序遍历，中序遍历和后序遍历，其定义如下，先序遍历的根最先遍历，后续遍历的根最后遍历

从表达式看，以上三个迅雷恰好为表达式的前缀表示（波兰式）中缀表示和后缀表示（逆波兰式）

中序遍历的递归算法

void InOrderTraverse(BiTree T)
{
    if(T)//若二叉树非空
    {
        InOrderTraverse(T->lchild);//中序遍历左子树
        cout << T->data;//访问根结点
        InOrderTraverse(T->rchild);//中序遍历右子树
    }
}

其余两种算法只需要交换顺序即可

中序遍历的非递归算法

void InOrderTraverse(BiTree T)
{
InitStack(S);p=T;
q=new BiTNode;
while(p||!StackEmpty(S))
{
    if(p)//p非空
    {
        Push(S,p);//根指针进栈
        p=p->lchild;
    }
    else//p为空
    {
        Pop(S,q);//出栈
        cout << q->data;//访问根结点
        p=q->rchild;//遍历右子树
    }
}
}

先序遍历的顺序建立二叉链表

上图b详细解释：ABC##DE#G##F###（树→子树）

1. A：根节点
2. B：根节点建立后开始下一个左树建立，左树根节点为B
3. C：根节点建立后开始下一个左树建立，左树根节点为C
4. ·#：继续往下建立左树，此时左树为空
5. ·#：左树为空就建立当前层次的右树，这个#表示右树为空
6. D：该层次为空递归完成，该层函数返回自上一层，也就是根节点为B的那一层，该层左树已经建立，这层函数继续往下运行，建立右树，根节点为D，继续递归
7. E：继续往下层建立左树，根节点为E
8. ·#：继续往下层建立左树，此时左树为空
9. G：该层左树为空，函数往下运行建立右树，右树根节点为G
10. ·#：继续向下建立左树，左树为空
11. ·#：左树为空，函数向下运行建立右树，右树也为空，递归结束，函数返回上一层，上一层右树已经建立完成，继续返回上一层（D）
12. F：左树建立已经完成，此时建立右树，根节点为F
13. ·#：继续往下建立左树，左树为空
14. ·#：该层函数往下运行建立右树，右树为空，函数返回上一层（B），左右建立完成，继续返回（A）
15. ·#：建立A结点的右树，右树为空

复制二叉树

void Copy(BiTree T,BiTree &NewT)
{
    if(!T)//空
    {
        NewT= nullptr;
        return;
    }
    else
    {
        NewT=new BiTNode;
        NewT->data=T->data;//复制根结点
        Copy(T->lchild,NewT->lchild);//复制左右结点
        Copy(T->rchild,NewT->rchild);
    }
}

计算二叉树的深度

int Depth(BiTree T)
{
    int m;
    int n;
    if(!T) return 0;
    else
    {
        m=Depth(T->lchild);//递归遍历左结点
        n=Depth(T->rchild);//递归遍历右结点
        if(m>n) return m+1;//m计数
    }
    return 0;//没用
}

统计二叉树中结点的个数

int NodeCount(BiTree T)
{
    if(!T) return 0;
    else
    {
        return NodeCount(T->lchild)+ NodeCount(T->rchild)+1;//有左树，有右树就会进入递归，每次递归计数+1
    }
}

附本节代码

#include<iostream>
#define OK "OK"
#define ERROR "ERROR"
#define MAXSIZE 100//二叉树的最大结点数
using namespace std;
typedef string Status;
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild= nullptr,*rchild= nullptr;
}BiTNode,*BiTree;

void InOrderTraverse(BiTree T)//递归中序遍历
{
    if(T!= nullptr)//若二叉树非空
    {
        InOrderTraverse(T->lchild);//中序遍历左子树
        cout << T->data;//访问根结点
        InOrderTraverse(T->rchild);//中序遍历右子树
    }
}
void Copy(BiTree T,BiTree &NewT)//复制二叉树
{
    if(!T)//空
    {
        NewT= nullptr;
        return;
    }
    else
    {
        NewT=new BiTNode;
        NewT->data=T->data;//复制根结点
        Copy(T->lchild,NewT->lchild);//复制左右结点
        Copy(T->rchild,NewT->rchild);
    }
}
int Depth(BiTree T)//计算深度
{
    int m=0;
    int n=0;
    if(!T) return 0;
    else
    {
        m=Depth(T->lchild);
        n=Depth(T->rchild);
        if(m>n) return m+1;
    }
    return 0;
}
int NodeCount(BiTree T)
{
    if(!T) return 0;
    else
    {
        return NodeCount(T->lchild)+ NodeCount(T->rchild)+1;//有左树，有右树就会进入递归，每次递归计数+1
    }
}
int main()
{
    /**初始化二叉树**/
    auto T=new BiTNode;
    T->lchild=new BiTNode;
    T->rchild=new BiTNode;
    T->lchild->lchild=new BiTNode;
    T->lchild->rchild=new BiTNode;
    T->data='-';
    T->lchild->data='*';
    T->lchild->lchild->data='a';
    T->lchild->rchild->data='b';
    T->rchild->data='c';
    InOrderTraverse(T);
    return 0;
}

5.5.2线索二叉树

概念

引入线索二叉树是为了保存在遍历动态过程中得到的有关前驱和后继的信息，但是这样做是的存储密度大大降低，由于n个结点的二叉链表中必定存在n+1个空链域，可以充分利用这些空链域来保存这些前驱和后继的信息

以这种结点构成的二叉链表作为二叉树的存储结构，叫做线索链表，加上线索的二叉树称之为线索二叉树，对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

二叉树的二叉线索类型定义如下

typedef int TElemType;
typedef string Status;
typedef struct BiThrNode
{
    TElemType data;//存放数据
    struct BiThrNode *lchild,*rchild;//左右孩子指针
    int LTag,RTag;//左右标志，0表示孩子，1表示前驱
}BiThrNode,*BiThrTree;

构造线索二叉树

线索化：在遍历的过程中修改空指针的过程

以结点p为根的子树中序线索化

void InThreading(BiThrTree p) {
    if (p) {
    //pre是全局变量，初始化的时候其右孩子指针为空，便于在树的最左点开始建线索
        InThreading(p->lchild);//左子树递归线索化
        if (!p->lchild) {
            p->LTag = 1;//给p加上做线索+
            p->lchild = pre;//p的左孩子指针指向pre
        } else p->LTag = 0;
        if (!pre->rchild) {//pre右孩子为空
            pre->RTag = 1;//给pre加上右线索
            pre->rchild = p;//pre的右孩子指针指向p（后继）
        } else p->RTag = 0;
        pre = p;//pre指向p的前驱
        InThreading(p->rchild);
    }
}

带头结点的二叉树中序线索化

void InThreading2(BiThrTree &Thrt,BiThrTree T)
{
    //中序遍历二叉树T，并将其线索化，Thrt指向头结点
    Thrt=new BiThrNode;//建头结点
    Thrt->LTag=0;//头结点有右孩子，若树非空，则其左孩子为树根
    Thrt->RTag=1;//头结点的右孩子指针为右线索
    Thrt->rchild=Thrt;//初始化时右指针指向自己
    if(!T) Thrt->lchild=Thrt;//若树为空则左指针指向自己
    else
    {
        Thrt->lchild=T;//头结点的左孩子指向根，pre初值指向头结点
        pre=Thrt;
        InThreading(T);//调用算法5.7，对T为根的二叉树进行中序线索化
        pre->rchild=Thrt;//算法5.7结束后，pre为最右节点，pre的右线索指向头结点
        pre->RTag=1;
        Thrt->rchild=pre;//头结点的右线索指向pre
    }
}

遍历线索二叉树

void InOrderTraverse_Thr(BiThrTree T)
{
//T指向头结点，头结点的左链lchild指向根结点
//中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
p=T->lchild;//p指向根结点
while(p!=T)//空树或遍历结束时，p==T
{
    while(p->LTag==0)p=p->lchild;//沿左孩子向下
    cout << p->data;//访问其左子树为空的结点
    while(p->RTag==1&&p->rchild!=T)
    {
        p=p->rchild;cout << p->data;//沿右线索访问后继结点
    }
    p=p->rchild;//转向p的右子树
}
}

5.6树和森林

5.6.1树的存储结构

双亲表示法

每个结点包括一个数据域和一个parent域指向其双亲结点的位置

R是0，以此类推

这种存储结构利用了每个结点（根除外）只有唯一的双亲的性质，这种存储结构下，求结点的双亲十分方便，也很容易求树的根，但是求结点的孩子时需要遍历整个结构

孩子表示法

1. 设置多个指针域指向一棵子树的根结点
2. 把每个结点的孩子结点排列起来，看成是一个线性表且以单链表做存储结
   构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构

孩子兄弟法（二叉树表示法）

链表中的两个链域分别指向该结点的第一个孩子结点后下一个兄弟结点

typedef struct CSNode
{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;//第一个孩子结点和下一个兄弟结点
}CSNode,*CSTree;

这种表示方法是一种比较普遍的表示方法

5.6.2森林与二叉树的转换

任何一棵树对应的二叉树其根结点的右子树必空

解释：上图中森林中每一棵树中转换成二叉树，根结点的第一个子树转换为二叉树的左子树，随后该层的其他子树跟在第一个结点后面，依次为右子树，其余结点的情况都是一样的

• 即每一层第一个结点都是上一个结点的左子树的根，该层其他结点跟在此结点后作为右子树

下面是书中的描述

5.6.3树和森林的遍历

树的遍历

两种方法：先根(次序)遍历,先访问根结点在访问子树，后根(次序)遍历

对该树用先根遍历：RADEBCFGHK

对该树用后根遍历：DEABGHKFCR

森林的遍历

先序遍历森林：

1. 访问森林中第一棵树的根结点
2. 先序遍历第一棵树的根结点的子树森林
3. 先序遍历除去第一棵树之后剩余的树构成的森林

中序遍历和后序遍历仅仅改变三者顺序

森林和树转换成二叉树结构遍历

• 当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，其余树的森林转换成右子树，森林的先序遍历和中序遍历即为其对应的二叉树的先序和中序遍历
• 当以二叉链表做树的存储结构的时候，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现

5.7哈夫曼树及其应用

5.7.1哈夫曼树的基本概念

哈夫曼树又称最优树，是一类带权路径最短的树

1. 路径：从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径
2. 路径长度：路径上的分支数目称作路径长度
3. 树的路径长度：从树根到每一结点的路径长度之和
4. 权：视具体情况而定
5. 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积
6. 树的带权路径长度：树中所有叶子结点的带权路径长度之和
7. 哈夫曼树：其中带权路径长度最小的二叉树称作最优二叉树或者哈夫曼树

如上图中c树的带权和最小，他就是哈夫曼树

5.7.2哈夫曼树的构造算法

哈夫曼树的构造过程

这个构造过程就是离散数学中哈夫曼树的构造过程，一模一样，这种算法是一种典型的贪心算法

哈夫曼树的实现

 typedef struct
 {
     int weight;//结点的权值
     int parent,lchild,rchild;//结点双亲，左孩子，右孩子的下标
 }HTNode,*HuffmanTree;

哈夫曼树各个结点存储在由HuffmanTree定义的动态分配的数组中，且数组的0号单元不使用，数组的大小是2n,叶子结点几种存储在前面1~n个位置，后面存在后面的位置

构造哈夫曼树

void CreateHuffmanTree(HuffmanTree &HT,int n)
{
    if(n<=1) return;
    m=2*n-1;
    HT=new HTNode[m+1];//动态分配m+1个单元，HT[m]表示根结点
    for(int i=1;i<=m;i++)//初始化
    {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(int i=1;i<=n;i++)//输入前n个单元中叶子结点的权值
        cin >> HT[i].weight;
    for(int i=n+1;i<=m;i++)//创建哈夫曼树
    {
        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;
    }
}

5.7.3哈夫曼编码

对一棵哈夫曼树，左边赋值为0，右边赋值为1，结点路径产生的二进制串就是哈夫曼编码，哈夫曼编码是最优前缀编码，产生的二进制串最短

算法实现

void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{
    HC=new char*[n+1];//分配存储n个字符编码的编码表空间
    cd=new char[n];//分配零食存放每个字符编码的动态数组空间
    cd[n-1]='\0';
    for(int i=1;i<=n;i++)//逐个字符求哈夫曼编码
    {
        start=n-1;//
        c=i;
        f=HT[i].parent;
        while(f!= 0)
        {
            -start;//回溯一次start向前指一个位置
            if(HT[f].lchild=c)  cd[start]='0';//左孩子是1，右孩子是0
            else cd[start]='1';
            c=f;//继续向上回溯
            f=HT[f].parent;
        }
        HC[i]=new char[n-start]；//为第i个字符编码分配空间
        strcpy(HC[i],&cd[start]);
        }
        delete cd;//释放临时空间
    }

文件的编码和译码

(1)编码：字符→哈夫曼字符编码

(2)译码：借助哈夫曼树译码