树的基本结构

树的定义

树与线性表不同的地方是：线性表有唯一 的直接前趋，和唯一的直接后继，但是树有唯一的直接前趋，不唯一的直接后继

树是n（n≥0）个结点的有限集。

若n == 0, 称为**空树**

若 n > 0，则它满足以下两个条件：
  1. 有且仅有一个特定的称为根的节点
  2. 其余节点可分为m（m≥0）个互不相交的有限集T1， T2, T3·····其中每一个集合本身有是一颗树，并成为根的子树

树的基本术语

  1. 根节点：非空树中无前趋结点的结点

  2. 节点的度：结点拥有的子树数

  3. 树的度：树内各节点的度的最大值

  4. 当度=0时的结点：终端节点

  5. 当度≠0时的结点：称为分支结点，非终端结点，根节点以外的分支结点称为内部结点

  6. 结点的子树的跟称为该节点的孩子，该节点称为孩子的双亲

  7. 拥有同一个双亲的一类结点，称为兄弟结点

  8. 双亲在同一层的结点，称为堂兄弟结点

  9. 结点的祖先：从根节点到该节点所经分支上的所有结点

  10. 树的深度：树中结点的最大层次

  11. 有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）

  12. 无序树：树中结点的各子树无次序。

  13. 森林：是m(m≥0)颗互不相交的树的集合

    		把根节点删除树，就变成了森林。

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

		给森林中各子树加上一个双亲结点，森林就变成了树

    树结构和线性结构的比较

线性结构 树结构
第一个元素 无前趋 根节点（只有一个） 无双亲
最后一个元素 无后继 叶子节点 无孩子
其他元素 一个前趋一个后继 其他结点-----中间节点 一个双亲多个孩子
一对一 一对多

二叉树的定义

最多只有两个叉的树

在计算的 时候普通树（多叉树）若不转换为二叉树，则运算很难实现

二叉树的优点：

  1. 二叉树的结构最简单，规律性最强
  2. 可以证明，所有树都能转为唯一对应的二叉树，不失一般性

二叉树是n（n≥0）个结点的有限集，他或者是空集（n=0），或者由一个根节点及两颗互不相交的分别称作这个跟的左子树和右子树的二叉树组成

特点：
  1. 每个结点最多有俩孩子（二叉树中不存在度大于2的结点）
  2. 子树有左右之分，其次序不能颠倒
  3. 二叉树可以是空集合，跟可以有空的左子树或空的右子树

注：二叉树不是树的特殊情况，他们是两个概念

		二叉树的子树，要区分左子树和右子树，即使只有一颗子树也要区分，说明他是左子树还是右子树

		当树结点只有一个孩子时，就**无序区分**它是左还是右的次序，因此二者是不同的

		（也就是说二叉树每个结点的位置或者说次序都是固定的，可以是空，但是不能说他没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，他就无所谓左右了）

案例引入

  1. 数据压缩问题

    将数据文件转换成由0，1组成的二进制码，称之为编码

  2. 利用二叉树求解表达式的值

二叉树的抽象数据类型定义

ADT BinaryTree

{

	数据对象D：D是具有相同特侦的数据元素的集合。

	数据关系：若D是空集，则R是空集

						若D不是空集，则R={H}; H,是如下二元关系：

							1 root唯一       // 关于跟的说明

							2 子树不相交

							3 关于数据元素的说明

							4 关于左子树和右子树的说明

	基本操作：// 至少有20个

	CreateBiTree（&T, definition）

			初始条件：definition给出二叉树T的定义

			操作结果：按definition构造二叉树T

	PreOrderTraverse（T）：

		初始条件：二叉树T存在

		操作结果：先遍历T，对每一个结点访问一次

	InOrderTraverse（T）

		初始条件：二叉树存在

		操作结果：中序遍历T，对每一个节点访问一次

	PostOrderTraverse（T）

		初始条件：二叉树T存在

		操作结果：后序遍历T，对每一个结点访问一次

}ADT BinaryTree

二叉树的性质和存储结构

