Fabian备忘录

人类资格证考核中

五、树与二叉树

发表于 更新于 分类于 ，
本文字数： 13k

基本概念

树是n（n大≥0）个结点的有限集合，n=0时称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点；
  2. 当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根节点的子树。

非空树的特性：

  • 有且仅有一个根节点；
  • 没有后继的结点称为“叶子结点”；
  • 有后继的结点称为“分支节点”；
  • 除了根节点外，任何一个结点都有且仅有一个前驱；
  • 每个结点可以有0个或多个后继；

结点和树的属性

  • 结点间的路径：只能从上往下数；
  • 路径长度：两个结点经过了几条边；
  • 结点的层次（深度）：从上往下数；
  • 结点的高度：从下往上数；
  • 数的高度（深度）：总共多少层
  • 结点的度：有几个孩子（分支）；
  • 树的度：各个结点的度的最大值；

有序树和无序树

  • 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换；
  • 无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换；

选择哪种树，具体看用树存什么，是否需要用结点的左右位置反映某些逻辑关系；

树和森林

森林是m（m≥0）棵互不相交的树的集合

常考性质

一、结点数=总度数+1

结点的度意思是结点有几个孩子，相加之后可以求出所有子节点个数，然后需要把根节点也计算上，所以+1；

 

二、区分度为m的树和m叉树

度为m的树 m叉树
树的度：各结点的度的最大值 m叉树：每个结点最多只能有m个孩子的树
任意结点的度≤m（最多m个孩子） 任意结点的度≤m（最多m个孩子）
至少有一个结点的度=m(要保证有一个结点的孩子数量为m) 允许所有结点的度都<m
一定是非空树，至少有m+1个结点 可以是空树

 

三、度为m的树的第i层至多有个结点

 

四、高度为h的m叉树至多有个结点

其实就是等比数列求和，首项为1；

 

五、高度为h的m叉树至少有h个结点；高度为h、度为m的树至少有h+m-1个结点

求至少，那么按照最少的来算就行；m叉树就让每一层的度都为1；规定树的度为m，那就只让尾结点的数量为m；

 

六、具有n个结点的m叉树的最小高度为

求m叉树的最小高度，那么就让树的每一层的度都为m。已知第h层最多有个结点，则

​

二叉树

二叉树是n（n大≥0）个结点的有限集合：

  1. n=0时为空二叉树；
  2. n>0时，由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树分别是一颗二叉树

特点： + 每个结点至多只有两棵子树； + 二叉树是有序树，左右子树不能颠倒； + 要注意区分度为2的有序树，度为2的有序树，至少需要有一个结点有2个孩子；

二叉树的五种状态：空树、只有左子树、只有右子树、只有根节点、左右子树都有；

几种特殊的二叉树

  • 满二叉树

一颗高度为h，且含有个结点的二叉树

  • 只有最后一层有叶子节点；
  • 不存在度为1的结点；
  • 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点的父节点为

 

  • 完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应，称为完全二叉树。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

  • 只有最后两层可能有叶子结点；
  • 最多只有一个度为1的结点；
  • 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点的父节点为；
  • i≤为分支结点，i>为叶子节点；
  • 如果一个结点只有一个孩子，那么一定是左孩子；

 

  • 二叉排序树

一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：

  • 左子树上的所有节点的关键字均小于根结点的关键字；
  • 右子树上所有结点的关键字均大于根节点的关键字
  • 左右子树分别又是一棵二叉排序树；

二叉排序树可以用于元素的排序、搜索

 

  • 平衡二叉树

树上任意结点的左子树和右子树的深度之差不超过1；

二叉树常考性质

  • 一、设非空二叉树中度为0、1、2的结点个数分别为、、，则

推导：假设树中的结点总数为n，则可得：

  1. n = + +
  2. 已知数的结点数=总度数+1，则n=+2+1

