树

非线性结构中的树形结构前驱个数唯一，后驱不唯一

每个树有且只有一个根结点Root，其余可分为n个互不相交的有限集，每个有限集本身又是一棵树，并称为根的子树

根节点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数
树的树：树内各结点的度的最大值
叶结点/终端结点：度为零的结点，没有后驱
分支结点的度不为零，根结点之外的分支结点称为内部结点

树的存储结构

双亲表示法

每个结点包含两个指针域，分别用来存放数据与该结点的双亲结点在数组中的位置

typedef struct PTNode {
    int data;
    int parent;
}PTNode;

#define MAX_SIZE 100
typedef struct PTree {
    PTNode nodes[MAX_SIZE];
    int r;  // 根结点位置
    int n;  // 结点个数
}

孩子链表

把每个结点的孩子排列成单链表，再将每个结点存入顺序表中，顺序表中每个元素的指针域指向该结点的孩子组成的链表的头指针

也可在顺序表各元素中添加双亲的位置

二叉树表示法

用二叉链表表示树的存储结构，链表中每个结点的两个指针域分别指向该结点的第一个孩子结点和下一个兄弟结点

typedef struct CSNode {
    int data;
    CSNode *child;
    CSNode *next;
}CSNode, *CSTree;

树、森林与二叉树的转换

树转化为二叉树：将每个结点与左兄弟节点连线，除了第一个孩子与父结点之间的连线，除掉其余孩子与父结点间的连线

二叉树转化为树：若一个结点是某个结点的左结点，则该结点的右结点以及右结点的右结点直至没有右结点，将这些结点与该结点的父结点连线，并去掉这些结点之间的连线

森林转化为二叉树：先将各个树转化为二叉树，再将二叉树的根节点连线，顺时针旋转45°，这样第二棵树的根节点就变成了第一棵树根结点的右结点

二叉树转化为森林：将二叉树的根节点与其右结点之间的连线去掉，使其变成孤立的二叉树，再将二叉树转化为树

树与森林的遍历

树的遍历

先根遍历：先访问根结点，再遍历各子树

后根遍历：先遍历各子树，再访问根结点

层次遍历：

森林的遍历

将森林看做由三部分组成：1.森林中第一棵树的根节点、2.森林中第一棵树的子树森林、3.森林中其他树构成的森林

先序遍历：先访问1，然后先序遍历2，最后先序遍历3，相当于依次对每棵树进行先根遍历

中序遍历：先中序遍历2，然后访问1，最后中序遍历3，相当于依次对每棵树进行后根遍历

二叉树

每个结点最多只有两个后驱结点的树称为二叉树

二叉树的结构最简单，规律性最强，所有树都能转化为唯一对应的二叉树，且普通树若不转化为二叉树，则运算很难实现，因此解决普通树的问题时一般转化为二叉树再运算

二叉树不是树的特殊情况，是两个概念

二叉树结点的子树要区分左子树与右子树，即使只有一棵子树也要区分，因此只有两个结点的二叉树有两种状态，分别是第二个结点为左子树和第二个结点为右子树，而有两个结点的树只有一种状态

满二叉树：每一层结点数量都为该层最大结点数
完全二叉树：除最后一层外，其余层数全满，最后一层的结点向左对齐

顺序存储

按照满二叉树的结点层次编号，依次存放二叉树中的元素，为空则用0表示

缺点：若二叉树空值较多则很浪费空间，适合用来存储满二叉树和完全二叉树

链式存储

结构

typedef struct BiNode {
    int data;
    BiNode *parent;
    BiNode *left;
    BiNode *right;
}BiNode, *BiTree;

遍历二叉树

假设 L：遍历左子树，D：遍历根节点，R：遍历右子树，规定遍历顺序为从左向右，则有三种情况，分别是DLR前序遍历，LDR中序遍历，LRD后序遍历

遍历的结果分别称为前缀表达，中缀表达，后缀表达

递归算法

以下为先序排列代码，中序排列与后续排列只需变换部分位置即可

void bianli(BiTree root) {
    if (!root) return;
    cout<<root->data<<" ";
    if (root->left) bianli(root->left);  
    if (root->right) bianli(root->right);
}

非递归算法

主要思路为先访问中结点，再将中结点存储起来，等待左结点访问完毕后访问右结点，以此循环，将各个中结点存储起来，并按照后存储的先取出的顺序访问，显然需要将结点存储在栈stack中，因此就有了以下先序遍历的代码

void DLR(BiTree root) {
    if (!root) return;
    LinkStack p = nullptr;
    Push(p, root);
    while (p) {
        BiTree current = Pop(p);
        cout<<current->data<<" ";
        if (current->right) Push(p, current->right);
        if (current->left) Push(p, current->left);
    }
}

首先新建一个栈，将root压入栈中
进入循环，当栈空时跳出循环，中结点出栈并用curent保存中结点，访问中结点后依次将右结点左结点入栈，左结点后入先出，先访问左结点再访问右结点，实现中序遍历
若要实现中序遍历与后序遍历，只需更改访问结点的位置，变更代码顺序即可

层次遍历

将每层所有结点都存入队列中，然后依次取出访问，并将其左结点与右结点在存入队列中，以此循环

void cengci(BiTree root) {
    LinkQueue Q;
    Init(Q);
    Enter(Q, root);
    while (Q.front != Q.rear) {
        BiTree p = Q.front->next->data;
        cout<<p->data<<" ";
        Delete(Q);
        if (p->left) Enter(Q, p->left);
        if (p->right) Enter(Q, p->right);
    }
    Destroy(Q);
}

