数据结构详细笔记——树

---

树的定义和基本术语

树是n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1、有且仅有一个特定的称为根的结点
2、当n>1时，其余结点可分为m(m>0)个互不相交的有限集合，其中每一个集合本身又是一棵树，并且称为根结点的子树。

结点、树的属性描述

1、结点的层次（深度）————从上往下数
2、结点的高度————从下往上数
3、树的高度（深度）————总共多少层
4、结点的度————有几个孩子（分支）
5、树的度————各结点的度的最大值

有序树与无序树

有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
注意：具体看你的树存什么，是否需要用结点的左右位置反映某些逻辑关系

树与森林

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

树的常考性质

1、结点数 = 总度数 + 1

2、度为m的树、m叉树的区别

树的度————各结点的度的最大值
m叉树————每个结点最多只能有m个孩子的树

3、度为 m 的树第 i 层至多有 mⁱ⁻¹ 个结点（i >= 1）

4、高度为 n 的 m 叉树至多有 mⁿ - 1/m-1 个结点

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

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

树的存储结构

双亲表示法（顺序存储）

每一个结点中保存指向双亲的“指针”

#define MAX_REE_SIZE 100
typedef struct{       // 树结点定义 
	ElemType data;    // 数据元素
	int parent;       // 双亲位置域
} PTNode;
typedef struct{       // 树的类型定义
	PTNode nodes[MAX_REE_SIZE];  // 双亲表示 
	int n;            // 结点数
}PTree;
1
2
3
4
5
6
7
8
9

注意：根节点固定存储在0，-1 表示没有双亲

优点：查指定结点的双亲很方便
缺点：查指定结点的孩子只能从头遍历

孩子表示法（顺序+链式存储）

顺序存储各个结点，每个结点中保存孩子链表头指针

struct CTNode{
	int child;  // 孩子结点在数组中的位置
	struct CTNode *next;  // 下一个孩子
}
typedef struct{
	ElemType data;
	struct CTNode *firstChild; // 第一个孩子
}CTBox;
typedef struct{
	CTBox nodes[MAX_REE_SIZE];
	int n,r;   // 结点数和根的位置
}CTree;
1
2
3
4
5
6
7
8
9
10
11
12

孩子兄弟表示法（链式存储）

typedef struct CSNode{
	ElemType data;
	struct CSNode *firstChild,*nextsibling;  // 第一个孩子和右兄弟指针
}CSNode,*CSTree;
1
2
3
4

该方法相当于树和二叉树的转化（下一篇博客会讲到二叉树）

树和森林的遍历

树的遍历

1、先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历

如上图的树：
A	 B		  	 C	    D
A	(B	E	F)  (C G)  (D H I J)
A   (B (EK) F)  (C G)  (D H I J)

得先根遍历结果为 ABEKFCGDHIJ
1
2
3
4
5
6

2、后根遍历:若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点
3、层序遍历：用队列实现。①若树非空，则根结点入队。②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队。③重复②直到队列为空

树的后根遍历序列与这棵树相应二叉树的中序序列相同

森林的遍历

1、先根遍历：等同于依次对各个树进行先根遍历
2、中序遍历：等同于依次对各个树进行后根遍历，也等同于对对应的二叉树进行中序遍历

哈夫曼树

哈夫曼树的基础术语

结点的权：有某种现实含义的数值（如：表示结点的重要性等）
结点的带权路径长度：从树的根到该 结点的路径长度（经过的边数）与 该结点上的权值的 乘积
树的带权路径长度：树中所有 叶子结点的带权路径 长度之和（WPL）

哈夫曼树的定义

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

哈夫曼树的构造

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

特点：
①每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
②哈夫曼树的结点总数为2n-1
③哈夫曼树中不存在度为1的结点
④哈夫曼树并不唯一，但WPL必然相同且最优