两式联立可得

 

  • 二、二叉树第i层至多有个结点(i≥1)

 

  • 三、高度为h的二叉树至多有个结点(此时是满二叉树)

 

完全二叉树常考性质

  • 一、具有n个结点的完全二叉树的高度为h=或

高为h的满二叉树共有个结点；

高为h-1的满二叉树共有个结点；

高为h的完全二叉树至少个结点，至多个结点；

 

  • 二、对于完全二叉树，可以由结点数n推出度为0、1、2的结点个数、、

突破点：完全二叉树最多只有一个度为1的结点，即要么是0，要么是1；

又由可得，,一定为奇数，则：

  1. 若完全二叉树有2k（偶数）个结点，则必有;
  2. 若完全二叉树有2k-1(奇数)个结点，则必有，;

二叉树的存储结构

顺序存储

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MaxSize 100
struct TreeNode{
    ElemType value;    //结点中的数据元素
    bool isEmpty;      //结点是否为空
}

//定义一个长度为MaxSize的数组t，按照从上至下，从左至右的顺序依次存储完全二叉树中的各个节点
TreeNode t[MaxSize];

for(int i = 0; i < MaxSize; i++)
{
    t[i].isEmpty = true;
}

可以让数组的第一个位置空缺，保证数组下标和结点编号位置一致

基本操作：

  • i的左孩子——2i；
  • i的右孩子——2i+1;
  • i的父节点——或

若完全二叉树共有n个结点，则：

  • 判断i是否有左孩子——2i≤n?
  • 判断i是否有右孩子——2i+1≤n?
  • 判断i是否是叶子/分支结点？——i>n/2

重要：二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来，这样才能计算逻辑关系。所以顺序存储很浪费空间，最坏的情况，高度为h且每个结点都只有一个右孩子，那么也依旧需要个存储单元。所以二叉树的顺序存储结构只适合存储完全二叉树。

链式存储

二叉链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct BiTNode{
    ElemType data;          //数据域
    struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode, *BiTree;

//定义一颗空树
BiTree root = NULL;

//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchile = NULL;

//插入新结点
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchile = NULL;
root->lchild = p;   //作为根节点的左孩子

对于采用链式存储的二叉树，如果有n个结点，那么就会有2n个指针。其中除根节点外，每个结点都有指针指向自己，即n-1个指针指向具体结点，那么就会剩下n+1个结点指向空链域。可以利用这些空链域构造线索二叉树。

上面的链式存储找到指定结点的左右孩子的操作非常简单，但是如果想寻找父节点，那么就需要从头遍历。如果实际操作中需要频繁的寻找父节点，那么可以用三叉链表：

1
2
3
4
5
typedef struct BiTNode{
    ElemType data;          //数据域
    struct BiTNode *lchild,*rchild; //左右孩子指针
    struct BiTNode *parenty;    //父节点指针
}BiTNode, *BiTree;

但考试中基本不涉及这种场景，需要针对二叉链表进行遍历。

二叉树的遍历

遍历就是按照某种次序把所有结点都访问一遍。对于树形结构来说，总体上有两种遍历顺序，一种是层序遍历：基于树的层次特性确定的次序规则；另一种是先：基于树的递归特性确定的次序规则。

先中后序遍历

  • 先序遍历：根左右（NLR）
  • 中序遍历：左根右（LNR）
  • 后序遍历：左右根（LRN）

上图的先序遍历：ABDECFG；中序遍历：DBEAFCG；后序遍历：DEBFCGA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchlid;
}BiTNode, *BiTree;

//先序遍历
void PreOrder(BiTree T)
{
    if(T != NULL){
        visit(T);             //访问根节点
        PreOrder(T->lchild);  //递归遍历左子树
        PreOrder(T->rchild);  //递归遍历右子树
    }
}

//中序遍历
void InOrder(BiTree T)
{
    if(T != NULL){
        InOrder(T->lchild);  //递归遍历左子树
        visit(T);             //访问根节点
        InOrder(T->rchild);  //递归遍历右子树
    }
}

