数据结构——树

逻辑结构：非线性结构—-元素之间关系为1：N

特点：

• 结点之间有分支
• 有层次关系

树的定义

• n(n>=0)个结点的有限集

  • 若n=0，则成为空树；

  • 若n>0，则它满足如下两个条件：

    1. 有且仅有一个成为根(root)的结点
    2. 其余结点可分为m(m>=0)个互不相交的有限集 T1,T2,T3…Tm; 其中每一个集合本身也是一棵树，每个集合称为根的子树

树的基本术语

• 根结点：无前驱的结点
• 叶子结点：无后继的结点，度为0
• 结点的度：结点拥有的子树的数目
• 树的度：各结点的度的最大值
• 分支结点：度 != 0
• 内部结点：根结点以外的分支结点
• 双亲结点与孩子结点：结点的子树的根称为该结点的孩子，该结点被称为子树的根的双亲
• 兄弟结点：拥有同一双亲的所欲结点称为兄弟结点
• 堂兄弟结点(雾)：双亲处于同一层但不是同一双亲的结点之间称为堂兄弟结点
• 结点的祖先：从根结点到该结点上的所经过分支上的所有的结点称为该结点的祖先
• 树的深度：树的层数

有序树和无序树

• 有序树：树中结点的各子树从左至右有次序(最左边为第一个孩子)
• 无序树：树中结点的各子树无次序

森林

m(m>=0)棵互不相加的树组成的树的集合

一棵树可以看成是一个特殊的森林

给森林中的所有树加上同一个双亲结点，这个森林就变成了树

所以：树一定是森林，森林不一定是树‘

二叉树

每个结点上最多只有两个分支

二叉树是n(n>=0)个结点的有限集，n==0为空集，或者由根结点和左右子树为二叉树的子树组成

特点：

• 每个结点最多只有两个孩子(故二叉树中不存在度大于2的结点)
• 结点的子树有左右之分，不能颠倒
• 二叉树可以是空树，结点可以有空的左子树或右子树

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

最主要的区别：二叉树严格区分左子树和右子树，即使结点上只有一个孩子（这时可以有两种二叉树）；树只有一个孩子时，无需区分左右次序（这时只有一种树）

1. 二叉树的常见使用案例

1.1 数据压缩问题

将数据文件转成由二进制串，称为编码

1.2 求解表达式

以二叉树表示表达式的递归定义如下：

1. 若表达式为数或简单变量，则只需要一个根节点存放，其数据域表示表达式
2. 若表达式形式为：”第一操作数 运算符 第二操作数“ 的形式，则对应的二叉树中，左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符—-若为一元运算符，则左子树为空，其中操作数本身也是表达式

2. 二叉树的性质

• 在第i层上至多有 2 个结点 (i>=1), 至少有 1 个结点
• 深度为k的二叉树至多有 2 个结点 (k>=1)，至少有 k 个结点
• 对任意一棵二叉树T，如果其叶子数为n, 度为2的结点为n, 则n=n+1

2.1 满二叉树和完全二叉树

2.1.1 满二叉树

定义：一棵深度为k且有2个结点的二叉树称为满二叉树

特点：

• 每层都满
• 叶子结点全在一层(最底层)

对满二叉树中结点位置进行编号

• 规则：从根结点开始，自顶向下，自左到右
• 前提：每一结点位置都有元素

满二叉树在同样深度的二叉树中，结点数最多

满二叉树在同样深度的二叉树中叶子结点数最多

2.1.2 完全二叉树

定义：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的 1~n 个结点一一对应时，称为满二叉树

所以：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

从满二叉树最后一个结点开始往前连续去掉任意个结点，即是一棵完全二叉树

特点：

• 叶子结点要么在最后一层，要么在倒数第二层
• 对任意结点，如果其右子树最大层次为 i，其左子树最大层次为 i 或 i+1 (因为编号从左至右，因此完全二叉树任意结点的左边一定和右边有相同层次或更深)

性质：

• 具有n个结点的完全二叉树的深度为 [logn]+1； [x]为x的底，表示不大于x的最大整数

上述性质表明了完全二叉树结点数n与完全二叉树深度k之间的关系

• 如果对一棵具有n个结点的完全二叉树按层序编号(从第一层到第[logn]+1层，每层从左至右)，则对任一结点i (1<=i<=n), 有：

  • 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲节点是[i/2]
  • 如果2i > n, 则结点i为叶子节点，无左孩子；否则，其左孩子结点是 2i
  • 如果2i+1>n, 则结点i无右孩子；否则，其右孩子结点是2i+1

上述性质表明了完全二叉树中双亲结点编号和孩子结点编号之间的关系