性质

  1. 性质一：

    在二叉树的第i层上至多由 2^(i-1)次方 个结点

     第一层	2^0 = 1

 第二层	2^1 = 2

 第三层    2^2 = 4

 第四层    2^3 = 8

    第i层上至少有1个结点

  2. 性质二：

    深度为k的二叉树总共至多有2^k - 1个节点

    证明：使用性质一，可得到每一层之间的数量是等比数列

     深度为k的二叉树的最大节点数为等比数列的前n项和

 深度为k的二叉树总共至少有k个结点

  3. 性质三：

    对任何一颗二叉树T，如果其叶子树为n0，度为2的节点数为n2，则n0 = n2 + 1

    总边数 B = n - 1 (n 是总结点数) B = n2 * 2 + n1 * 1;(n2 是度为二的节点数， n1是度为一的节点数)

    由上可得 n = n2 * 2 + n1 * 1 + 1;

    又因为 n = n2 + n1 + n0(n0 是叶子结点)

    所以 n2 + n1 + n0 = n2 * 2 + n1 * 1 + 1 ======> n0 = n2 + 1

  4. 满二叉树：

    一颗深度为k且有2^k - 1个结点的二叉树称为满二叉树

    特点：

    1. 每层上的结点数都是最大结点数（即每层都满）
    2. 叶子节点全部在最底层

    对满二叉树节点位置进行编号：

    编号规则：从根节点位置进行编号，自上而下，自左而右

    每一个节点位置都有元素

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

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

  5. 完全二叉树

    深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1 ~ n的结点一一对应时，称之为完全二叉树

    可以不满，但是存在的位置的结点排序后，必须与满二叉树对应的结点顺序一一对应

    特点：1.叶子只能分布在层次最大的两层上

     	2. 对于任意一个，如果其中右子树的最大层次为i 则其左子树最大层次必是i或i+1

  6. 性质4：具有n个结点的完全二叉树的深度为[log2^n] + 1

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

  7. 性质5：如果对一颗有n个结点的完全二叉树（深度为龙[㏒2^n] )的点按层编号（从第一层到【log2^n】+1 层，每层从左到右），则对任一结点i（1≤ i ≤ n ）有：

    如果 i == 1 则节点i 是二叉树的跟， 无双亲，如果i > 1,则其双亲是节点[ i / 2 ]

    如果2i > n则节点i为叶子结点， 无左孩子；否则，其左孩子的结点是2i

    如果2i+1>n ，则结点i无右孩子；否则，其右孩子的结点2i + 1

存储结构

二叉树的顺序存储：

image-20221105101911170

实现：按**满二叉树**的结点层次编号，依次存放二叉树中的数据元素

#define MAXSIZE 100

Typedef TElemType SqBiTree[MAXSIZE]

SqBiTree bt

当存储非完全二叉树，和满二叉树的时候，再遇见空元素的时候需要使用0来占位

特点：

结点关系，蕴含在其存储结构中，浪费空间，适于存放**满二叉树和完全二叉树**

二叉树的链式存储结构

image-20221105101833300

二叉树结点的特点， 一个双亲两个孩子

链式存储方式：

	一个结点中有三个元素， 数据， 左节点指针，右节点指针

**二叉链表**的存储结构：

typedef struct BiNode

{

TRlemType data;    //  数据元素

struct BiNode *lchild, *rchild;   //  左右孩子指针

}BiNode, *BiTree;

在n个结点的二叉链表中，右（n+1）个空指针域

	**注（自己理解）**：可以理解为原先全部都是空结点，现在每多加一个，就消耗一个空结点，多出两个空结点，所以每添加一个结点，就多出一个空结点

	**分析**：必有2n个链域，除根节点外，每个结点有且仅有一个双亲，所以，只有n-1个结点的链域，存放指针，指向非空子女结点。

		空指针数目 ===== 2n -(n-1) = n+1; 

**三叉链表**

相比于二叉链表多出一个**双亲指针**

二叉树的遍历

  • 遍历定义：顺着某一条搜索路经巡防二叉树中的结点，使得每一个结点均被访问一次，而且仅被访问一次（又称周游）
    • 访问的含义很广，可以是对节点做各种处理，如：输出节点的信息，修改节点的数据值等，但要求这种访问不破坏原来的数据结构
  • 遍历目的--------得到树中结点的一个线性排列
  • 遍历用途--------它是树结构插入，删除，修改，查找和排序运算的前提，是二叉树一切运算的基础和核心

遍历方法

假设L：遍历左子树， D：访问访问根节点 R: 遍历右子树

则遍历正二叉树方案共有：

DLR, LDR. LRD. DRL. RDL. RLD  六种
  • 若规定先左后右，则只有前三种情况
  • DLR---- 先（根）序遍历
  • LDR-----中（根）序遍历
  • LRD ---- 后（根）序遍历
  • 若二叉树为空，则空操作，否则
    • 先访问根节点
    • 先序遍历左子树
    • 先序遍历右子树

