树

树的定义：n个节点组成的有限集合。n=0，空树；n>0,1个根节点，m个互不相交的有限集，每个子集为根的子树。

树的基本术语

节点的度：树中某个节点的子树的个数。

树的度：树中各节点的度的最大值。

树根结点（简称“根结点”）：每一个非空树都有且只有一个被称为根的结点。

分支节点：度不为零的节点。

叶子节点：度为零的节点。

路径：i->j；路径长度：路径经过节点数目减1。

孩子节点：某节点的后继节点；
双亲节点：该节点为其孩子节点的双亲节点（父母节点）；
兄弟节点：同一双亲的孩子节点；
子孙节点：某节点所有子树中的节点；
祖先节点：从树节点到该节点的路径上的节点。

节点的层次：根节点为第一层（以此类推）；

树的高度：树中节点的最大层次。

有序树：树中节点子树按次序从左向右安排，次序不能改变；无序树：与之相反

空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。

森林：互不相交的树的集合。

树的性质

树的节点树为所有节点度数加1（加根节点）。

度为m的树中第i层最多有m^(i-1)个节点。

高度为h的m次树至多(m^h-1)/(m-1)个节点。

具有n个节点的m次树的最小高度为logm( n(m-1) + 1 ) 向上取整。

二叉树

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成，本身是有序树。

二叉树的特点

1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点，即只能是 0、1 或者 2。

2）左子树和右子树是有顺序的，次序不能任意颠倒。

3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的性质

经过前人的总结，二叉树具有以下几个性质：

1. 二叉树中，第 i 层最多有 2^(i-1) 个结点。
2. 深度为k的二叉树至多有2^k-1个结点(k≥1)。
3. 包含n个结点的二叉树的高度至少为log2(n+1)。
4. 在任意一棵二叉树中，若终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

性质4 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：

1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

2）非叶子结点的度一定是2。

3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

满二叉树除了满足普通二叉树的性质，还具有以下性质：

1. 满二叉树中第 i 层的节点数为 2^(n-1) 个。
2. 深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子数为 2^(k-1)。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
（如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。）

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。

⌊log2n⌋ 表示取小于 log2n 的最大整数。例如，⌊log24⌋ = 2，而 ⌊log25⌋ 结果也是 2。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号，对于任意一个结点 i ，完全二叉树还有以下几个结论成立：

1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
3. 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

二叉树的顺序存储和链式存储

如果想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其”拼凑”成完全二叉树即可。

完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,…），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。此性质可用于还原数组中存储的完全二叉树。

一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。

一颗二叉树的结点设计一定要有如下内容：

a)结点元素，data域，用来存储数据，其可以是int，char等基本的类型，同时也可以是struct等这些复杂的复合数据类型。

b)左孩子结点，left指针，总是用来指向当前结点的下一层的左边结点，其属于一种指针。

c)右孩子结点，right指针，总是用来指向当前结点的下一层的右边结点，其属于一种指针。

d)父结点（可选），parent指针，总是指向当前结点的前一个结点，简称父亲结点，其不属于必须结点设计，省略掉可以达到节省内存的效果，而使用则可以更方便进行定向搜索，本案例中不使用父节点。

以上就是一颗二叉树的结点设计，除此之外，我们使用一棵树的时候需要建立一颗树根，由这个“根”，来进行逐步的向下构建。

其设计代码可以表示为：

//树的结点
typedef struct node{
    int data;
    struct node* left;
    struct node* right;
    // struct node *parent;
} Node;
  
//树根
typedef struct {
    Node* root;
} Tree;

二叉树的遍历

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

二叉树先序遍历的实现思想是：

访问根节点；访问当前节点的左子树；若当前节点无左子树，则访问当前节点的右子树；

//树的先序遍历 Preorder traversal递归实现
void preorder(Node* node){
    if (node != NULL){
        printf("%d ",node->data);//调用操作结点数据的函数方法
        preorder(node->left);//访问该结点的左孩子
        preorder(node->right);//访问该结点的右孩子
    }
    //如果结点为空，返回上一层
    return;
}

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现。

二叉树中序遍历的实现思想是：访问当前节点的左子树；访问根节点；访问当前节点的右子树；

//树的中序遍历 In-order traversal递归实现
void inorder(Node* node){
    if (node != NULL){
        inorder(node->left);//访问该结点的左孩子
        printf("%d ",node->data);//调用操作结点数据的函数方法
        inorder(node->right);//访问该结点的右孩子
    }
    //如果结点为空，返回上一层
    return;
}

中序遍历的非递归方式实现思想是：从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。
除此之外，还有另一种实现思想：中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不需要压栈。当结点的左子树遍历完成后，只需要以栈顶结点的右孩子为根结点，继续循环遍历即可。