先将根结点存入队列中，进入循环，循环条件为队列不为空，用p表示根结点，访问根结点后取出，接着将左结点与右结点存入队列末尾

练习

已知二叉树的先序和中序序列，构造出相应的二叉树

先序：A B C D E F G H I J

中序：C D B F E A I H G J

由先序遍历可知，A为根结点的值，结合中序序列可推测出CDBFE为左子树，IHGJ为右子树；再看先序序列A之后是B，因此B为左子树的根节点，可得出CD为左子树的左子树，FE为左子树的右子树；再看先序序列B之后的C，多次重复即可得出结果

应用

计算深度

int Depth(BiTree root) {
    if (!root) return 0;
    return 1 + max(Depth(root->left), Depth(root->right));
}

计算结点数

int Number(BiTree root) {
    if (!root) return 0;
    return 1 + Number(root->left) + Number(root->right);
}

计算叶结点数

int LeafNum(BiTree root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return LeafNum(root->left) + LeafNum(root->right);
}

线索二叉树

利用二叉树中的空指针域，如果某个结点的左结点为空，则将左结点指针域改为指向其前驱，若右结点为空，则改为指向其后继，这种改变指向的指针称为线索，加上线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化

为区分left与right指向孩子还是指向前驱或后继，在二叉链表的每个节点中增设两个标致域ltag和rtag，当值为0时指向孩子，值为1时指向前驱或后继

哈夫曼树

树的路径长度指树的根结点到每个结点的路径长度之和

结点数相同的二叉树中，完全二叉树是路径长度最短的二叉树，但路径最短的二叉树不一定是完全二叉树

权：将树中结点赋给一个有着某种含义的数值，则这个值称为该结点的权

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和

哈夫曼树：最优二叉树，即带权路径长度最短的二叉树

构造哈夫曼树

根据n个给定的权值，构成n棵深度为零的二叉树的森林
在森林中选取两个权值最小的二叉树作为新二叉树的左右子树，新二叉树的权值即为这两棵二叉树的权值之和
在森林中删除这两棵用到的二叉树，再将新二叉树加入森林中
重复(2)(3)直至森林中只剩一棵树，这棵树即为哈夫曼树

哈夫曼树的结点度数只能为0或2，不能为1
包含n个叶结点的哈夫曼树共有2n-1个结点

构造算法的实现

采用顺序存储结构，一维结构数组，为方便处理，数组的第0位不使用，从第一位开始

先初始化哈夫曼树，为前n个结点的权赋值并将其他数据赋为0

void CreateHuffmanTree(HuffmanTree tree, int n) {
    for (int i = n+1; i <= 2*n; i++) {
        // 1.
        int s1 = -1, s2 = -1;
        // (1)
        for (int j = 1; j <= i; j++) {
            if (tree[j].parent == 0) {
                if (s1==-1 || tree[s1].weight > tree[j].weight) {
                    s2 = s1;
                    s1 = j;
                }
                else if (s2==-1 || (tree[s2].weight > tree[j].weight && s1 != j)) { // (2)
                    s2 = j;
                }
            }
        }
        // 2.
        tree[i].weight = tree[s1].weight + tree[s2].weight;
        tree[i].left = s1;
        tree[i].right = s2;
        tree[s1].parent = i;
        tree[s2].parent = i;
    }
}

构造哈夫曼树的过程就是逐个为后n-1个元素的权进行赋值，当最后一个元素得到权，就意味着哈夫曼树构造成功，因此需要一个从n+1开始2n结束的循环
其中步骤1.表示在所有没有父结点的结点中找出最小的两个结点s1、s2，步骤2.表示为第i位元素的数据进行赋值，并添加s1、s2所代表的结点的父结点，用来表示这两个结点已合并
(1)求最小值与次小值，LeetCode第414题官方题解方法三，注意赋值时的顺序
(2)需添加s1 != j来防止s1s2指向同一个结点

哈夫曼编码

传递字符时，若使用等长的编码方式会浪费空间，因此可以使用不等长的编码方式，但这样要解码时就容易出现重码问题

因此要解决重码问题，则必须使任一字符的编码都不是另一个字符的编码的前缀，哈夫曼编码即可保证是前缀编码

哈夫曼编码是以每个字符出现的概率/次数作为权重，构造哈夫曼树，再用左孩子代表0，右孩子代表1，得到各个字符的编码

图中从根结点到每个字符的路径上都不会遇到其他字符，所以每个叶结点的编码都不是其他叶结点编码的前缀，因此能够保证是前缀编码
哈夫曼树带权路径长度最短的性质保证了字符编码的总长最短

构造哈夫曼编码

#include <algorithm>
string* CreateHuffmanCode(HuffmanTree tree, int n){
    string *codes = new string[n+1];
    for (int i = 1; i <= n; i++) {
        string cd = "";
        int j = i, p = tree[i].parent;
        while (p != 0) {
            if (tree[p].left==j) cd += "0";
            else cd +=  "1";
            j = p;
            p = tree[p].parent;
        }
        reverse(cd.begin(), cd.end());
        codes[i] = cd;
    }
    return codes;
}

从叶结点向根结点回溯，若子结点是父结点的左结点则记为0，右结点记为1，将编码暂时存储在字符串中，最后反转再赋值给字符串数组
使用字符串临时存放编码，优点是不用考虑越界问题，且最后不用进行转换
reverse(a, b)表示反转从a到b区间内的字符串，cd.begin()``cd.end()分别表示字符串cd的开始和末尾，#include <algorithm>是使用reverse时所需的头文件