例题-------已知先序和中序序列求二叉树

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

先序：A B C D E F G H I J

中序：C D B F E A I H G J

先找根节点：

由先序可知A必是根节点， B必是左节点的根节点， G是右结点的根节点

由中序可知C D B F E是左节点， I H G J是右节点

		CD是B的左结点， EF是B的右节点， IH是G的左节点，J是H的右节点

由先序可知，C，E， H是根节点， 由中序可知D， F是右节点， I是左节点

遍历算法（递归型）：

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
62
63
64
65
// 以下是伪代码(先序遍历)
Status PreOrderTraverse(BiTree T)
{
    if(T == NULL)return OK;
    else
    {
        visit(T); // 访问根节点的一些方法 例如：printf("%d", T);
        PrrOrderTraverse(T->lchild); // 递归遍历左子树
        PreOrderTraverse(T->rchild);  //  递归遍历右子树
    }
}

// 以下是算法的真代码（先序遍历）
void Pre(BiTree *T)
{
    if(T != NULL)
    {
        printf("%d\t", T->data);
        Pre(T->lchild);
        Pre(T->rchild);
    }
}

//  一下是伪代码（中序遍历）
Status InOrderTraverse(BiTree T)
{
    if(T == NULL)return OK;
    else
    {
        InOrderTraverse(T->lchild); // 递归遍历左子树
        visit(T); // 访问根节点
        InOrderTraverse(T->rchild); // 递归遍历右子树
    }
}
// 以下是算法的真代码（中序遍历）
void In(BiTree *T)
{
    if(T != NULL)
    {
        Pre(T->lchild);
        printf("%d\t", T->data);
        Pre(T->rchild);
    }
}
//  一下是伪代码（后序遍历）
Status PostOrderTraverse(BiTree T)
{
    if(T == NULL)return OK;
    else
    {
        InOrderTraverse(T->lchild); // 递归遍历左子树
        InOrderTraverse(T->rchild); // 递归遍历右子树
        visit(T); // 访问根节点
    }
}
// 以下是算法的真代码（后序遍历）
void Post(BiTree *T)
{
    if(T != NULL)
    {
        Pre(T->lchild);
        Pre(T->rchild);
        printf("%d\t", T->data);
    }
}

看这三种算法：如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同

如下图所示：从虚线出发到终点的路径上，每个结点经过三次：

第一次经过时访问 = 先序遍历

第二次经过时访问 = 中序遍历

第三次经过时访问 = 后序遍历

遍历算法（非递归型）：

中序遍历非递归算法

二叉树**中序遍历的非递归算法的关键**：在中序遍历过某节点的整个左子树后，如何找到该节点的**根**及**右子树**

基本思想：

  • 建立一个栈
  • 根节点进栈，遍历左子树
  • 根节点出栈，输出根节点，遍历右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Status InOrderTraverse(BiTree T)
{
    BiTree p; 
    InitStack(S);
    p = T;
    while( p || !StackEmpty(S))
    {
        if(p) // 先判断是否为空
        {
            Push(S,p);  // 不为空，就压栈，再往下走
            p = p->lchild; 
        }
        else
        {
            Pop(S,q); // 空的话就把根节点出栈， 并指向右节点
            printf("%c",q->data);
            p = q->rchild;
        }
    }
}

二叉树的层次遍历

从根节点开始，按照从上到下，从左到右的顺序访问每一个结点，每一个结点仅仅访问一次

算法设计思路：使用一个队列

  1. 将根节点入队
  2. 对不空时循环：从队列中出列一个结点*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
// 队列类型定义
typedef struct
{
    BTNode data[MaxSize]; // 存放在队中元素
    int front, rear; // 队头和队尾指针
}SqQueue;

void LevelOrder(BTNode *b)
{
    BTNode *p;
    SqQueue *qu;
    InitQueue(qu);   //  初始化队列
    enQueue(qu, b);  // 根节点指针进入队列
    while(!QueueEmpty(qu))
    {
        deQueue(qu,p); // 出队根节点
        printf("%c", p->data);
        if(p->lchild != NULL) // 如果根节点有左孩子。则将其入队
        {
            enQueue(qu, p->lchild);
        }
        if(p->rchild != NULL) // 如果根节点有右孩子，则将其入队
        {
            enQueue(qu, p->rchild);
        }
    }
}

二叉树的建立

按先序遍历序列建立二叉树的二叉链表

  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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTree
{
	char data;
	struct BiTree *lchild;
	struct BiTree *rchild;
}BiTree, *BiNode;

