数据结构第五章(一)二叉树部分代码

顺序存储结构

#ifndef TREE_H
#define TREE_H

#include
#include
#include

// 二叉树的顺序存储结构，适合于完全二叉树和满二叉树
#define MaxSize 100
typedef int ElemType;
typedef struct TreeNode{
    ElemType value;//结点中的数据元素
    bool isEmpty;//结点是否为空
}TreeNode;
// TreeNode t[MaxSize] //初始化长度为MaxSize的数组t
// for(int i=0;i
//     t[i].isEmpty=true;//初始化标记为空
// }

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 顺序链表常用于存储完全二叉树或者满二叉树，如果用来表示普通二叉树，只能添加一些并不存在的空结点来让每一个结点和完全二叉树的结点向对应。

顺序链表的应用：已知一棵二叉树按照顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近的公共祖先结点的值

#include "tree.h"

// #define MaxSize 100
// 已知一棵二叉树按照顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近的公共祖先结点的值
// 按照完全二叉树的存储形式,其实就是求两个数的除法

// 正解
int Common(TreeNode t[],int i,int j){
    if(t[i].isEmpty||t[j].isEmpty)//结点不存在
        return -1;
    while(i!=j){
        if(i>j)
            i/=2;
        else
            j/=2;
    }
    return i;
}
void test127(){
    // 初始化一个顺序存储结构的树
    TreeNode T[MaxSize];
    for(int i=0;i<MaxSize;i++){
        T[i].value=i;
        T[i].isEmpty=true;
    }
    int len=10;
    // 构造一个二叉树为1-10
    for(int i=1;i<=len;i++){
        T[i].isEmpty=false;
    }
    // Common(T,1,2);
    printf("%d\n",Common(T,1,2));
    
}
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

链式存储结构

所有的测试用例都是：ABD##E##CF##G##

// 二叉树的链式存储
typedef struct BiTNode{
    DataType data;
    struct BiTNode *lchild,*rchild;
    // struct BiTNode *parent;//用来方便存储父节点指针，这也是所谓的三叉链表
}BiTNode,*BiTree;
1
2
3
4
5
6

创建一棵树

这里要注意的是，树的定义是递归定义的，所以创建的时候也是用递归创建的。这里使用#字符表示NULL，表示结束，并且使用的是先序法创建一个树，也即是说，输入的字符顺序和先序法获得的结点顺序是一致的。

// create
void createTree(BiTree *T){
    DataType ch;
    scanf("%c",&ch);
    // while(getchar()!='\n');//当获取一个有效字符时结束循环
    if(ch=='#'){
        *T=NULL;
        return;
    }
    else{
        *T=(BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data=ch;
        createTree(&((*T)->lchild));
        createTree(&((*T)->rchild));
    }
}

void testCreate(){
    BiTree T;
    printf("请连续输入字符，中间不要有空格和换行。。。\n");
    createTree(&T);//ABD##E##CF##G##
    printf("create ok");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二叉树的先序遍历、中序遍历、后序遍历

对先序遍历、中序遍历、后序遍历的理解，其实就是关于进入递归的三个位置(前序位置、中序位置、后序位置)的操作。可以看看这个博文

顺便提一句：递归一般都有前序位置、后序位置，可以用来做一些特殊操作，比如链表的倒置

void visit(BiTree T){
    printf("%c ",T->data);
}
// 先序遍历
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);
    }
}
void testCreate(){
    BiTree T;
    printf("请连续输入字符，中间不要有空格和换行。。。\n");
    createTree(&T);
    printf("create ok\n");
    PreOrder(T);
    printf("\n");
    InOrder(T);
    printf("\n");
    PostOrder(T);
}
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

求树的深度——后序遍历的应用

