数据结构笔记 - 树
2019-08-22 本文已影响0人
MrOreo
🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲
背景
这篇文章主要记录🌲的相关知识。最近又重新读了一遍数据结构的课本及相关读物，因此想记录一些基本的知识点。
1. 树的表示法：
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
typedef int DataType;
typedef struct SNode
{
DataType data;
struct SNode *lchild, *rchild;
} SNode, * BiTree;
2. 二叉树的存储
- 二叉树的顺序存储适合于完全二叉树
- 普通情况适用于二叉链表存储
3. 二叉树的遍历
遍历：二叉树的遍历按照某个次序，对于每个结点进行访问，且只访问一次。
因此共有四种：
- 前序遍历
- 中序遍历
- 后序遍历
- 层次遍历
// 前序遍历
void preOrderTraverse(BiTree t)
{
if (t == null) return;
invite(t->data);
preOrderTraverse(t->lchild);
preOrderTraverse(t->rchild);
}
// 中序遍历
void inOrderTraverse(BiTree t)
{
if (t == null) return;
inOrderTraverse(t->lchild);
invite(t->data);
inOrderTraverse(t->rchild);
}
// 后序遍历
void postOrderTraverse(BiTree t)
{
if (t == null) return;
postOrderTraverse(t->lchild);
postOrderTraverse(t->rchild);
invite(t->data);
}
对于二叉树的创建，如果按照前序遍历的方式，只不过将访问的操作替换成了，构建结点并赋值的操作。
其他仍旧和前序遍历的代码是一致的。
note：需要对原始的二叉树进行扩展，使其叶子结点变为非叶子结点。可以通过添加#元素的结点来判断是否为为null的操作。
4. 线索二叉树
由于二叉链表存储含有空节点，因此为了更好地利用空间及查找每个结点的前驱和后继，
因此出现了线索二叉树。其实就是一个双向链表的形式。
5. Huffman哈弗曼树（最优二叉树）
- 每个叶子结点都带有权值，而所有叶子结点到树根之间的带权路径和最小的树为哈弗曼树。
- 按照每个字符集出现的次数/频率，构造Huffman，然后将每个结点的分支标记为左0右1.
- 这样组成的01序列即为huffman编码。
6. 二叉排序树（二叉查找树）BST
-
查找效率：o(h)
-
查找效率与树的深度有关。而深度与树的形状有关。因此，树越平衡，则h越小，相应的查找效率越高。
-
中序遍历是一个有序的集合，插入和删除依旧保持有序。
删除时，分三种情况：- 是否为子节点
- 是否有左子树/右子树
- 是否左右子树都有。
若都有，则需要找到删除元素的前驱和后继，让其中一个去替换即可。
7. 平衡二叉树AVL
-
查找：o(logn)
-
插入/删除 o(logn)
-
高度平衡的二叉搜索树，每个节点的左右子树差绝对值<=1。
即 BST && |BF|<=1.
不平衡时进行旋转操作：
在插入结点b时：
- BF > 1，找到距离b的父节点更近的不平衡结点n，然后右旋结点n。(如果n和n.child的BF
符号不同，则需要先左旋n.child结点，再进行n结点的右旋操作)； - BF < -1, 找到距离b的父节点更近的不平衡结点n，然后左旋结点n。(如果n和n.child的BF
符号不同，则需要先右旋n.child结点，再进行r结点的左旋操作)。 - 即：+➡，-←。
数据结构
typedef int DataType;
typedef struct SNode
{
DataType data;
int bf;
struct SNode *lchild, *rchild;
} SNode, * BiTree;
// 右旋
void r_rotate(BiTree *p)
{
BiTree L = (*p)->lchild;
(*p)->lchild = L->rchild;
L->rchild = (*p);
(*p) = L;
}
拿到右旋结点p的左子树L，将L的rchild挂到p的lchild。将p挂到L的rchild。
// 左旋
void l_rotate(BiTree *p)
{
BiTree R = (*p)->rchild;
(*p)->rchild = R->lchild;
R->lchild = (*p);
(*p) = R;
}
拿到左旋结点p的右子树R，将R的lchild挂到p的rchild。将p挂到R的lchild。
8. 多路查找树（B树），前提：排序树。
上述的二叉树的每个结点都只能存储一个元素，且最多有两个子结点。
而多路的定义是：每个节点孩子数可以多于两个，每个结点可以存储多个元素。
有4中特殊形式：
- 2-3树
- 2-3-4树
- B树
- B+树
2-3树：每个结点都具有两个孩子(2结点)或三个孩子(3结点)。
- 2结点：包含一个元素和两个孩子（或没有孩子），并且是排序树；
- 3结点：包含两个个元素和三个孩子（或没有孩子），并且是排序树；
- 所有叶子结点都在同一层。
B树：针对内存与外存之间的存取而专门设计的。