BiNode CreatBiTree(BiNode T) // 这里的返回值时BiNode类型的，而且必须是这个类型的，因为在这里面还有动态申请空间的条件，所以需要使用返回值来带回申请空间的地址
{
	char ch;
	scanf("%c", &ch);
	if(ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = (BiNode)malloc(sizeof(BiTree));
		T->data = ch;
		T->lchild = CreatBiTree(T->lchild);
		T->rchild = CreatBiTree(T->rchild);
	}
	return T;
}


void PreBiTree(BiNode T)
{
	if(T)
	{
		printf("%c", T->data);
		PreBiTree(T->lchild);
		PreBiTree(T->rchild);
	}
}


int main()
{
	BiNode T;
	T = CreatBiTree(T);
	PreBiTree(T);

}

二叉树遍历算法的应用—复制二叉树、

如果是空树，递归结束

否则，申请新节点空间，复制根节点

递归复制左子树

递归复制右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BiTree * Copy(BiTree T, BiTree *NewT)
{
    if(T==NULL)// 如果是空树则返回空
    {
        return NULL;
    }
    else
    {
        NewT = (BiTree)malloc(sizeof(BiTree));
        NewT->data = T->data;
        Newt->lchild = Copy(T->lchild, NewT->lchild);
        NewT->rchild = Copy(T->rchild, NewT->rchild);
    }
    return NewT;
}

二叉树遍历算法的应用—计算二叉树深度

如果是空树，则深度为零

否则，递归计算左子树的深度记为m，递归计算右子树的深度为n，二叉树的深度则为m与n的较大者加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Depth(BiTree *T)
{
	int m, n;
	m = n = 0;
	if(T == NULL)
	{
		return 0;
	}
	else
	{
		m = Depth(T->lchild);
		n = Depth(T->rchild);
		if( m > n)
		{
			return (m+1);
		}
		else
		{
			return (n+1);
		}
	}
}

计算二叉树结点总数

如果是空树，则结点个数为0；

否则，结点个数的为左子树的结点个数+右子树的结点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BNumber(BiNode T)
{
	int m, n;
	if(T==NULL)
	{
		return 0;
	}
	else
	{
		m = BNumber(T->lchild);
		n = BNumber(T->rchild);
		return m+n + 1;
	}
}

计算二叉树叶子节点数

如果是空树，则叶子节点个数为零

否则，为左子树的叶子节点个数+右子树叶子节点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LeafCount(BiNode T)
{
	if(T == NULL)
	{
		return 0;
	}
	if( T->lchild == NULL && T->rchild == NULL)
	{
		return 1;
	}
	else
	{
		return LeafCount(T->lchild) + LeafCount(T->rchild);
	}
}

线索二叉树

在二叉树中寻找前趋和后继的方法：

  1. 通过将二叉树遍历寻找---------费时间
  2. 再增设前趋，后继指针域-----------增加了存储负担
  3. 利用二叉链表中空指针域

二叉树中空指针域的数量：

  • 具有n个结点的二叉链表中，一共有2n个指针域，因为n个结点中有 n-1个孩子，即2n个指针域中，有n-1个用来指示节点的左右孩子，其余n+1个指针域为空

利用二叉链表中的空指针域：

如果某个节点中的左孩子为空，则将空的左孩子指针域改为**指向其前趋**，如果某个节点的右孩子为空，则将空的右孩子指针域改位**指向其后继**

-----这种**改变指向的指针**称为“**线索**”

加上了线索的二叉树称为**线索二叉树**

为了区分lchild和rchild指针到底是指向孩子的指针还是指向前趋或者后继的指针，对二叉链表中的**每一个结点增设两个标致域 ltag和rtag**，并约定

ltag = 0	lchild指向该节点的**左孩子**

ltag = 1	lchild指向该节点的**前趋**

rtag = 0	rchild指向该节点的**右孩子**

rtag = 1	rchild指向该节点的**后继**

当我们遇到二叉树的第一个元素和最后一个元素的时候，会有两个空的指针，我们可以增设一个头结点

ltag = 0，lchild指向根节点	

rtag = 1， rchild指向遍历序列中最后一个结点

遍历序列中的第一个结点的lc域和最后一个结点的rc域都指向头结点

树和森林

树：是n（n≥0）个结点的有限集。若n = 0，称为空树；

若n > 0

1. **有且仅有一个**特定的称为**根**的结点
2. **其余结点**可分为m（m≥0）个互不相交的有限集T1，T2，T3，·····，Tn