// 求树的深度——后序遍历的应用
int treeDepth(BiTree T){
    if(T==NULL){
        return 0;
    }
    else{
        int l=treeDepth(T->lchild);
        int r=treeDepth(T->rchild);
        return l>r?l+1:r+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11

遍历的非递归实现

把第一个递归操作变成访问左子树，把第二个递归操作变成访问右子树，其他的打印操作和递归实现是一致的。

这里在实现的时候要注意的一个点就是，入栈的不是树的一个结点，而是一整棵树，不然会出现树断开无法访问的情况。

#ifndef LISTACK_H
#define LISTACK_H
#include
#include
#include
#include "tree.h"
// 链栈，不带头结点的情况
typedef BiTree TreeType;//入栈的节点是一棵树，不是树的一个节点，否则树会断层
typedef struct LinkNode{
    TreeType data;//数据域
    struct LinkNode *next;
}LinkNode,*LinkStack;

bool InitStack4(LinkStack *s);//初始化不带头结点的栈
bool Push4(LinkStack *s,TreeType x);//入栈
bool Pop4(LinkStack *s,TreeType *x);//出栈
void printfStack4(LinkStack s);//打印
bool EmptyStack4(LinkStack s);//空栈
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include "listack.h"


bool InitStack4(LinkStack *s){
    *s=NULL;//栈空,不带头结点
    return true;
}
bool EmptyStack4(LinkStack s){
    if(s==NULL){
        return true;
    }
    return false;
}
// x在这里表示的是一棵树
bool Push4(LinkStack *s,TreeType x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;
    p->data=x;
    // 这一步很容易错
    p->next=(*s);
    (*s)=p;
    return true;
}
bool Pop4(LinkStack *s,TreeType *x){
    // printf("Pop-%d",x);
    if((*s)==NULL)//空表
        return false;
    LinkNode *p=*s;
    *s=(*s)->next;
    *x=p->data;
    free(p);

    return true;
}
// void printfStack4(LinkStack s){
//     // s=NULL;
//     LinkNode *p=s;
//     while(p!=NULL){
//         printf("%c->",p->data);
//         p=p->next;
//     }
//     printf("\n");
// }

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

//前序遍历
void PreOrder2(BiTree T){
    LinkStack S;
    InitStack4(&S);
    BiTree p=T;

    while(p!=NULL||!EmptyStack4(S)){
        if(p!=NULL){
            visit(p);
            Push4(&S,p);
            p=p->lchild;
        }else{
            Pop4(&S,&p);
            p=p->rchild;
        }
    }
    printf("\n");
}
//中序遍历
void InOrder2(BiTree T){
    LinkStack S;
    InitStack4(&S);
    BiTree p=T;

    while(p!=NULL||!EmptyStack4(S)){
        if(p!=NULL){
            Push4(&S,p);
            p=p->lchild;
        }else{
            Pop4(&S,&p);
            visit(p);
            p=p->rchild;
        }
    }
    printf("\n");
}
// 后序遍历
void PostOrder2(BiTree T){
    LinkStack S;
    InitStack4(&S);
    BiTree p=T;
    BiTree r=NULL;

    while(p!=NULL||!EmptyStack4(S)){
        if(p!=NULL){
            Push4(&S,p);
            p=p->lchild;
        }else{
            GetTop(S,&p);
            if(p->rchild!=NULL&&p->rchild!=r)//右子树存在且没有被访问过
                p=p->rchild;
            else{
                Pop4(&S,&p);
                visit(p);
                r=p;
                p=NULL;//每一次访问完一个结点都相当于遍历完以该结点为根的子树，所以要置位为NULL
            }
        }
    }
    printf("\n");
}
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
59
60
61

对于非递归的后序遍历算法，当访问一个结点的时候，栈中的结点恰好是p结点的所有祖先，并且由低向顶加上被访问的结点本身，刚好是从根结点到p结点的一条路径，用这个思路可以求根结点到某一个结点的路径、求两个结点的最近公共祖先等。

层次遍历

初始化一个空队列，将根节点入队列，然后出队，如果出队的结点有左右孩子，就把左右孩子入队列，以此循环一直到队列为空。

// 层次遍历
void levelOrder(BiTree T){
    LQueue Q;
    InitLQueue_withHead(&Q);
    BiTree p=NULL;
    EnLQueue_withHead(&Q,T);


    while(!LQueueEmpty_withHead(Q)){
        DeLQueue_withHead(&Q,&p);
        printf("%c ",p->data);
        if(p->lchild!=NULL)
            EnLQueue_withHead(&Q,p->lchild);
        if(p->rchild!=NULL)
            EnLQueue_withHead(&Q,p->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

线索二叉树

无论是先序、中序、后续的线索二叉树的实现，都要记得最后一个结点要单独处理。

#ifndef THREADTREE_H
#define THREADTREE_H
#include
#include
#include
#include "tree.h"

// typedef char ElemType;
typedef struct ThreadNode{
    DataType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;//左右线索标志,tag=0,表示指向孩子，tag=1表示的是线索
}ThreadNode,*ThreadTree;

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 创建一棵普通的树

void createThreadTree(ThreadTree *T){
    DataType ch;
    scanf("%c",&ch);
    // while(getchar()!='\n');//当获取一个有效字符时结束循环
    if(ch=='#'){
        *T=NULL;
        return;
    }
    else{
        *T=(ThreadNode *)malloc(sizeof(ThreadNode));
        (*T)->data=ch;
        (*T)->ltag=0;//创建一棵树的时候不要忘记初始化，不然可能会出错
        (*T)->rtag=0;
        createThreadTree(&((*T)->lchild));
        createThreadTree(&((*T)->rchild));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

先序线索二叉树的实现

先序线索二叉树的实现中，要注意避免死循环的情况。比如当前树的根节点（假设为A）被访问，当这个A被访问且左子树被修改为其前向结点时(也即是说A的左子树本来为NULL，然后被修改，假设其前向指针为O，就会被修改为O)，按照先序遍历的逻辑是接下来会访问根节点A的左子树，访问时就会发现其左子树是当前节点的前向结点O（本来是NULL然后被修改了），程序会跳转到O，然后O访问完又跳转到A出现死循环问题，俗称“爱的魔力转圈圈”问题。解决的办法就是看标志位ltag

void ThreadVisit(ThreadNode *q){
    printf("%c ",q->data);
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
// 先序线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        ThreadVisit(T);
        if(T->ltag==0)
            PreThread(T->lchild);
        PreThread(T->rchild);
    }
}
void CreatePreThread(ThreadTree T){
    pre=NULL;
    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

中序线索二叉树的实现

#include "threadtree.h"
ThreadNode *pre=NULL;//全局变量指向当前访问的结点的前驱

void createThreadTree(ThreadTree *T){
    DataType ch;
    scanf("%c",&ch);
    // while(getchar()!='\n');//当获取一个有效字符时结束循环
    if(ch=='#'){
        *T=NULL;
        return;
    }
    else{
        *T=(ThreadNode *)malloc(sizeof(ThreadNode));
        (*T)->data=ch;
        createThreadTree(&((*T)->lchild));
        createThreadTree(&((*T)->rchild));
    }
}
// 中序线索化-是建立在已经建立了一棵二叉树的前提下实现的
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);
        ThreadVisit(T);
        InThread(T->rchild);
    }
}
void ThreadVisit(ThreadNode *q){
    printf("%c ",q->data);
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
void CreateInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if(pre->rchild==NULL)
            pre->rtag=1;//处理遍历后的最后一个结点
    }
}
void test3(){
    ThreadTree T;
    printf("please imput a string without blank and line feed...\n");
    createThreadTree(&T);
    printf("create successfully\n");
    CreateInThread(T);
    printf("\nsuccessful!");
}
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

后序线索二叉树的实现

void ThreadVisit(ThreadNode *q){
    printf("%c ",q->data);
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
// 后序线索化
void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);
        PostThread(T->rchild);
        ThreadVisit(T);
    }
}
void CreatePostThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        PostThread(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

---

线索二叉树的遍历

中序线索二叉树可以找前驱后继，先序线索二叉树不能找前驱只能找后继，后序线索二叉树不能找后继只能找前驱。

这里说的不能，是说不重新按照遍历顺序遍历，不使用三叉链表的前提下

用例：ABD##E##CF##G##

中序

• 后继结点遍历：正向的中序遍历

思路：找到遍历的第一个结点作为当前结点，然后不断寻找当前结点的后继结点直到没有后继结点（这不比递归来的香）

// 中序线索二叉树的遍历：找到第一个结点，然后不断寻找后继结点的过程,空间复杂度为O(1)
// 找到以p为根节点的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(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;//tag=1的时候rchild就是直接后继
}
void InOrder3(ThreadTree T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        printf("%c ",p->data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 中序前向结点的遍历：实现二叉树的中序遍历的倒置

// 前向遍历
ThreadNode *Lastnode(ThreadNode* p){
    while(p->rtag==0)
        p=p->rchild;
    return p;
}
// 寻找其前向结点
ThreadNode *Prenode(ThreadNode *p){
    if(p->ltag==0)
        return Lastnode(p->lchild);
    else
        return p->lchild;
}
void RevInOrder3(ThreadTree T){
    for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))
        printf("%c ",p->data);
    printf("\n");
}
void test3(){
    ThreadTree T;
    printf("please imput a string without blank and line feed...\n");
    createThreadTree(&T);
    printf("create successfully\n");
    CreateInThread(T);
    printf("\nsuccessful!\n");
    InOrder3(T);
    RevInOrder3(T);
}
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

先序

// 前序二叉树寻找后继结点
ThreadNode *Nextnode_pre(ThreadNode *p){
    if(p->rtag==1)
        return p->rchild;
    else{
        if(p->lchild!=NULL)
            return p->lchild;
        else
            return p->rchild;
    }
}
void PreOrder3(ThreadTree T){
    for(ThreadNode *p=T;p!=NULL;p=Nextnode_pre(p))
        printf("%c ",p->data);
    printf("\n");
}
// 前序二叉线索数寻找前向结点需要假设能找到结点的父节点(三叉链表)
// 如果p是左孩子，能找到父节点，则父节点为其前驱
// 如果p是右孩子，能找到父节点，父节点左孩子为空，则父节点为其前驱
// 如果p是右孩子，能找到父节点，且父节点的左孩子非空，则p的前驱为左孩子树中最后一个被先序遍历的节点，也就是左孩子树中最后一个右子树.因为数据结构定义问题这个先不实现了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

后序

// 后序线索二叉树
// 寻找后序前驱
ThreadNode *Prenode_post(ThreadNode *p){
    if(p->ltag==1)
        return p->lchild;
    else{
        if(p->rtag==0)//说明p有右子树
            return p->rchild;
        else
            return p->lchild;
    }
}
void RevPostOrder3(ThreadTree T){
    // 寻找后序遍历的最后一个被遍历到的节点，一定就是根节点
    for(ThreadNode *p=T;p!=NULL;p=Prenode_post(p))
        printf("%c ",p->data);
    printf("\n");
}

// 寻找后续后继——基于父节点来实现
// 如果p是右孩子，其后继便是父节点
// 如果p是左孩子且没有兄弟节点，则其后继为父节点
// 如果p是左孩子且右孩子非空，其后继为右兄弟中第一个被后序遍历的结点
// 如果p是跟结点，则p是没有后序后继的，且父节点的左孩子非空，则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

后序

// 后序线索二叉树
// 寻找后序前驱
ThreadNode *Prenode_post(ThreadNode *p){
    if(p->ltag==1)
        return p->lchild;
    else{
        if(p->rtag==0)//说明p有右子树
            return p->rchild;
        else
            return p->lchild;
    }
}
void RevPostOrder3(ThreadTree T){
    // 寻找后序遍历的最后一个被遍历到的节点，一定就是根节点
    for(ThreadNode *p=T;p!=NULL;p=Prenode_post(p))
        printf("%c ",p->data);
    printf("\n");
}

// 寻找后续后继——基于父节点来实现
// 如果p是右孩子，其后继便是父节点
// 如果p是左孩子且没有兄弟节点，则其后继为父节点
// 如果p是左孩子且右孩子非空，其后继为右兄弟中第一个被后序遍历的结点
// 如果p是跟结点，则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

---

树的存储结构

#ifndef TREEPLUS_H
#define TREEPLUS_H

// 双亲表示法
#define MAX_TREE_SIZE 100
typedef char ElemType;
typedef struct{
    ElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int len;//表示结点的数量
}PTree;


// 孩子表示法
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;//结点的数量和根的位置
}CTree;//一整个数组