3. 二叉树的顺序存储

如果是完全二叉树，则按满二叉树的编号规则进行编号，然后根据编号依次存放元素

如果不是完全二叉树，则空出不是连续存放的位置

顺序存储的缺点：

所以顺序存储适用于满二叉树和完全二叉树这种必定连续的二叉树

3.1 顺序二叉树(完全二叉树)

//顺序存储表示
#define MAX_SIZE 100
Typedef ElementTypy BiTree[MAX_SIZE];
BiTree tree;

结点规律

假设双亲结点下标为i，则左孩子下标为 2_i+1, 右孩子下标为2(i+1)即2_i+1+1(左孩子的下一个)

构造：

//通过前序递归创建完全二叉树（顺序的），i为数组下标, 只有通过传递i才知道左右子树下标
void initBiTree(int i) 
{
    int ele;
    scanf_s("%d", &ele);
    fflush(stdin);
    //如果输入为-1，代表输入结束
    if (ele == -1)
    {
        tree[i] = -1;
        return;
    }
    //结点赋值
    tree[i] = ele;
    //输入左孩子
    printf("左孩子结点：");
    initBiTree( 2*i + 1);
    //输入右孩子
    printf("右孩子结点：");
    initBiTree( 2*(i + 1));
}

前序遍历：

void scanTree(int i)
{
    if (tree[i] == -1)
    {
        return;
    }
    printf("结点：%d ", tree[i]);
    scanTree(2 * i + 1);
    scanTree(2 * (i + 1));
}

4. 二叉树的链式存储

链式结构的结点分为三个部分：右孩子指针域，左孩子指针域，数据域

//链式存储表示
typedef struct biNode
{
    ElementType data;
    struct biNode* lchild, *rchild;
}bi_node, *bi_node;

在n个节点的二叉链表中，有 n+1 个空指针域

因为n个结点必有2n个指针域(一个结点两个指针域)，除根结点外，每个结点有且只有一个双亲，所以有n-1个结点有双亲(即有n-1个边—即指针域用来存放了指向孩子的指针)，即意味着有n-1个指针域中不是NULL，因此 2n-(n-1)=n+1 于是剩下n+1个指针域是空指针域

三叉链表

在二叉链表的基础上添加一个指针域指向其双亲

typedef struct biNode
{
    ElementType data;
    struct biNode* lchild, *rchild, *parent;
}bi_node, *bi_node;

5. 二叉树的遍历**

遍历：顺着某一条搜索路径访问二叉树中的结点，使得每个结点均被访问一次，仅且一次 (访问可以包含多种含义，可以是对结点进行的各种处理，但要求是访问不能对结构进行破坏)

遍历目的：获得树中所有结点的一个线性排序

遍历用途：是二叉树进行CRUD和排序运算的前提

5.1 深度优先

若规定遍历为先左后右，则有：

• 先序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根

所以二叉树的遍历操作是一种递归操作

表达式的应用：

5.1.1 根据遍历序列确定二叉树

• 若二叉树中各结点的值均不相同，则二叉树结点的先序序列，中序序列，和后序序列都是唯一的
• 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一颗二叉树

先序和中序确定：由先序序列确定根；由中序序列确定左右子树

中序和后序确定：后序遍历，根节点必定在后序序列尾部。因此通过后序确定根，中序确定左右子树

单独先序遍历：能求解根，但不能求解左子树什么时候结束、右子树什么时候开始

注意：在创建二叉树的时候，一般有两种办法

• 在创建完成后，返回根节点的指针

以前序创建为例

node* InitBirTree2()
{
    node* retree;
    char ch;
    scanf("%c", &ch);
    setbuf(stdin, NULL);
    if (ch == '#')
    {
        retree = NULL;
    }
    else
    {
         //每个结点
        retree = (node*)malloc(sizeof(node));
        retree->flag = ch;
        retree->p_left = InitBirTree2();
        retree->p_right = InitBirTree2();
    }
    return retree;
}

• 传入一个二级指针，取出其中一级指针指向根结点，然后递归创建

以前序创建为例

//因为需要递归对每个结点进行赋值，如果只是单纯的传一级指针的话，因为每个结点中的左右孩子指针也是一级指针，单纯的赋值即是传值而不是传址，是无法在函数调用结束后依然存在的 
void InitBirTree(node** tree)
{
    char ch;
    scanf("%c", &ch);
    setbuf(stdin, NULL);
    if (ch == '#')
    {
        *tree = NULL;
        return;
    }
    else
    {
        *tree = (node*)malloc(sizeof(node));
        if (!*tree)
            exit(0);
        (*tree)->flag = ch;
        InitBirTree(&(*tree)->p_left);  //先建立左结点
        InitBirTree(&(*tree)->p_right);
    }
}