森林：是m（m大于等于0）棵互不相交的树的集合

树的存储结构

  1. 双亲表示法

    实现：定义结构数组

     	存放树的结点；

 	每个结点含两个域
    • 数据域：存放结点本身信息
    • 双亲域：指示本节点的双亲结点在数组中的位置
    • 特点：找双亲容易，找孩子难
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef struct PTNode
    {
        TElemType data;
        int parent; // 双亲位置
    }PTNode;
    // 树结构
    #define MAX_TREE_SIZE 100
    typedef strcut
    {
        PTNode nodes[MAX_TREE_SIZE];
        int r, n; // 根节点的位置和结点个数
    }PTree；

  2. 孩子表示法

	把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，把n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针由组成一个线性表，用顺序表（含n个元素的结构数组）存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 孩子结点结构：
typedef struct CTNode
{
    int child;
    strcut CTNode *next;
}*ChildPtr;
// 双亲结点结构
typedef struct
{
    TElemType data;
    Child firstchild;// 孩子链表头指针
}CTBox;
// 树结构
typedef struct
{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;// 结点数和根节点的位置
}

特点：找孩子容易，找双亲难

为了解决找双亲难的问题，可以在双亲结点中再加一项，双亲的下标，这种存储结构我们称作带双亲的孩子链表

  1. 孩子兄弟表示法（二叉树表示法，二叉链表表示法）

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

    typedef strcut CSNode

    {

    ElemType data；

    strcut CSNode *firstchild， *nextsibling；

    }CSNode， *CSTree；

树与二叉树的转换

  • 将树转换成二叉树进行处理，利用二叉树的算法来实现对数的操作
  • 由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表做媒介可以导出树与二叉树之间的一个对应关系

  1. 将树转换成二叉树

    • 加线:在兄弟之间加一连线
    • 抹线：对每个结点，除了其左孩子外，去除其与其他孩子之间的联系
    • 旋转：以树的根节点为轴心，将整数顺时针旋转45°
    • 树变二叉树：兄弟相连留长子

  2. 二叉树转换成树

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

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

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

      二叉树变树：

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

  3. 森林转换成二叉树（二叉树与多棵树之间的关系）

    • 将各棵树分别转换成二叉树
    • 将每棵树的结点用线相连
    • 已第一颗树根结点为二叉树的根，再以根节点为轴心，顺时针旋转构成二叉树型结构
    • 森林变二叉树；树变二叉根相连

  4. 二叉树转换成森林

    将森林转换成二叉树的方法倒过来即可

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

    2. 还原，将孤立的二叉树还原成树

      二叉树变森林：

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

树的遍历

  • 先根（次序）遍历：
    • 若树不空，则先访问根节点，然后依次先根遍历各个子树
  • 后跟（次序）遍历：
    • 若树不空，则先依次后跟遍历各棵子树，然后访问根节点
  • 按层次遍历
    • 若树不空，则自上而下自左而右访问每个结点

森林的遍历

将森林看作由三部分组成

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

先序遍历

若森林不空，则

1. 访问森林中第一颗树的根节点
2. 先序遍历森林中第一颗树的子树森林
3. 先序遍历森林中（除第一颗树之外）其余树构成的森林

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

哈夫曼树

基本概念

在进行百分制转换成五分制的时候，我们需要依次比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if(score < 60)
{
    grade = 'E';
}
else if( score < 70)
{
    grade = 'D'
}
else if( score < 80)
{
    grade = 'C'
}
else if( score < 90)
{
    grade = 'B'
}
else
{
    grade = 'A'
}

在这种情况下，假如数据查找量很多，而且成绩集中分布在CB这里，那么在使用这种方法那就比较不明智，我们可是用树来分割这些比较的先后，可以先比较中间的

哈夫曼树（最优二叉树）

哈夫曼树的基本概念

  1. 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

  2. 结点的路径长度：两节点间路径上的分支数

  3. 树的路径长度：从树根到每一个结点的路径长度之和，记作TL

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

  4. 权：将树中结点赋给一个有着某种含义的数值，则称这个数值为该点的权

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

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

    相同权值，相同数目的叶子结点，不同的二叉树，树的带权路径长度是不同的

哈夫曼树：最优树（带权路径长度最短的树）

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

哈夫曼树：最优二叉树（带权路径长度最短的二叉树）

	满二叉树不一定是哈夫曼树， 在哈夫曼树中权值较大的离根节点比较近，权值较小的里根节点比较远

	具有相同带权结点的哈夫曼树不唯一