// 孩子兄弟表示法（链式存储）——树和二叉树相互转化的问题
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;
#endif
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

树的遍历

• 树的先根遍历

因为涉及到具体要使用的存储结构，所以这里给的是伪代码。

对数的先根遍历和这棵树对应的二叉树的先序序列相同

void PreOrder4(TreeNode *R){
    if(R!=NULL){
        visit(R);//访问根结点
        while(R还有下一个子树T){
            PreOrder4(T);//先根遍历下一棵子树
        }
    }
}
1
2
3
4
5
6
7
8

• 后根遍历

如果树非空，先依次对每棵子树进行后根遍历，最后再访问根节点

对树的后跟遍历和这棵树对应的二叉树的中序序列相同

void PostOrder4(TreeNode *R){
    if(R!=NULL){
        while(R还有下一棵子树T)
            PostOrder4(T);
        visit(R);//访问根结点
    }
}
1
2
3
4
5
6
7

先根遍历和后跟遍历并称为深度优先遍历

• 树的层次优先遍历——也叫广度优先遍历

和二叉树一样，也是使用队列来辅助进行遍历的，思路是：
首先根节点入队列
根节点出队列，如果出队的结点有孩子结点，就把孩子结点入队列
重复以上操作直到队列为空
1
2
3
4

森林的遍历