//后序遍历
void PostOrder(BiTree T)
{
    if(T != NULL){
        PostOrder(T->lchild);  //递归遍历左子树
        PostOrder(T->rchild);  //递归遍历右子树
        visit(T);             //访问根节点
    }
}

层序遍历

算法思想：

  1. 初始化一个辅助队列；
  2. 根节点入队
  3. 若队列非空，则队头结点出队，访问该节点，并将其左、右孩子插入队尾
  4. 重复3直到队列为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchlid;
}BiTNode, *BiTree;

typedef struct LinkNode{
    BiTNode *data;   //存指针即可，不需要存结点真实数据，节省空间
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front, *rear;  //队头队尾
}LinkQueue;

void LevelOrder(BiTree T)
{
    LinkQueue Q;
    InitQueue(Q);     //初始化辅助队列，使用链队列方便扩展
    BiTree p;
    EnQueue(Q, T);    //将根节点入队
    while(!IsEmpty(Q))  //队列不空则循环
    {
        DeQueue(Q, p);    //队头结点出队
        visit(p);         //访问出队结点
        if(p->lchild != NULL)
            EnQueue(Q, p->lchild);   //左孩子入队
        if(p->rchild != NULL)
            EnQueue(Qm p->rchild);  //右孩子入队
    }
}

由遍历序列构造二叉树

不论遍历序列是前序、中序、后序还是层序，一个遍历序列都可以对应多种二叉树形态。如果只给出一颗二叉树的前/中/后/层序遍历中的一种，不能唯一确定一颗二叉树。

但只要给出中序遍历，那么任意结合前序、后序、层序遍历的一种，即可唯一确定一颗二叉树。

 

前序+中序：

 

后序+中序：

 

层序+中序：

 

核心就是找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点。

必须要结合中序遍历序列，否则无法确定。

线索二叉树

二叉树的遍历并不能向线性表一样从任意结点开始访问，如果要找某个结点的前驱或者后继，必须要从根节点开始。

由前面的结论可得，n个结点的二叉树，有n+1个空链域，可以用来记录前驱、后继的信息。我们根据中序遍历的顺序来指定前驱和后继。这样我们就可以方便的找到其前驱和后继，方便遍历操作。

线索二叉树中，只有线索指向的结点才能称为前驱(后继)

1
2
3
4
5
6
7
//线索二叉树结点
//左右线索标志tag==0表示指针指向孩子，tag==1表示指针是线索
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;   
}ThreadNode,*ThreadTree;

先序线索二叉树和后序线索二叉树和中序一样，只是前驱和后序不同而已。

二叉树的线索化

对二叉树进行线索化的过程：直接进行遍历，遍历的过程中进行线索化。用一个指针pre记录当前访问结点的前驱结点

