文章目录
- (一) 树
- 1.树、森林的概念
- 森林
- 2.树的性质
- (1)结点数 = 1 + 度数
- (2)正则k叉树
- 3.树、森林的存储结构
- 1.双亲表示法 (顺序存储)
- 2.孩子表示法 (顺序+链式存储)
- 3.孩子兄弟表示法 (链式存储)
- (1)树、森林 与 二叉树的转换
- ①树、森林 → 二叉树
- ②二叉树→树、森林
- 4.树、森林的遍历
- 1.树的遍历
- 2.森林的遍历
- (二) 二叉树
- 1.二叉树结点的数据类型定义 (链式存储)
- 2.二叉树的性质
- 3.二叉树的存储结构
- (1)顺序存储（数组）
- (2)二叉树的链式存储（二叉链表）
- 4.几种特殊的二叉树
- 1. 满二叉树
- 2. 完全二叉树
- 完全二叉树结点的性质
- 3.二叉排序树(BST树)
- (1) BST的删除
- (2) BST的删除后再插入：删叶相同
- 4.平衡二叉树
- (1)AVL树的平衡调整
- ①AVL插入操作：4种插入调整
- ②AVL删除操作
- AVL的删除后再插入：无法确定
- (2)n个结点AVL最大深度/ 高度为h的AVL树总结点数最少是多少
- 5.线索二叉树（线索链表）：无子树则有线索。左线索指前驱，右线索指后继
- 6.哈夫曼树
- (1)带权路径长度
- (2)哈夫曼树（最小带权路径长度 WPL）
- (3)哈夫曼编码
- 7.并查集
- 5.二叉树的遍历
- 1. 前序遍历
- 2.中序遍历
- 3. 后序遍历
- (1)由遍历序列构造二叉树（三种遍历序列之间的关系）
- 4. 层序遍历
(一) 树
1.树、森林的概念
(一) 树
1.除根结点外，任何一个结点有且仅有一个前驱。
2.树是一种递归定义的数据结构，任何一棵树都可以看作是根结点和若干个互不相交的子树构成的。
3.树结点的路径是有向边，只能从上往下
4.结点的度：结点有几个孩子(分支)
树的度：树中各结点的度的最大值
森林
森林：m (m≥0) 棵互不相交的树的集合。
树和森林是相互递归定义的