5.1.2 先序遍历

void firstPrint(node* tree)
{
    if (tree == NULL)
        return;
    printf(" %c", tree->flag); //根(可换为其他操作)
    firstPrint(tree->p_left); //👈
    firstPrint(tree->p_right); //👉
}

5.1.3 中序遍历

• 递归

void secondPrint(node* tree)
{
    if (tree == NULL)
        return;
    secondPrint(tree->p_left); //👈
    printf(" %c", tree->flag); //根(可换为其他操作)
    secondPrint(tree->p_right); //👉
}

• 非递归(后入先出，可以用栈实现)

  • 建立一个栈
  • 根结点进栈，遍历左子树
  • 根结点出栈，输出根结点，遍历右子树

//栈建立
treeNode trees[100];
int i=-1;
//栈进行中序遍历
//中序遍历为：左根右
//每次先找左子树，有的话就入栈，没有的话就出栈其根，最后才是转向右子树查找
void pre(pTreeNode tree)
{
    if (!tree)
    {
        return;
    }
    pTreeNode p = tree;
    while (p || isEmpty())
    {
        //如果结点不为空，入栈(左子树先入栈)
        if(p)
        {
            login(*p);
            p = p->left;
        }
        //因为是中序，所以只要左边没有就直接出栈根，并转向右子树
        else
        {
            //获取左结点(没有左子树，则直接出栈其双亲后转向判断有没有右子树，
            //如果没有，则再getTop一个根节点，继续循环判断)
                p = getTop();  //获得双亲
            logOut();     //出栈上层根
            printf("%d--->", p->ele);    //输出根节点(根)
            p = p->right;  //转向兄弟结点(右)
        }
    }
}

5.1.4 后序遍历

void thirtyPrint(node* tree)
{
    if (tree == NULL)
        return;
    thirtyPrint(tree->p_left); //👈
    thirtyPrint(tree->p_right); //👉
    printf(" %c", tree->flag); //根(可换为其他操作)
}

5.2 深度优先遍历算法分析

如果去掉输出语句，三种算法的访问路径是完全相同的，只是访问结点的时机不同

从虚线的出发点到终点的路径上，每个结点经过了3次

• 第一次经过时访问结点 = 前序遍历
• 第二次经过时访问结点 = 中序遍历
• 第三次经过时访问结点 = 后序遍历

5.3 广度优先(层次遍历)

• 使用队列
• 根节点进队

• 队不为空时循环：从队列中出列一个结点*p的同时

  • 若它有左孩子，将左孩子进队
  • 若它有右孩子，右孩子进队

treeNode queTree[100];
int top;
int base;
//广度优先遍历
void printQue(pTreeNode tree)
{
    pTreeNode p = tree;
    in(*p);    //入队根结点
    while (top!=base)
    {
        //出队同时该结点的左右孩子入队
        p = out();
        printf("%d--->", p->ele);
        //左右孩子入队
        if (p->left)
        {
            in(*p->left);
        }
        if (p->right)
        {
            in(*p->right);
        }
    }
}

6. 二叉树创建

6.1先序遍历创建二叉树

typedef struct tree
{
    char ele;
    struct tree* left, * right;
}treeNode, *pTreeNode;
void initTree(pTreeNode* tree)
{
    char ele;
    scanf("%d", &ele);
    if (ele == '#')
    {   
        //构造当前结点为空结点
        *tree = NULL;
        return;
    }
    *tree = (pTreeNode)malloc(sizeof(treeNode));
    (*tree)->ele = ele;
    (*tree)->left = NULL;
    (*tree)->right = NULL;
    initTree(&(*tree)->left);
    initTree(&(*tree)->right);
}

因为如果只有结点的话前序遍历构造出来的二叉树不是唯一的，因此引入空结点

可以看到，在没有引入空结点前这两颗树的先序序列都是：ABCDEGF

因此我们可以用#表示空结点来构造带空结点的二叉树，这里以构造树2为例：ABC##DEG##F####

可以通过传入二级指针建立二叉树，也可以通过返回根节点的指针来建立二叉树

7. 二叉树遍历算法应用

7.1复制二叉树

• 如果是空树，返回

• 否则，申请新的结点，复制根结点

  • 递归复制左子树
  • 递归复制右子树