要注意最后一个结点的rchile、rtag的处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//中序线索化
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;   
}ThreadNode,*ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//中序遍历，一边遍历一边线索化
void InThread(ThreadTree T)
{
    if(T != NULL){
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

void visit(ThreadNode* q)
{
    if(q->lchild == NULL)  //左子树为空，建立前驱线索
    {
        q->lchild = pre;
        q->ltag = 1;
    }

    if(pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;  //建立前驱结点的后继线索
        pre->rtag = 1;
    }

    pre = q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T)
{
    pre = NULL;   //pre初始为空
    if(T != NULL)  //非空二叉树才能线索化
    {
        InThread(T);  //中序线索化二叉树
        if(pre->rchild == NULL)
        {
            pre->rtag = 1;  //处理遍历的最后一个结点
        }
    }
}

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//先序线索化
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;   
}ThreadNode,*ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//先序遍历，一边遍历一边线索化
void PreThread(ThreadTree T)
{
    if(T != NULL){
        visit(T);
        //这里必须判断一下lchild不是前驱线索
        //先序遍历的顺序是根左右，如果一个结点没有左子树，那么线索化后左子树指针就会指向这个结点的根节点
        //而此时pre指针指向的就是其根节点
        //此时发生的事情就是结点的左子树指向pre(即根结点)，然后pre指向自身
        //根据先序遍历根左右的顺序，这个结点访问完后就要访问其左子树，这样又造成了循环访问，再也出不来了
        if(T->ltag == 0){
            PreThread(T->lchild);
        }
        PreThread(T->rchild);
    }
}

void visit(ThreadNode* q)
{
    if(q->lchild == NULL)  //左子树为空，建立前驱线索
    {
        q->lchild = pre;
        q->ltag = 1;
    }

    if(pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;  //建立前驱结点的后继线索
        pre->rtag = 1;
    }

    pre = q;
}

//先序线索化二叉树T
void CreateInThread(ThreadTree T)
{
    pre = NULL;   //pre初始为空
    if(T != NULL)  //非空二叉树才能线索化
    {
        PreThread(T);  //中序线索化二叉树
        if(pre->rchild == NULL)
        {
            pre->rtag = 1;  //处理遍历的最后一个结点
        }
    }
}

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//后序线索化
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;   
}ThreadNode,*ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//后序遍历，一边遍历一边线索化
void PostThread(ThreadTree T)
{
    if(T != NULL){
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}

void visit(ThreadNode* q)
{
    if(q->lchild == NULL)  //左子树为空，建立前驱线索
    {
        q->lchild = pre;
        q->ltag = 1;
    }

    if(pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;  //建立前驱结点的后继线索
        pre->rtag = 1;
    }

    pre = q;
}

//后序线索化二叉树T
void CreateInThread(ThreadTree T)
{
    pre = NULL;   //pre初始为空
    if(T != NULL)  //非空二叉树才能线索化
    {
        PostThread(T);  //中序线索化二叉树
        if(pre->rchild == NULL)
        {
            pre->rtag = 1;  //处理遍历的最后一个结点
        }
    }
}

线索二叉树找前驱、后继

中序线索二叉树中找到指定结点*p的中序后继next：

  1. 如果p->rtag == 1 ，则next=p->rchild;
  2. 如果p->rtag==0，则p必有右孩子，next=p右子树中最左下结点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode* FirtstNode(ThreadNode *p)
{
    //循环找到最左下结点
    while(p->ltag == 0){
        p = p->lchild;
    }
    return p;
}

//在中序线索二叉树中找到结点P的后继结点
ThreadNode* NextNode(ThreadNode *p)
{
    //右子树最左下结点
    if(p->rtag == 0){
        return FirstNode(p->rchild);
    }
    else{
        return p->rchild;
    }
}

//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
//不需要嵌套，空间复杂度O(1)
void Inorder(ThreadNode *T){
    for(ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
    {
        visit(p);
    }
}

 

在中序线索二叉树中找到指定结点*p的中序前驱pre

  1. 若p->ltag == 1,则pre = p->lchild
  2. 若p->ltag == 0,则p必有左孩子。pre=p的左子树中最右下的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//找到以P为根的子树中，最后一个被中序遍历的结点
ThreadNode* LaststNode(ThreadNode *p)
{
    //循环找到最左下结点
    while(p->rtag == 0){
        p = p->rchild;
    }
    return p;
}

//在中序线索二叉树中找到结点P的前驱结点
ThreadNode* PreNode(ThreadNode *p)
{
    //左子树最右下结点
    if(p->rtag == 0){
        return LaststNode(p->lchild);
    }
    else{
        return p->lchild;
    }
}

//对中序线索二叉树进行逆向中序遍历(利用线索实现的非递归算法)
//不需要嵌套，空间复杂度O(1)
void RevInorder(ThreadNode *T){
    for(ThreadNode *p = LaststNode(T); p != NULL; p = PreNode(p))
    {
        visit(p);
    }
}

 

在先序线索二叉树中找到指定结点*p的先序后继next:

  1. 若p->rtag == 1，则next = p->rchild;
  2. 若p->rtag == 0，p必有右孩子
    1. 若p有左孩子，则先序后继为左孩子
    2. 若p没有作海周四，则先序后继为右孩子

 

在先序线索二叉树中找到指定节点*p的先序前驱pre

  1. 若p->ltag == 1，则next = p->lchild;
  2. 若p->ltah == 0,则只能用土办法从头开始先序遍历了。先序遍历中左右子树的结点只可能是根的后继，不可能是根的前驱

 

在后序线索二叉树中找到指定结点*p的后序前驱pre：

  1. 若p->ltag == 1,则pre=p->lchild;
  2. 若p->ltag == 0,则p必有左孩子
    1. 若p有右孩子，则后序前驱为右孩子；
    2. 若p没有右孩子，则后序前驱为左孩子

 

在后序线索二叉树中找到指定结点*p的后序后继next

  1. 若p->rtag == 1，则next = p->rchild;
  2. 若p->rtag == 0,则只能用土办法从头开始后序遍历，后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继

树的存储结构

二叉树的顺序存储，可以按照完全二叉树中的结点顺序，将各个结点存储到数组的对应位置。数组下标反映结点之间的逻辑关系。但对于普通的树，一个分支结点可以有多棵子树，没有完全树的概念。只依靠数组下标，无法反映结点之间的逻辑关系。

双亲表示法

顺序存储。

思路：用数组顺序存储各个结点。每个结点中保存数据元素、指向双亲结点的“指针”(数组下标)。非根节点的双亲指针=父节点在数组中的下标、根节点的双亲指针为-1

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAX_TREE_SIZE 100  

//结点定义
#define struct{
    ElemType data;      //数据元素
    int parant;         //双亲位置域
}PTNode;

//类型定义
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];    //双亲表示
    int n;                          //结点数
}PTree;