• 森林的先序遍历——两层的递归遍历

森林是由n棵互不相交的树的集合，没棵树去掉根节点后，其余各个子树又组成了森林。因此森林是用树来递归定义的，基于这个想法，森林的先序遍历如下

如果森林非空，则
    访问森林中第一棵树的根节点
    先序遍历第一棵树中根节点的子树森林
    先序遍历除第一棵树之后剩余的树构成的森林
1
2
3
4

森林的先序遍历和其对应的每一棵树的分别的先序遍历得到的结果是相同的

也可以先把森林转换为对应的二叉树，对二叉树进行先序遍历，得到的结果相同

简单来讲，先序遍历没有什么特别的，就代码特别难写

• 森林的中序遍历——两层的递归遍历

如果森林非空
    中序遍历森林中的第一棵树的根节点的子树森林
    访问第一棵树的根节点
    中序遍历除第一棵树之后剩余的树构成的森林
1
2
3
4

森林的中序遍历相当于对森林的每一棵树的后序遍历得到的结果

也可以先转化为对应的二叉树，对二叉树进行中序遍历，得到的结果也相同

哈夫曼树

• 带权路径长度

结点的权：有某种现实含义的数值

结点的带权路径长度：从树的根节点到该结点的路劲长度（经过的边数）与该结点上权值的乘积

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