//这里不需要修改旧树的内容，因此只用一级指针
void initTree(pTreeNode oldTree ,pTreeNode* tree)
{
    if (oldTree == NULL)
    {   
        //构造当前结点为空结点
        *tree = NULL;
        return;
    }
    *tree = (pTreeNode)malloc(sizeof(treeNode));
    (*tree)->ele = *oldTree->ele;
    (*tree)->left = NULL;
    (*tree)->right = NULL;
    initTree(oldTree->left, &(*tree)->left);
    initTree(oldTree->left, &(*tree)->right);
}

7.2 计算二叉树深度

7.2.1 最大深度

• 如果是空树，返回0，深度为0

• 否则：

  • 递归计算左子树的深度记为m
  • 递归计算右子树的深度记为n
  • 二叉树的深度则为m与n的较大者+1 (+1代表根)

int maxDepth(struct TreeNode* root){
    if(!root){
        return 0;
    }
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return 1 + ( (left) > (right)? (left) : (right) );
}

7.2.2 最小深度

int minDepth(struct TreeNode* root){
    if(!root)
        return 0;
    int left = minDepth(root->left);   //记录左子树层数
    int right = minDepth(root->right); //记录右子树层数
    if(left && right)
        return (left<right ? left:right)+1 ; //取两个子树最浅的那个
    else
      return 1+left+right;   //如果左子树或者右子树其中一个不存在(即只有一个根节点及其一个子结点两个结点)时，有两层，但left==0或right==0，而另外一个等于1，因此1+left+right即可
                            //或者只有根节点时，算一层，但left和right都是0，因此+1
}

7.3计算二叉树结点数

7.3.1 结点总数

• 如果是空树，则结点数为0，返回0
• 否则：结点个数为左子树的结点个数+右子树的结点个数再+1

int nodeCount(struct TreeNode* root)
{
    if(!root)
    {
        return 0;
    }
    return nodeCount(root->left)+nodeCount(root->right)+1;  //一棵树的结点数即左右根三个结点，如果更深，递归即可，+1为根结点计数
}

7.3.2 叶子结点数

• 如果是空树，则叶子结点数位0
• 否则，为左子树的叶子结点个数+右子树的叶子结点个数

int nodeCount(struct TreeNode* root)
{
    if(!root)
    {
        return 0;
    }
    //如果左右都为空，无后继, 说明是叶子结点
    if(!root->left && !root->right)
    {
        return 1;
    }
    return nodeCount(root->left)+nodeCount(root->right); 
}

7.4 LeetCode-617合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2){
    if( t1 == NULL && t2 == NULL)
        return NULL;
    struct TreeNode* newTree = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    //如果t1==null的话，就直接用t2即可
    if(t1 == NULL)
        return t2;
    //t2==null同理
    if(t2 == NULL)
        return t1;
    newTree->val = t1->val+t2->val;
    newTree->left = mergeTrees(t1->left, t2->left);
    newTree->right = mergeTrees(t1->right, t2->right);
    return newTree;
}

7.5 LeetCode-226翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

struct TreeNode* invertTree(struct TreeNode* root){
    if(root)
    {
        if(root->left || root->right)
        {
            struct TreeNode* ptemp = root->right;
            root->right = root->left;
            root->left = ptemp;
        }
        invertTree(root->left);
        invertTree(root->right);
    }
    return root;
}

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。 (意味着我能进google(确信))

7.6 LeetCode-965单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

bool isUnivalTree(struct TreeNode* root){
    if(root)
    {
        if(root->left)
            if(root->val != root->left->val)
                return false;
        if(root->right)
            if(root->val != root->right->val)
                return false;
        if(!isUnivalTree(root->left) || !isUnivalTree(root->right))
            return false;
    }
    return true;
}

8. 线索二叉树

普通的二叉树可以很快速的找到某个结点的左右孩子，但在一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点

Q: 如何寻找特定遍历序列中某个二叉树结点的前驱和后继

A：解决方法

• 通过遍历查询—-消耗时间

• 增设前驱和后继的指针域—-消耗空间

• 利用二叉树中的空指针域

二叉树当中有 n+1 个空指针域，但只有 n-1个 孩子，因此可以利用这些空指针域：

• 如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；

• 如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继

这种改变指向的指针称为‘ 线索 ’，加上了线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化

为区分每个结点上的左右指针到底是指向孩子的指针还是指向前驱后继的指针，因此对二叉链表中的每个结点增设两个标志域ltag和rtag用于区分指针域指向的是什么

• ltag = 0, 则左指针指向左孩子
• ltag = 1, 则左指针指向前驱
• rtag = 0, 则右指针指向右孩子
• rtag = 1, 则右指针指向后继

因此线索二叉树结构可更改为

typedef struct tree
{
    char ele;
    int lflag, rflag;
    struct tree* left, * right;
}treeNode, *pTreeNode;