二叉树后序遍历的实现思想是：从根节点出发，依次遍历各节点的左右子树，直到当前节点左右子树遍历完成后，才访问该节点元素。

//树的后序遍历 Post-order traversal递归实现
void postorder(Node* node){
    if (node != NULL){
        postorder(node->left);//访问该结点的左孩子
        postorder(node->right);//访问该结点的右孩子
        printf("%d ",node->data);//调用操作结点数据的函数方法
    }
    //如果结点为空，返回上一层
    return;
}

后序遍历是在遍历完当前结点的左右孩子之后，才调用操作函数，所以需要在操作结点进栈时，为每个结点配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0，进栈；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。这样，当遍历完成，该结点弹栈时，查看该结点的标志位的值：如果是 0，表示该结点的右孩子还没有遍历；反之如果是 1，说明该结点的左右孩子都遍历完成，可以调用操作函数。

二叉树层次遍历

按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

通常，普通树的存储具有普通树结构数据的方法有 3 种：

双亲表示法；孩子表示法；孩子兄弟表示法；

双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。

孩子表示法存储普通树采用的是 “顺序表+链表” 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。
如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。

孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。

因此，该链表中的节点应包含以下 3 部分内容：
节点的值；指向孩子节点的指针；指向兄弟节点的指针；

表示节点结构代码为：

#define ElemType char
typedef struct CSNode{
    ElemType data;
    struct CSNode * firstchild,*nextsibling;
}CSNode,*CSTree;

可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，换句话说，任意一棵普通树都有唯一的一棵二叉树于其对应。

因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为”二叉树表示法”或”二叉链表表示法”。

树与森林

树转换成二叉树

操作过程如下：

加线：在兄弟（即同一层之间的孩子）之间加一连线

抹线：对每个结点，除了其第一个孩子外，除去其与其余孩子之间的连线

旋转：以树的根结点为轴心，将整树顺时针转45°

注意：树转换成二叉树其右子树一定为空

二叉树转换成树

加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来

抹线：抹掉原二叉树中双亲与右孩子之间的连线

调整：将结点按层次排列，形成树结构

森林转换成二叉树

将各棵树分别转换成二叉树

将每棵树的根结点用线相连

以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

二叉树转换成森林

抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

还原：将孤立的二叉树还原成树（二叉树→树）

哈夫曼树

哈夫曼树（Huffman Tree），又名：最优二叉树，赫夫曼树

其标准含义是：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树相关的几个名词

a) 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。

b) 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。

c) 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。

d) 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。

e) 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”。

在构建哈夫曼树时，只需要遵循一个原则，那就是权重越大的结点距离树根越近。

首先，选出我们数据中最小的两个数据，构建成二叉树的左孩子和右孩子，而根的数据为两者之和

其次，将刚才合成的数据作为右孩子，左孩子从未处理的数据中选出最小的一个，作为左孩子，他们的根同样为左右孩子的权值和

不断重复上述的步骤，直到将所有的数据全部处理完并构建出二叉树，这棵二叉树就是我们的哈夫曼树。

哈夫曼树的结点结构

其代码表示为：

//哈夫曼树结点结构
typedef struct {
    int weight; //结点权重
    int parent, left, right;    //父结点、左孩子、右孩子在数组中的位置下标
} HTNode, *HuffmanTree;

构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。

查找权重值最小的两个结点的思想是：从数组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：

如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
如果介于两个结点权重值之间，替换原来较大的结点；

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。哈夫曼编码就是在哈夫曼树的基础上构建的，这种编码方式最大的优点就是用最少的字符包含最多的信息内容。霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合，也包括文件传输的场合。

根据发送信息的内容，通过统计文本中相同字符的个数作为每个字符的权值，建立哈夫曼树。对于树中的每一个子树，统一规定其左孩子标记为 0 ，右孩子标记为 1 。这样，用到哪个字符时，从哈夫曼树的根结点开始，依次写出经过结点的标记，最终得到的就是该结点的哈夫曼编码。

文本中字符出现的次数越多，在哈夫曼树中的体现就是越接近树根。编码的长度越短。

使用程序求哈夫曼编码有两种方法：

从叶子结点一直找到根结点，逆向记录途中经过的标记。

从根结点出发，一直到叶子结点，记录途中经过的标记。

n 个结点可以构建多少种形态不同的二叉树。

每一棵普通树对应的都是一棵没有右子树的二叉树，所以对于 n 个结点的树来说，树的形态改变是因为除了根结点之外的其它结点改变形态得到的，所以，n 个结点构建的形态不同的树与之对应的是 n-1 个结点构建的形态不同的二叉树。

如果 tn 表示 n 个结点构建的形态不同的树的数量，bn 表示 n 个结点构建的形态不同的二叉树的数量，则两者之间有这样的关系：tn=bn-1。