数据结构——树与二叉树

这一篇主要介绍了数据结构中树的知识点

---

			|- 二叉树-------|- 概念
			|				|- 操作：三种遍历（先序、中序、后序）；线索二叉树
			|				|- 应用：排序二叉树；平衡二叉树；哈夫曼树
树形结构-----|
			|				|- 概念		|- 与二叉树的转换
			|				|- 操作：---|- 树遍历（先根、后根）；森林遍历（先序、中序）
			|- 树和森林-----|- 应用：并查集

---

一、树的基本概念

1. 树的定义

是一种递归的数据结构
根节点没有前驱，其他节点只有一个前驱；所有节点有零个或多个后继。

2. 基本术语

节点的度：树中一个节点的子节点个数；
树的度：树中节点的最大度数；
节点的深度：从根节点自顶向下逐层累加；
节点的高度：从叶子节点自底向上逐层累加；

3. 树的性质

（1）树中节点数等于所有节点的度数加1；
（2）度为m的树第 i 层至多有 m^(i-1) 个节点；
（3）高度为h的m叉树 至多有 (m^h-1)/(m-1) 个节点；

二、二叉树的概念

1. 二叉树的定义及主要特性

二叉树是有序树，二叉树可以是空树

（1）满二叉树

（2）完全二叉树

特点如下：

• 叶子节点只可能在层次最大的两层，且最大层次的叶子节点都在左边。
• 如果有度为1的节点，只可能有一个，且该节点只有左孩子没有右孩子。
• 节点个数为n，若n为奇数，则每个分支节点都有左孩子和右孩子；若n为偶数，则编号最大的节点只有左孩子没有右孩子，其余节点左右孩子都有。

（3）二叉排序树

左子树上所有节点的关键字 < 根节点的关键字 < 右子树上所有节点的关键字

（4）平衡二叉树

任一节点的左右子树深度之差不超过1.

（5）二叉树的性质

• 非空二叉树叶子上节点数 N0 等于度为2的节点数 N1 加1，即 N0 = N1 +1；

2. 二叉树的存储结构

（1）顺序存储

• 用一组地址连续的存储单元依次自上而下、自左至右 存储完全二叉树的节点；
• 完全二叉树和满二叉树适合采用顺序存储，既能最大可能的节省存储空间，又可以利用数组元素的下标值确定节点在二叉树的位置，以及节点之间的位置关系；

（2）链式存储

• 由于顺序存储的空间利用率第，所以通常采用链式存储；
• 有 n 个节点的二叉链表中含有 n+1 个空链域；
  链式存储结构如下：

typedef struct BiTNode{
	ElemType data;		//数据域
	struct BiTNode *lchild, *rchild;	//左、右孩子域
} BiTNode, *BiTree;

三、 二叉树的遍历

1. 先序遍历

2. 中序遍历

3. 后序遍历

4. 递归和非递归的转换

5. 层次遍历

6. 由遍历构造二叉树

四、线索二叉树

1. 线索二叉树的基本概念

2. 线索二叉树的构造

3. 线索二叉树的遍历

五、树和森林

1. 树的存储结构

（1）双亲表示法

（2）孩子表示法

（3）孩子兄弟表示法

2. 树、森林、二叉树的转换

3. 树和森林的遍历

六、 树的应用——并查集

七、 二叉树的应用

1. 二叉排序树

（1）二叉排序树定义

（2）二叉排序树查找

（3）二叉排序树插入

（4）二叉排序树构造

（5）二叉排序树删除

2. 平衡二叉树

（1）平衡二叉树定义

（2）平衡二叉树插入

（3）平衡二叉树查找

3. 哈夫曼树

（1）哈夫曼树定义

（2）哈夫曼树构造

（3）哈夫曼编码