为了方便操作，可以增设一个头结点，其数据如下：

• ltag=0, left指向根结点
• rtag=1, right指向遍历序列中最后一个结点
• 遍历序列中第一个结点得left域和最后一个结点的right域都指向头结点，避免悬空指针

8.1 中序线索化及其遍历

线索化

//中序线索化
void threadTree(pthTree root)
{
    //中序：左子树和根相连，根再和右子树相连
    //pre指针从左子树移动到根再移动到右子树上
    if (root)
    {
        threadTree(root->left);  //递归线索化左子树（左）
        //（根）
        if (!root->left)    //没有左孩子 
        {
            root->lflag = 1;   //前驱线索置为1，表示指向前驱
            root->left = pre;  //指向前驱
        }
        //右孩子为空，存放根结点
        if (pre && !pre->right)
        {
            pre->rflag = 1;
            pre->right = root;  //前驱右孩子指向后继，即当前结点root
        }
        pre = root;    //保持指向p的前驱（遍历序列下）
        threadTree(root->right);   //递归线索化右子树（右）
    }
}

遍历

void printTree(pthTree tree)
{
    if (tree)
    {
        pthTree tmp = tree;
        while (tmp)
        {
            //找到最左结点
            while (tmp->lflag == 0)
            {
                tmp = tmp->left;
            }
            printf("%c", tmp->ele);  //输出左结点
            //如果有后继
            if (tmp && tmp->rflag == 1)
            {
                tmp = tmp->right;
                printf("%c", tmp->ele);
            }
            //没有后继就找右子树
            tmp = tmp->right;
        }
    }
}

树和森林

森林：是m(m>=0)棵互不相交的树的集合

1.树的存储结构

1.1双亲表示法

定义结构数组存放结点，每个结点分为指针域和数据域—->其中指针域要存放双亲结点在数组中的位置

//结点的结构
typedef struct PNode
{
    ElementType data;          //数据类型
    int parent;                //双亲下标
}tree_node;
typedef struct ATree
{
    tree_node trees[MAX_SIZE];     //树组
    int r, n;                      //根的位置r和结点数n
}Atree;

找双亲简单，找孩子🚹

1.2孩子表示法(孩子链表)

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点右n个孩子链表(叶子结点的孩子链表为空)。而n个头指针又组成一个线性表，用顺序表存储这n个头指针

存储结构：

typedef struct ChildList    //孩子链表的结点
{
    int child_id;     //孩子结点的下标
    struct ChildList* next;        //指向该结点的兄弟结点
}ChildNode;
typedef struct Head    //表头
{
    char id;                 //数据域
    ChildNode* first_child;  //表头结点指向第一个孩子结点(最左边的孩子结点)
}List;
typedef struct Tree
{
    List node[MAX_SIZE];    //结点数组，存储头结点
    int n;
}tree;

构造：

ChildNode* ptail = NULL;
ChildNode* phead = NULL;
//初始化头结点
void InitChildlistHead()
{
    phead = (ChildNode*)malloc(sizeof(ChildNode));
    phead->child_id = -1;
    phead->next = NULL;
}
//初始化树
void InitTree(tree* trees)
{
    printf("输入结点数量n: ");
    scanf("%d", &trees->n);
    int sum = 0;
    for (int i = 0; i < trees->n; i++)
    {
        setbuf(stdin, NULL);
        printf("输入结点id："); //即数据
        scanf("%c", &trees->node[i].id);
        //为表头指针结点申请空间
        trees->node[i].first_child = (ChildNode*)malloc(sizeof(ChildNode));
        trees->node[i].first_child -> next = NULL;   //指向NULL
        printf("输入第%d个节点的孩子结点的数量：", i + 1);
        int nums;
        scanf("%d", &nums);
        sum += nums;
        //等于0时是叶子结点，空链表
        if (nums != 0)
        {
             ptail = trees->node[i].first_child;   //指向当前节点
             phead = ptail;
            for (int j = 0; j < nums; j++)
            {
                ChildNode* new_node = (ChildNode*)malloc(sizeof(ChildNode));   //申请第i+1个节点的孩子节点
                new_node->next = NULL;
                printf("输入第%d个孩子在顺序表中的位置：", j + 1);
                scanf("%d", &new_node->child_id);
                //链接
                ptail -> next = new_node;
                ptail = new_node;
            }
        }
    }
}

遍历：