森林是m棵互不相交的数的集合。双亲表示法也可以存储森林。

  • 优点：找父节点很方便，直接读取parant；
  • 缺点：找孩子不方便，只能从头到尾遍历整个数组；

适用于找父亲多，找孩子少的场景，比如“并查集”。

孩子表示法

既使用顺序存储，也使用链式存储。

思路：用数组顺序存储各个结点。每个结点中保存数据元素和孩子链表的头指针。用一个链表记录一个结点的所有孩子的编号，结点的指针域指向第一个孩子编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAX_TREE_SIZE 100  

struct CTNode{
    int child;      //孩子节点在数组中的位置
    struct CTNode *next;   //下一个孩子
}

typedef struct {
    ElemType data;
    struct CTNode *firstChild;      //第一个孩子
}CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;   //结点数和根结点位置
}

孩子表示法也可以存储森林。但需要记录多个根的位置。

  • 优点：找孩子很方便；
  • 缺点：找双亲不方便，只能遍历每个链表；

使用于找孩子多，找父亲少的场景，比如服务流程树。

孩子兄弟表示法

链式存储方式。

孩子兄弟表示法与二叉树类似，采用二叉链表实现。每个结点内保存数据元素和两个指针，但两个指针的含义和二叉树不同。

1
2
3
4
5
6
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstChild;      //指向第一个孩子
    struct CSNode *nextsibling;     //指向右兄弟
}

孩子兄弟表示法也可以存储森林。每棵树的树根都看成平级的关系，当作兄弟结点处理。

由于存储视角上看形态和二叉树雷系，所以是重要考点：树、森林和二叉树的转换。

树、森林转二叉树

树转二叉树

  1. 先在二叉树中，画出一个根结点；
  2. 按照树的“层序”依次处理每个结点：如果当前处理的结点在树中有孩子，就把所有孩子结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方。

森林转二叉树

森林中各个树的根结点均视为平级的兄弟关系：

  1. 先把所有树的根结点画出来，在二叉树中用右指针串成糖葫芦
  2. 按照森林的“层序”依次处理每个结点：如果当前处理的结点在树中有孩子，就把所有孩子结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方。

