数据结构-树和二叉树（上）_树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。对于每一个结点

---

---

树和二叉树

树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
树是以分支关系定义的层次结构。

---

一、树的定义与基本术语

简单粗暴的定义就是有且仅有一个根节点、无环。

1. 结点
2. 根节点
3. 结点的度：结点拥有的子树数量；
   如A的度是3，B的度是2，K的度是0。
4. 叶子结点或终端结点：度为0的结点；
5. 层次/深度；

二、二叉树

要求严格一点
特点：
1.每个结点至多只有两棵子树，即二叉树中的结点度都不大于2；
2.二叉树的子树有左右之分，次序不能任意颠倒；

二叉树的5种基本形态

二叉树的性质

1. 第i层最多有$2^{i-1}$个结点；
2. 深度为k的二叉树最大结点数为$2^k-1$；
3. 任一棵二叉树，若其终端结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$；

满二叉树与完全二叉树

满二叉树：每一层上的结点数都是最大结点数
完全二叉树：
深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。
*特点：*叶子结点只在最深的两层出现；
对任一结点若其右分支的最大深度为$l$，则左分支的最大深度必为$l$或$l+1$（可以理解为左子树要全满）;
完全二叉树的两个重要特性:

1. $n$个结点完全二叉树深度为$\lfloor {\log }_{2}n\rfloor +1$
2. $n$个结点完全二叉树从上至下从左至右编号，对结点$i$:
   - $i=1$，$i$即为根，无双亲；$i>1$，双亲结点为$\lfloor i/2\rfloor$
   - $2i>n$，则$i$为叶子结点（$i$无左孩子）；否则$i$的左孩子结点为$2i$；
   - $2i+1>n$，则$i$无右孩子；否则$i$的右孩子结点为$2i+1$；

二叉树的顺序存储和链式存储

二叉树的二叉链表存储表示

typedef struct BitNode{
	int data;//int 可换成其他数据类型
	struct BitNode *lchild,*rchild;
}BitNode,*BiTree;



//创建二叉树
void Create(BiTree *T)//二级指针 指向BiTree的指针 
{
	char ch;
	scanf("%c",&ch);
	if(ch=='#')//#代表结点为空
	{
		*T=NULL;
		return;
	}
	(*T)=(BiTree)malloc(sizeof(BitNode));
	(*T)->data=ch;
	Create(&((*T)->lchild));//传递*T的左孩子的地址 
	Create(&((*T)->rchild));//传递*T的右孩子的地址 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、二叉树的遍历

递归算法定义：

先序遍历

若二叉树为空.则空操作;否则
(1）访问根结点；
(2）先序遍历左子树；
(3）先序遍历右子树。

//先序遍历 
void Pre_Traversal(BiTree T)
{
	if(T==NULL)return;
	printf("%c ",T->data);
	Pre_Traversal(T->lchild);
	Pre_Traversal(T->rchild);
}
1
2
3
4
5
6
7
8

中序遍历

若二叉树为空,则空操作;否则
(1）中序遍历左子树；
(2）访问根结点；
(3）中序遍历右子树。

//中序遍历 
void Mid_Traversal(BiTree T)
{
	if(T==NULL)return;
	Mid_Traversal(T->lchild);
	printf("%c ",T->data);
	Mid_Traversal(T->rchild);
}
1
2
3
4
5
6
7
8

后序遍历

若二叉树为空,则空操作；否则：
(1）后序遍历左子树;
(2）后序遍历右子树;
(3）访问根结点。

//后序遍历 
void Post_Traversal(BiTree T)
{
	if(T==NULL)return;
	Post_Traversal(T->lchild);
	Post_Traversal(T->rchild);
	printf("%c ",T->data);
}


1
2
3
4
5
6
7
8
9
10

四、哈夫曼树

又称最优树，是一类带权路径最短的树。

相关概念

树的路径长度是从树根到每一结点的路径长度之和。
结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度之和为树中所有叶子节点的带权路径长度之和，记作$WPL={\sum }_{k=1}^n{w}_k{l}_k$。

假设有$n$个权值 { w 1 , w 2 , . . . w n } \{w_1,w_2,...w_n\} {w1​,w2​,...wn​}，试构造一棵有$n$个叶子结点的二叉树，每个叶子节点带权为$w_i$，则其中$WPL$最小的二叉树称做最优二叉树或哈夫曼树。

构造哈夫曼树

哈夫曼算法

具体过程较为直观：

假设有 { a , b , c , d } \{a,b,c,d\} {a,b,c,d}四个结点，权值分别为 { 7 , 5 , 2 , 4 } \{7,5,2,4\} {7,5,2,4}，将四个结点都视为只有根结点的树。
1.找到权值最小的两个结点$c,d$，将之构造为一棵树并给根结点赋权值，权值为两结点之和，此时有 { 7 , 5 , 6 } \{7,5,6\} {7,5,6}；
2.继续寻找根结点权值最小的两棵树并将之合并，新树根结点权值为两树根结点之和;
3.重复以上过程直至最后只剩一棵树，该树即为哈夫曼树，树根结点权值即为$WPL$。

哈夫曼编码

前缀编码：编码长度可以不一，任一个字符的编码都不是另一个字符编码的前缀。

设计电文总长最短的二进制前缀编码，即以$n$种字符出现的频率作权设计一棵哈夫曼树的问题，得到的前缀编码称为哈夫曼编码。