void FindAllKids(tree* trees, char id)
{
    int isId = 0;
    for (int i = 0; i < trees->n; i++)
    {
        if (trees->node[i].id == id && trees->node[trees->node[i].first_child->next->child_id].id != 0)
        {
            ChildNode* p = trees->node[i].first_child->next;    //指向长子
            while (p != NULL)
            {
                isId = 1;
                printf("%c", trees->node[p->child_id].id);
                p = p->next;
            }
            printf("\n");
            break;
        }
    }
    if (isId == 0)
    {
        printf("木得孩子\n");
        return 0;
    }
}

1.3双亲孩子表示法

在孩子表示法的基础上在表头再增设一个存放双亲结点下标的指针域

typedef struct ChildList    //孩子链表的结点
{
    int child_id;     //孩子结点的下标
    struct ChildList* next;        //指向该结点的兄弟结点
}ChildNode;
typedef struct Head    //表头
{
    int parent;               //双亲结点下标
    char id;                 //数据域
    ChildNode* first_child;  //表头结点指向第一个孩子结点(最左边的孩子结点)
}List;
typedef struct Tree
{
    List node[MAX_SIZE];    //结点数组，存储头结点
    int n;
}tree;

1.4孩子兄弟表示法(二叉树表示法)

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

实际上只需要不断地添加子结点并进行相应判断即可完成

typedef struct Node{
    ElementType data;
    struct Node *child, *brother;
}*CSTree;

根节点的brother为NULL

实现设计：传入父结点和子结点，如果父父结点存在子结点，则将子结点链接到父结点的子结点上;如果不存在，则作为长子结点添加上去

void AddNode(CSTree parent, CSTree child)        // 添加子节点
{
    // 如果tail的当前结点没有兄弟，并且传入的父亲结点有孩子，这个就是兄弟结点，就接在tail后面
    if (tail->brother == NULL && parent->child != NULL)
    {
        tail->brother = child;
    }
    else
    {
        parent->child = child;            //如果传入的父结点没有孩子，直接添加child
    }
    tail = child;
}

可以这么进行赋值，模拟树结构

AddNode(&c[0], &c[1]);        // A->B
AddNode(&c[0], &c[2]);        // A->C
AddNode(&c[0], &c[3]);        // A->D
AddNode(&c[1], &c[4]);        // B->E
AddNode(&c[1], &c[5]);        // B->F

遍历方法可以参照二叉树的广度优先遍历和深度优先遍历

2. 树与二叉树的转换

利用二叉链表作媒介导出树与二叉树之间的关系，进行转换

给定一棵树，就可以找到唯一的一棵二叉树与之对应

2.1 树转为二叉树

1. 加线：在兄弟之间加一根连线
2. 去线：对每个结点，除了其最左边的孩子外，去除其与其余孩子之间的关系
3. 旋转：以根节点为轴心，将整棵树顺时针旋转45°

兄弟相连留长子

2.2 二叉树转为树

1. 加线：若结点p是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连起来 (因为左孩子的右孩子是兄弟结点)
2. 抹线：抹掉原二叉树中双亲与右孩子之间的连线
3. 调整：将结点按层次排列，形成树结构

左孩右右连双亲，去掉原来右孩线

3. 森林与二叉树的转换

3.1 森林转换成二叉树

二叉树与多棵树之间的关系

1. 将各棵树分别转换成二叉树
2. 将每棵树的根结点用线相连
3. 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 (其余树的根作为第一棵树的根的右孩子进行递归)

树变二叉根相连

3.2 二叉树转换为森林

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

去掉全部右孩线，孤立二叉再还原

4.树与森林的遍历

4.1 树的遍历

• 先根： 若树不为空，则先访问根结点，然后依次先序遍历各棵子树
• 后根： 若树不为空，则先依次先序遍历各棵子树，然后访问根结点 (树的后根遍历序列对应二叉树的中序遍历序列)
• 层次：若树不为空，则从上至下，从左至右依次访问树中每个结点

4.2森立的遍历

将森林看做是三部分构成：

1. 森林中第一棵树的根结点
2. 森林中第一棵树的子树
3. 森林中其它树构成的森林

先序遍历：若森林不为空，则

1. 访问森林中第一棵树的根结点
2. 先序遍历森林中第一棵树的子树
3. 先序遍历森林中(除一棵树外)其余树构成的森林

即从左至右依次对森林中的每一棵树进行先根遍历

中序遍历：若森林不为空，则

1. 中序遍历森林中第一棵树的子树
2. 访问森林中第一棵树的根结点
3. 中序遍历森林中(除第一棵树外)其余的树构成的森林

即从左至右依次对森林中的每一棵树进行后根遍历

哈夫曼树(**)

可以将if {} else if {} else {}转换为一棵树，这种树称为判断树，是用于描述分类过程的二叉树