二叉树转树、森林

二叉树转树：

  1. 先画出树的根节点；
  2. 从树的根节点开始，按照树的“层序”恢复每个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点的下方；

二叉树转森林：

  1. 先把二叉树的根节点和“一整串右指针糖葫芦”拆下来，作为多棵树的根节点；
  2. 按照森林的“层序”恢复每个结点的孩子：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点的下方；

树和森林的遍历

树的遍历分为三种：

  1. 先根遍历：若树非空，先访问根节点，再依次对每棵子树进行先根遍历(根左右)；树的先根遍历序列与这棵树相应的二叉树的先序序列相同；
  2. 后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再访问根节点(左右根)。树的后根遍历序列与这棵树对应的二叉树的中序序列相同
  3. 层次遍历(用辅助队列实现)：
    1. 若树非空，则根节点入队；、
    2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
    3. 重复2直到队列为空

先根遍历和后根遍历是深度优先，层次遍历是广度优先

 

森林的遍历分为两种：

  1. 先序遍历(效果等同于依次对各个树进行先根遍历，或者直接把森林转换成二叉树，看二叉树的先序遍历序列)：
    1. 访问森林中第一棵树的根节点；
    2. 先序遍历第一棵树中根节点的子树森林
    3. 先序遍历除第一棵树之后剩余的树构成的森林。
  2. 中序遍历(效果上等同于依次对各个树进行后根遍历，或者看对应二叉树的中序遍历序列):
    1. 中序遍历森林中第一棵树的根节点的字数森林
    2. 访问森林中第一棵树的根节点
    3. 中序遍历除去第一棵树之后剩余的树

哈夫曼树

  • 结点的权：有某种现实含义的数值，比如表示结点的重要性等。

  • 结点的带权路径长度：从树的根到该节点的路径长度（经过的边数）与该结点上权值的乘积。
  • 树的带权路径长度：树中所有叶节点的带权路径长度之和。

在含有n个带权叶结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树

哈夫曼树的构造

给定n个权值分别为、、、的结点，构造哈夫曼树的算法描述如下： 1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F 2. 构造一个新的结点，从F中选取两棵根节点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根节点的权值之和； 3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中； 4. 重复2、3，直到F中只剩下一棵树为止；

  • 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大；
  • n个结点总共合并n-1次，每次合并都会导致增加一个结点，最终的结点总数为2n-1；
  • 哈夫曼树中不存在度为1的结点；
  • 哈夫曼树并不唯一，但每个哈夫曼树的带权路径长度必然相同且为最优。

哈夫曼编码

哈夫曼编码常用于数据压缩。

考虑以下场景，假设需要通过编码传递A、B、C、D的选择题答案，首先想到的是固定长度编码：每个字符用相等长度的二进制位表示。比如用ASCII编码，每个字符用8bit来表示A(01000001)、B(01000010)、C(01000011)、D(01000100).可见这种方式效率极低，如果有100道题目，总共要花费800bit。

首先想到的优化方式是，只有4个选项，那么每个字符可以只用长度为2的二进制表示：A(00)、B(01)、C(10)、D(11).这也是固定长度编码，100道题的二进制长度只有200bit.

假设已经知道了100题中有80个C，10个A，8个B，2个D，那么可以根据这个数字来构造哈夫曼树.

构造出来后，可以用0表示C，10表示A，111表示B，110表示D。这就是可变长度编码——允许使用不同字符用不等长的二进制位表示。这100道题最终只需要130bit。

哈夫曼编码是前缀编码：没有一个编码是另一个编码的前缀。前缀编码解码时无歧义。

哈夫曼编码：字符集中的每个字符作为一个叶子节点，各个字符出现的频度作为结点的权值，构造哈夫曼树。哈夫曼树不唯一，所以哈夫曼编码不唯一。