树和二叉树

树和二叉树的定义与存储

树的定义

树是一种非线性的数据结构，它是由n个有限结点组成有层次关系的集合

树具有以下特点，可以根据这些特点来判断一个数据结构是否是树

每个结点具有0个或多个子结点
每个子结点只有一个父结点
没有前驱的结为根结点
除了根结点外，每个子结点又可以由m棵不相关的子树组成

树的基本术语

1.结点的度:结点拥有的子树数量称为结点的度
2.树的度:树内各结点度的最大值，即上图 D结点的度就是此树的度
3.叶子:度为0的节点称为叶子或终端节点
4.结点的层次和树的深度
5.森林:m棵互不相交的树的集合

二叉树与树主要有以下区别:
1.二叉树每个结点至多只有两棵子树(即二叉树中不能存在度大于 2 的结点)
2.二叉树的子树有左右之分，其次序不能任意颠倒
3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树的性质:

性质1:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质2:深度为k的二叉树至多有2^k-1个结点(k>=1)
性质3:对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1
【证明】一棵二叉树，除了终端结点(叶子结点)，就是度为1或2的结点。假设n1表示度为1的结点数，则树T的结点总数n=n0+n1+n2,我们再换个角度，看一下树T的连接线数，除了根节点，其他结点都有一根线表示分支进入，所以连接线数为结点总数减去1。按连接线树算的话:n-1=n1+2n2，可推导出n0+n1+n2-1=n1+2n2，继续推导可得n0=n2+1

性质4:具有n个结点的完全二又树的深度为[log2n]+1

性质5:如果对一颗有n个结点的完全二叉树(其深度为[logzn]+ 1)的结点按层序编号(从第1层到第
[logzn]+ 1层，每层从左到右)，对任一结点i(1<=i<=n)有:
1.如果i=1,则结点i是二叉树的根，无双亲;如果i>1，则其双亲是结点[i/2]
2.如果2i>n,则结点i无孩子(结点i为叶子结点);否则其左孩子是结点 2i
3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点 2i+1

二叉树的存储结构

二叉树的存储:顺序存储、链式存储

二叉树的顺序存储结构缺点很明显:不能反应逻辑关系，
对于特殊的二叉树(左斜树、右斜树)，浪费存储空间。
所以二叉树顺序存储结构一般只用于完全二叉树。

//二叉树的二又链表存储表示
typedef struct BiTNode {
//结点数据域
    TElemType data;
//左右孩子指针
    struct BiTNode *lchild, *rchild;
} BiTNode,*BiTree;

树的遍历

树的遍历是指从根结点到叶子结点的遍历过程。

树的先序遍历

先序遍历是指先访问根结点，然后先序遍历左子树，再先序遍历右子树。

访问根结点
先序遍历左子树
先序遍历右子树
(根左右)

树的中序遍历

中序遍历是指先序遍历左子树，再访问根结点，最后中序遍历右子树。

中序遍历左子树
访问根结点
中序遍历右子树
(左根右)

树的后序遍历

后序遍历是指先序遍历左子树，再中序遍历右子树，最后访问根结点。

后序遍历左子树
后序遍历右子树
访问根结点
(左右根)

树的层序遍历

层序遍历是指按层次从上到下，从左到右访问结点的遍历过程。

//层序遍历
void levelOrder(BiTree T) {
    int i, j, k;
    BiTNode *p, *q;
    int front, rear;
    //申请一个队列
    front = rear = 0;
    //入队
    q[rear++] = T;
    //循环
    while (front!= rear) {
        //出队
        p = q[front++];
        //访问结点
        printf("%c ", p->data);
        //入队左孩子
        if (p->lchild!= NULL) {
            q[rear++] = p->lchild;
        }
        //入队右孩子
        if (p->rchild!= NULL) {
            q[rear++] = p->rchild;
        }
    }
}

哈夫曼树

基本概念识记
1.路径:从一个结点到另一个结点之间的分支序列
2.路径长度:从一个结点到另一个结点所经过的分支数目
3.结点的权:根据应用的需要可以给树的结点赋权值
4.结点的带权路径长度:从根到该结点的路径长度与该结点权的乘积
5.树的带权路径长度:树中所有叶子结点的带权路径之和WPL=∑n k=1 wk*lk
其中，n是树的叶结点个数，w是第k个叶子的权，!是第k个叶子到根的路径长度。

6.哈夫曼树:由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树

n个叶子结点的哈弗曼树有 2n-1 个结点
在构造哈弗曼树时，是从叶子结点向根节点的方向进行的，每次都是两个两个成对的结点来形成一个新的分支结点，所以不存在度为1的结点。

哈夫曼树的构造

对于有n个叶子结点，可以构造出多个二叉树。
但Huffman树是一个带权路径长度最小的二叉树，又称最优二叉树。
方法:
(1)将{w1,w2..…wn}看成n个二叉树
(2)选择 2 个根结点的值最小的二又树，构造1个新的二叉树;…;直至剩1个树止。

哈夫曼编码

前缀码:如果在一个编码系统中，任一个编码都不是其他任何编码的前缀，则称该编码系统中的编码是前缀码。
例如，一组编码01001,010,100,110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。
哈夫曼编码:对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶
子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。
哈夫曼编码是最优前缀码