• 哈夫曼树

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

• 构造哈夫曼树

每次选择结点权重最小的两个数作为兄弟节点，把他们权重的和作为他们的根结点。再把这个根结点和其他没有被选择的最小权值的结点构造一棵树，一次类推直到全部的结点都被选择。

构造出的哈夫曼树是不唯一的，其编码也是不唯一的

• 哈夫曼编码——前缀编码，无歧义

哈夫曼树可以用来进行数据的压缩

并查集——双亲表示法

将各个元素划分为互不相交的子集

用代码来表示同一个集合的元素：同一个集合的元素构成一棵树，这些树构成一个森林

查询操作：从指定元素出发，找到根节点，时间复杂度为O(n)，查询的时间复杂度与树的高度有关，所以优化的思路是，当合并的时候，小树合并成大树

#define SIZE 13
int UFSets[SIZE];//集合元素数组

//初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++)
        S[i]=-1;
}

//find操作
int Find(int S[],int x){
    while(S[x]>=0)
        x=S[x];
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并结合：其中一棵树称为另一棵树的子树就可以了——时间复杂度为O(1)

void Union(int S[],int Root1,int Root2){
    if(Root1==Root2)
        return;
    S[Root2]=Root1;
}
1
2
3
4
5

并查集的优化

• 优化union操作，优化的思路是小树合并成大树

优化后的合并操作——我们使得根节点对应的数组值变成其对应集合数量的相反数，比如一棵树的数量为10，那么其根节点对应的数组值为-10。

void Union2(int S[],int Root1,int Root2){
    if(Root1==Root2)
        return;
    if(S[Root1]>S[Root2]){
        S[Root1]+=S[Root2];
        S[Root2]=Root1;
    }else{
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}
1
2
3
4
5
6
7
8
9
10
11

用数学归纳法知，优化后的树的高度不会超过(log2)n+1

• 优化find操作

优化的结果是压缩路径，思路是先找到根节点，再将查找路径上的所有结点都挂接到根结点下面，优化后的代码如下

int find(int S[],int x){
    int root=x;
    while(S[root]>=0)
        root=s[root];
    while(x!=root){
        int t=S[x];//t指向x的父节点
        S[x]=root;//x直接挂接到根节点下面
        x=t;
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11

每次find操作后，再找根，再压缩路径，使得树的高度不超过O(α(n))，α(n)是一个增长很缓慢的树函数，对于常见的n的值，通常α(n)≤4，因此优化后的并查集的find和union操作时间开销都很低