哈夫曼树及其应用

哈夫曼树构造算法1：

哈夫曼算法（构造哈夫曼树的方法）

贪心算法：构造哈夫曼树时首先先责权值小的叶子结点
  1. 根据n个给定的权值{W1，W2，W3，······，Wn}构成n棵二叉树森林F = {T1,T2,·····，T3}；其中Ti只有一个带权为Wi的根节点
    • 构造森林全是根
  2. 在F中选择两颗根节点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左右子树上根节点的权值之和
    • 选用两小造新树
  3. 在F中删除这两颗树，同时将新的到的二叉树加入到森林中
    • 删除两小添新人
  4. 重复2和3，直到森林中只有一颗树为止，这棵树极为哈夫曼树
    • 重复2 3 得单根；
  5. 哈夫曼树中的结点度为零，和度为二，没有度为一的结点
  6. 总结：
    1. 在哈夫曼算法中，初始时有n棵二叉树，需要经过n-1次合并最终形成哈夫曼树
    2. 经过n-1次合并产生n-1个新节点，这n-1个新节点都是具有两个孩子的分支结点
    3. 可见哈夫曼树中共有n+n-1 = 2n-1个结点，且具有分支节点的度均不为1

哈夫曼树构造算法的实现

采用顺序存储结构------一维数组

结点类型定义

1
2
3
4
5
typedef struct
{
    int weight; // 这个点的权重
    int parent, lch, rch;  // 父母和左右孩子的位置
}HTNode, *HuffmanTree;

哈夫曼树中共有2n-1个结点不使用0下标，数组大小为2n

  1. 初始化HT[1……2n-1]:lch = rch = parent = 0;
  2. 输入初始n个叶子节点：置HT[1……n]的weight值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void CreatHuffmanTree(HuffmanTree HT, int n)
{
    int i, m, k;
    if( n <= 1)
    {
        return 0;
    }
    m = 2*n - 1;
    HT = (HuffmanTree)malloc(sizeof(HTNode)*(m+1));
    for(i = 1; i <= m; i++)
    {
        HT[i].parent = 0;
        HT[i].rch = 0;
        HT[i].lch = 0;
    }
    for( i = 1; i <= n; i++)
    {
        scanf("%d", &HT[i].weight);
    }
}
  1. 进行一下n-1次合并，依次产生n-1个结点，HT[i] i = n+1 …… 2n-1；
    • 在HT[1…i-1]中选两个未被选过的（从parent == 0）中选择weight值最小的两个结点HT[s1]和HT[s2], s1, s2为两个最小结点下标
    • 修改HT[s1]和HT[s2]的parent值，HT[s1].parent = i, 和HT[s2].parent = i;
    • 修改产生的HT[i]:
      • HT[i].weight = HT[s1].weight + HT[s2].weight;
      • HT[i].lch = s1; HT[i].rch = s2;
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
for(i = n+1; i <= m; i++)
{
    int min1, min2,temp;
    min1 = 1;
    min2 = 2;
    temp;
    for(k = 1; k < i; k++)
    {
        if(HT[k].parent != 0)
        {
            if(HT[min1].weight > HT[min2].weight)
            {
                temp = min1;
                min1 = min2;
                min2 = temp;
            }
            if(HT[min1].weight > HT[k].weight)
            {
                min1 = k;
            }
            else if( HT[min2].weight > HT[k].weight )
            {
                min2 = k;
            }
        }
    }
}

哈夫曼编码1—哈夫曼编码思想

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

若A-- 00， B— 01，C–10， D–11

则ABACCDA 转换成二进制的话就是 00010010101100

若将编码设计为长度不等 二进制编码，即让待转字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串变可能减少

A–0，B–00，C—1，D—01；那么ABACCDA就能转换为 000011010这个二进制编码

但是前面的0000这个会有三种不同的情况 可能是AAAA， ABA， BB这三种情况

所以为了不出现这种情况：

关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符编码的前缀----->前缀码

解决方法：–哈夫曼编码

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

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

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

    把结点的左分支标0， 右分支标1

    把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码

    两个问题

    1. 为什么哈夫曼编码能够保证是前缀编码？

      • 因为没有一片树叶是另一片树叶的祖先，所以每个叶节点的编码就不可能是其他叶结点的编码的前缀

    2. 为什么哈夫曼编码能过保证字符编码总长度最短？

      • 因为哈夫曼树带权路径长度最短，故字符编码的总长最短

      性质一：哈夫曼编码是前缀码

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