假设每个等级有一定的频率，E=5%, D=15%, C=40%, B=30%, A= 10%，则有：

这种比较次数过于复杂，因此可以将判断树改进

这次10000个数据的比较次数为： 10000(35%+315%+240%+230%+2*10%) = 22000次

效率最高的判断树即可通过哈夫曼树找到

1.哈夫曼树的基本概念

• 路径：从树中一个结点到另一个结点之间的分支构成了这两个结点间的路径
• 结点的路径长度：两结点间路径上的分支数
• 树的路径长度：从树根到每一个结点的路径长度之和。记作TL

         TL(a) = 20                                              TL(b) = 16

• 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

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

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

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

相同的叶子数和相同的权值构造出来的二叉树的WPL可以是不同的

哈夫曼树(最优树)：即带权路径长度(WPL)最短的树

带权路径长度最短是在度相同的树中比较而得的结果，因此有最优二叉树，最有三叉树等

所以，最优二叉树即带权路径长度最短的二叉树，也叫做哈夫曼树

可以看出，权值较小的结点离根较远，权值越大的叶子离根越近，并且具有相同带权结点的哈夫曼树不唯一

2.哈夫曼树的构造

贪心算法：构造哈夫曼树时首先选择权值小的叶子节点

哈夫曼算法：

1. 根据n个给定的权值{w, w ……, w}构成n棵二叉树的森林F={T， T, ….., T}，其中T只有一个带权为W的结点
   森林树全根，n个权值n棵树

2. 根据贪心算法，在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根节点的权值之和
   选用两小造新树

3. 在F中删除这两棵树，同时将新得到的二叉树加入森林中
   删除两小添新人

4. 重复2，3，知道森林中只剩下一棵树为止，这棵树即哈夫曼树
   重复2，3剩单根

哈夫曼树的结点的度为0或2，没有度为1的结点

哈夫曼树由n个结点两两合并而来，因此n个结点会合并n-1次并且每次产生1个结点，于是总共产生n-1个新结点，于是包含n个叶子结点的哈夫曼树中共有n-1+n即2n-1个结点

3.哈夫曼树的实现

3.1顺序存储

结点结构

typedef struct Haffman
{
    int weight;    //权重
    int parent, left, right;
}HaffmanTree, *pHaffmanTree;

由n个根结点构成的哈夫曼树需要2n-1个空间来存储

为了方便一些，可以不使用0下标，从1开始存，存到下标为2n-1的位置

直接上代码了：

#include<stdio.h>
#include<stdlib.h>
#define WEIGHT_SIZE 8
#define MAX 2147483647
typedef struct Huffman
{
    int weight; //权重
    int parent, left, right;
}Huffman, *pHuffman;
int main(void)
{
    int weights[WEIGHT_SIZE] = { 5,29,7,8,14,23,3,11};
    //申请2n个空间
    pHuffman huffmanTree = (pHuffman)calloc(WEIGHT_SIZE * 2,sizeof(Huffman));
    //赋值权值（构造森林全是根，双亲和孩子都是0）
    for (int i = 1; i <= WEIGHT_SIZE; i++)
    {
        huffmanTree[i].weight = weights[i - 1];
    }
    //产生新结点：由于共产生n-1个新结点，因此从n+1开始，到2n-1结束，都是新结点
    for (int i = WEIGHT_SIZE + 1; i < WEIGHT_SIZE * 2; i++)
    {
        //让最小值足够大，保证所有的权值都比它小，才能找到parent=0的最小值
        int min1 = MAX;
        int min2 = MAX;
        int one = 1, two = 1;
        int j, k;
        //寻找权值最小的两个根
        for (j = 1; j <= i-1; j++)
        {
            //双亲为0的才用来构造新树
            if (huffmanTree[j].parent == 0 && huffmanTree[j].weight <= min1)
            {
                min1 = huffmanTree[j].weight;
                one = j;        
            }
        }
        //根赋值双亲
        huffmanTree[one].parent = i;
        //当前有多少个结点，就比较多少个结点
        for (k = 1; k <= i-1; k++)
        {
            if (huffmanTree[k].weight <= min2 && huffmanTree[k].parent == 0)
            {
                min2 = huffmanTree[k].weight;
                two = k;
            }
        }
        //两个根有了双亲结点
        huffmanTree[two].parent = i;
        //构造新树
        huffmanTree[i].weight = min1 + min2;
        huffmanTree[i].left = one;
        huffmanTree[i].right = two;
    }
    for (int i = 1; i < WEIGHT_SIZE * 2; i++)
    {
        printf("第%d个结点：权重为%d，parent为%d，左孩子下标为%d--权重为%d，右孩子下标为%d--权重为%d\n", i, huffmanTree[i].weight,
            huffmanTree[i].parent, huffmanTree[i].left, huffmanTree[huffmanTree[i].left].weight, huffmanTree[i].right, huffmanTree[huffmanTree[i].right].weight);
    }
    system("pause");
    return 0;
}

