概念
定义
- 树枝分叉处、树叶、树根抽象为结点（node）
- 树根抽象为根结点（root），一棵树最多存在一个根结点
- 树叶抽象为叶子节点（leaf），不再延伸出新的结点
- 茎干和树枝抽象为边（edge），一条边只用来连接两个结点
- 树中的结点不能被边连成环
- 子结点（child）、子树（subtree）
性质
- 树可以没有结点（空树，empty tree）
- 树的层次（layer）从根结点开始算，根结点为第一层
- 结点的子树棵数为结点的度（degree），树中结点的最大的度称为树的度（宽度）
- 满足连通、边数等于顶点数减1的结构一定是一棵树
- 叶子节点是度为0的节点，所以树中只有一个结点（根结点）时根结点也是叶子结点
- 结点的深度（depth）是从根结点从上到下累加到该结点时的深度值，结点的高度（height）是从最底层叶子结点从下到上累加到该结点时的高度值，整个树的深度和高度相等
- 多棵树组合在一起称为森林（forest）
二叉树
二叉树的递归定义
- 没有结点，是一棵空树
- 由根结点、左子树、右子树构成，且左子树和右子树都是二叉树
注意：度为2的树左右子树没区别，二叉树左右子树有区别
两种特殊的二叉树
- 满二叉树：每一层结点个数都达到了当层能达到的最大结点数
- 完全二叉树：除了最下面一层，其余层都达到了当层能达到的最大结点数，且最下面一层只从左到右连续存在若干结点，右边的都不存在
二叉树的存储结构
-
二叉树使用链表来定义
struct node { typename data; node* lchild; node* rchild; }二叉树建树前根结点不存在，地址设置为NULL。
node* root = NULL;如果需要新建结点，可以使用下面的函数：
node* newNode(int v) { node* Node = new node; Node->data = v; Node->lchild = NULL; Node->rchild = NULL; return Node; }
二叉树的操作
-
查找、修改
用递归完成查找、修改操作。
void search(node* root, int x, int newdata) { if (root == NULL) { return; // 空树（递归边界） } if (root->data == x) { root->data = newdata; } search(root->lchild, x, newdata); search(root->rchild, x, newdata); } -
插入
二叉树结点的插入位置就是数据域在二叉树中查找失败的位置。
根结点指针
root使用了引用&。void insert(node* &root, int x) { if (root == NULL) { root = newNode(x); return; } if (由二叉树性质，x应该插在左子树) { insert(root->lchild, x); } else { insert(root->rchild, x); } } -
创建
把需要插入的数据存储在数组中，再用
insert函数一个个插入二叉树中；或者边输入数据边插入结点。node* Create(int data[], int n) { node* root = NULL; for (int i = 0; i < n; i++) { insert(root, data[i]); } return root; }
完全二叉树的存储结构
- 给完全二叉树的所有结点从上到下、从左到右编号（从1开始）
- 对完全二叉树中的任何一个结点x，左孩子编号一定是2x，右孩子编号一定是2x+1
- 完全二叉树可以通过大小为2k的数组存放所有节点的信息，k为完全二叉树的最大高度，1号位存放的必须是根结点
- 存放元素的顺序恰好为该完全二叉树的层序遍历序列
- 判断某个结点是否为叶结点：该结点的左子结点编号node*2大于结点总个数n
- 判断某个结点是否为空结点：该结点下标大于结点总个数
二叉树的遍历
- 先序遍历、中序遍历、后序遍历：DFS，序指的是根节点遍历的顺序
- 层次遍历：BFS
先序遍历
-
根结点→左子树→右子树
void preorder(node* root) { if (root == NULL) { return; // 递归边界 } // 访问根结点 printf("%d", root->data); // 访问左子树 preorder(root->lchild); // 访问右子树 preorder(root->rchild); }根结点一定在最前面。
中序遍历
-
左子树→根节点→右子树
void inorder(node* root) { if (root == NULL) { return; // 递归边界 } // 访问左子树 inorder(root->lchild); // 访问根结点 printf("%d", root->data); // 访问右子树 inorder(root->rchild); }只要知道根结点，就可以知道左子树和右子树。
后序遍历
-
左子树→右子树→根结点
void postorder(node* root) { if (root == NULL) { return; // 递归边界 } // 访问左子树 postorder(root->lchild); // 访问右子树 postorder(root->rchild); // 访问根结点 printf("%d", root->data); }根结点一定在最后面。
通过先序遍历序列和后序遍历序列都只能得到根结点，只有通过中序遍历序列才能用根结点把左右子树分开，从而唯一确定一棵二叉树。只有保证所有元素都不同时才能使用。
层次遍历
-
从根节点向下逐层遍历，同一层从左到右遍历
void LayerOrder(node* root) { queue<node*> q; q.push(root); while (!q.empty()) { node* cur = q.front(); q.pop(); printf("%d", cur->data); if (cur->lchild != NULL) { q.push(cur->lchild); } if (cur->rchild != NULL) { q.push(cur->rchild); } } }如果要记录层数，要在结构体内加个
layer，并在入队前令root的layer为1，然后每次在cur->lchild和cur->rchild入队前都让它们的层号等于cur的层号加1。
重建二叉树
用中序遍历序列和先序遍历序列、后序遍历序列、层序遍历序列中的一个重建二叉树。
例：用先序遍历序列和中序遍历序列重建二叉树
- 已知先序序列为pre1、pre2、……、pren，中序序列为in1、in2、……、inn
- 由先序序列的性质，先序序列的第一个元素pre1是当前二叉树的根结点
- 由中序序列的性质，当前二叉树的根节点将中序序列划分为左、右子树
- 在中序序列中找到结点ink，使得ink==pre1，这样就在中序序列中找到了根节点
// 当前先序序列为[preL, preR]，中序序列为[inL, inR]，返回根结点地址
node* create(int preL, int preR, int inL, int inR) {
if (preL > preR) {
return NULL; // 先序序列长度小于等于0时，直接返回
}
node* root = new node; // 新建一个新的结点，用来存放当前二叉树的根结点
root->data = pre[preL]; // 新结点的数据域为根结点的值
int k;
for (k = inL; k <= inR; k++) {
if (in[k] == pre[preL]) { // 在中序序列中找到in[k] == pre[L]的结点
break;
}
}
int numLeft = k - inL; // 左子树的结点个数
// 左子树的先序区间[preL+1, preL+numLeft]，中序区间[inL, k-1]
// 返回左子树的根结点地址，赋值给root的左指针
root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
// 右子树的先序区间[preL+numLeft+1, preR]，中序区间[k+1, inR]
// 返回右子树的根结点地址，赋值给root的右指针
root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);
return root;
}
二叉查找树（BST）
- 特殊的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树
- 递归定义
- 要么二叉查找树是一棵空树
- 要么二叉查找树由根结点、左子树、右子树组成，其中左右子树都是二叉查找树，且左子树上所有结点的数据域均小于等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域
基本操作
-
查找
void search(node* root, int x) { if (root == NULL) { return; } if (x == root->data) { printf("%d\n", root->data); } else if (x < root->data) { search(root->lchild, x); } else { search(root->rchild, x); } } -
插入
void insert(node* &root, int x) { if (root == NULL) { root = newNode(x); return; } if (x == root->data) { return; } else if (x < root->data) { insert(root->lchild, x); } else { insert(root->rchild, x); } } -
建立
node* Create(int data[], int n) { node* root = NULL; for (int i = 0; i < n; i++) { insert(root, data[i]); } return root; } -
删除
- 把以二叉查找树中比结点权值小的最大结点称为前驱，是该结点左子树的最右结点
- 把以二叉查找树中比结点权值大的最小结点称为后继，是该结点右子树的最左结点
- 用前驱或后继覆盖原来的结点，再把前驱或后继删除即可删除元素
思路如下：
- 如果当前结点
root为空，说明不存在权值为x的结点，直接返回 - 如果当前结点
root的权值为给定权值x，进入删除处理- 如果当前结点
root不存在左右孩子，说明是叶子结点，直接删除 - 如果当前结点
root存在左孩子，则在左子树中寻找前驱pre，让pre的数据覆盖root，并在左子树中删除结点pre - 如果当前结点
root存在右孩子，则在右子树中寻找后继next，让next的数据覆盖root，并在右子树中删除结点next
- 如果当前结点
- 如果当前结点
root的权值大于x，则在左子树中递归删除权值为x的结点 - 如果当前结点
root的权值小于x，则在右子树中递归删除权值为x的结点
node* findMax(node* root) { node* p = root; while (p->rchild != NULL) { p = p->rchild; } } node* findMin(node* root) { node* p = root; while (p->lchild != NULL) { p = p->lchild; } return p; } void deleteNode(node* &root, int x) { if (root == NULL) { return; } if (root->data == x) { if (root->lchild == NULL && root->rchild == NULL) { root = NULL; } else if (root->lchild != NULL) { node* pre = findMax(root->lchild); root->data = pre->data; deleteNode(root->lchild, pre->data); } else { node* next = findMin(root->rchild); root->data = next->data; deleteNode(root->rchild, next->data); } } else if (root->data > x) { deleteNode(root->lchild, x); } else { deleteNode(root->rchild, x); } }
二叉查找树的性质
对二叉查找树进行中序遍历，遍历的结果是有序的。
平衡二叉树（AVL）
任意结点左右子树高度差绝对值不超过1的二叉查找树。
在结点结构体内记录高度，因为平衡因子不能通过左右子树平衡因子得到，只能通过左右子树高度差得到。
并查集
father[i]数组，表示元素i的父结点是father[i]，根结点father[i]==i，也即所属集合。
堆
- 一棵完全二叉树，每个结点的值都不小于（或不大于）左右孩子结点的值
- 父结点大于等于子结点叫大顶堆，父结点小于等于子结点叫小顶堆
哈夫曼树
已知n个数，寻找一棵树，使得树的所有叶子结点的权值恰好为这n个数，并且使得这棵树的带权路径长度最小。
- 叶子结点的权值乘以路径长度的结果称为叶子结点的带权路径长度
- 树的带权路径长度大于所有叶子结点带权路径长度之和
- 带权路径长度最小的数被称为哈夫曼树（最优二叉树）
- 对同一组叶子结点来说，哈夫曼树不唯一，最小带权路径长度唯一
构造哈夫曼树
- 初始状态下共有n个结点，结点的权值分别是给定的n个数，将它们视作n棵只有一个结点的树
- 合并其中根结点权值最小的两棵树，生成两棵树根结点的父结点，权值为这两个根结点的权值之和
- 重复步骤2，直到只剩一棵树为止，这棵树就是哈夫曼树
性质
- 不存在度为1的结点
- 权值越高的结点越接近根结点
构建
- 反复选择两个最小的元素，合并，直到剩下一个元素
- 用优先队列（堆）执行这种策略
#include <cstdio>
#include <queue>
using namespace std;
// 小顶堆
priority_queue<long long, vector<long long>, greater<long long> > q;
int main() {
int n;
long long temp, x, y, ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &temp);
q.push(temp);
}
while (q.size() > 1) {
x = q.top();
q.pop();
y = q.top();
q.pop();
q.push(x + y);
ans += x + y;
}
printf("%lld\n", ans);
return 0;
}
哈夫曼编码
如果把二叉树左分支都标为0，右分支都标为1，则对任何一个结点都可以从根结点出发得到结点编码，且对于任何一个叶子结点，编号一定不会成为其他结点编号的前缀。
- 任何一个字符的编码都不是另一个字符编码的前缀，这种编码方式叫做前缀编码
- 字符串编码后的长度是树的带权路径长度
- 把每个字符出现的次数作为叶子结点的权值，求一棵树，使得这棵树的带权路径长度最小
- 需要构建具体的哈夫曼树