4.哈夫曼编码的思想

在远程通信中，将待传字符转换成二进制的字符串

• 定长编码：但这种方式较为浪费空间

• 
  <—-ABACCDA, 转换过来就是000011010，出现了0000的重码，0000可以表示AAAA/ABA/BB，这就是长度不等的编码的问题
  称为前缀编码

哈夫曼编码步骤

1. 统计字符集中每个字符在电文中出现的平均概率(概率越大，要求编码越短)

2. 利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值(频率)作为权值，构造哈夫曼树。则概率越大的结点，路径越短

3. 在哈夫曼树的每个分支上标上1或0

   • 结点的左分支为0，右分支为1
   • 把从根到每个叶子的路径上的标号连起来，作为该叶子代表的字符的编码

哈夫曼编码的性质：哈夫曼编码是最优前缀码

4.1算法实现

假设有已经构造好的哈夫曼树如下

则编码步骤为：

1. 申请二维数组，行宽为叶子结点数+1(存放’\0’)，列高为叶子结点数 (根到叶子结点的路径长度不会大于叶子结点数)

    2.申请临时的一维数组temp，用于在回溯的过程中存放哈夫曼编码，大小为n-1，多出来的1存放'\0'，因为哈夫曼树最高为n-1层(最多n-1个分支)

请把cd当成temp…

    3.从叶子结点向上回溯，每次回溯判断当前下标是双亲的左孩子还是右孩子；然后每次将判断对应的值存入临时一维数组temp中
    4.每次循环找完一个叶子结点的哈夫曼编码，就将每条路径的编码值(从临时一维数组中取)倒序存放入二维数组中
    5.重置temp数组，重复3，4，直到获取完所有叶子结点(n)的编码

最后：

    ![](https://gitee.com/antigenmhc/picture/raw/master/img/20201016175034.png#alt=image-20200307124730257)

代码如下

//求哈夫曼编码
    int i = 0, j = 0;//i为叶子个数，j保存回溯中的下标
    int top = 0, base = 0; //模拟栈
    char** HC, * temp;//二维数组，一维存放找到的编码
    HC = (char**)malloc(WEIGHT_SIZE * (WEIGHT_SIZE + 1)  * sizeof(char));  //编码表
    for (i = 1; i <= WEIGHT_SIZE; i++)
    {
        //申请i+1大小
        HC[i] = (char*)calloc(WEIGHT_SIZE+1, sizeof(char));
    }
    temp = (char*)calloc(WEIGHT_SIZE+1, sizeof(char));
    //从叶子结点(叶子结点就是一开始存的根结点)往上回溯，如果是上个结点的左孩子就赋值0，右孩子就赋值1
    //完成一个叶子结点的回溯后就按照逆序的方式将temp内容存入编码表中
    for (i = 1; i <= WEIGHT_SIZE; i++)
    {
        top = 0;
        j = i;
        //循环获取哈夫曼编码
        //重复回溯，直到根结点
        while (huffmanTree[j].parent != 0)
        {
            if (j == huffmanTree[huffmanTree[j].parent].left)
            {
                temp[top] = '0';
            }
            else
            {
                temp[top] = '1';
            }
            top++;
            j = huffmanTree[j].parent;   //向上回溯保存叶子到根的编码串
        }
        //复制哈夫曼编码,倒序赋值
        j = 0;
        while (temp[j] != '\0' && top>0)
        {
            HC[i][j] = temp[--top];
            j++;
        }
        memset(temp, '\0', WEIGHT_SIZE * sizeof(char));//重置temp数组
    } 
    for (int i = 1; i<=WEIGHT_SIZE ; i++)
    {
        printf("%c:  %s\n", huffmanTree[i].ele, HC[i]);
    }

5.文件的编码与解码

标准的ascii码用的7位存储一个字符

5.1编码

1. 输入各字符及其权值
2. 构造哈夫曼树
3. 进行哈夫曼树的编码
4. 查询编码表，得到各字符的哈夫曼编码

5.2解码

1. 输入各字符及其权值，构造哈夫曼树
2. 依次读入二进制码
3. 读入0，则走向左孩子；读入1，则走向右孩子
4. 一旦到达某叶子时，即可解码出字符
5. 然后再从根出发继续解码，直到结束