树的概念
树由有限个节点，组成具有层次关系的集合。每个结点或者无子结点或者只有有限个子结点;
有一个特殊的结点,它没有父结点，称为根结点。每一个非根节点有且只有一个父节点。并且树里面没有环路。
结点的度: 一个结点含有的子结点个数称为该结点的度;
树的度: 一棵树中，最大结点的度称为树的度;
按照有序性，可以分为有序树和无序树：
无序树：树中任意节点的子结点之间没有顺序关系 有序树：树中任意节点的子结点之间有顺序关系
二叉树
二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
二叉树可以分为以下几种：
(完)满二叉树：
叶节点除外的所有节点均含有两个子树的树被称为满二叉树;
完全二叉树：
如果一颗二叉树除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布
带权路径最短的二叉树，哈夫曼树应用于通讯及数据传送中对信息的二进制编码。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
首先它是一颗二叉树，若左子树不空，则左子树上所有结点的值均小于它的根结点的值;
若右子树不空，则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树;
红黑树是一颗特殊的二叉查找树，每个节点都是黑色或者红色，根节点、叶子节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的。
一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
| 完全二叉树 | 完美二叉树 | |
|---|---|---|
| 总节点k | $2^{h-1}$ <= k <= $2^{h} - 1$ | k = $2^{h} - 1$ |
| 树高h | h = $log_{2}k + 1$ | h = $log_{2}(k+1)$ |
基础应用：
以此树为例：
// 二叉树节点
struct Node
{
int value;
struct Node* left;
struct Node* right;
Node(int data) : value(data), left(nullptr), right(nullptr) {};
};
bfs 层次遍历
// 利用队列来做。
void LevelOrder(Node* head)
{
if (head) {
queue<Node*> queue;
queue.push(head);
Node* cur;
while (!queue.empty()) {
cur = queue.front();
queue.pop();
cout << cur->value << " ";
if (cur->left)
queue.push(cur->left);
if (cur->right)
queue.push(cur->right);
}
}
}
dfs 前中后 序
// 先序遍历
void PreOrder(Node* head)
{
if (head == nullptr)
return;
cout << head->value << " ";
PreOrder(head->left);
PreOrder(head->right);
}
// 中序遍历
void InOrder(Node* head)
{
if (head == nullptr)
return;
InOrder(head->left);
cout << head->value << " ";
InOrder(head->right);
}
// 后序遍历
void PosOrder(Node* head)
{
if (head == nullptr)
return;
PosOrder(head->left);
PosOrder(head->right);
cout << head->value << " ";
}
使用栈实现的前中后序遍历
vector<int> preorderTraversal(TreeNode* root) {
vector<int> retvec;
stack<TreeNode*> stk;
while (root != NULL || !stk.empty()) {
while (root != NULL) {
retvec.push_back(root->val);
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
root = root->right;
}
}
// 中序遍历.
vector<int> preorderTraversal(TreeNode* root) {
vector<int> retvec;
stack<TreeNode*> stk;
while (root != NULL || !stk.empty()) {
while (root != NULL) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
retvec.push_back(root->val);
root = root->right;
}
}
/* 补充: 后序遍历
前序遍历 => 根, 左, 右.
后序遍历 => 左, 右, 根.
仿照前序遍历方法求解出 => 根, 右, 左.
reverse => 得到后序遍历. */
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> vec;
while (root != NULL || !stk.empty()) {
while (root != NULL) {
vec.push_back(root->val);
stk.push(root);
root = root->right;
}
root = stk.top();
stk.pop();
root = root->left;
}
reverse(vec.begin(), vec.end());
return vec;
}
二叉树应用：
- 蓝桥杯：挑选工厂
/* 问题描述
最近，WYF正准备参观他的点卡工厂。WYF集团的经理氰垃圾需要帮助WYF设计参观路线。现在，氰垃圾知道一下几件事情：
1.WYF的点卡工厂构成一颗二叉树。
2.一共有n座工厂。
3.他需要把这颗树上的点以后序遍历的方法列出来，才能绘制地图。
还好，最近他的属下给了他先序遍历和中序遍历的数据。可是，氰垃圾最近还要帮㊎澤穻解决一些问题，没有时间。
请你帮帮他，替他完成这项任务。由于氰垃圾的一些特殊的要求，WYF的参观路线将会是这棵树的后序遍历。
输入格式
第一行一个整数n，表示一共又n座工厂。
第二行n个整数，表示先序遍历。
第三行n个整数，表示中序遍历。
输出格式
输出共一行，包含n个整数，为后序遍历。
样例输入
8
1 2 4 5 7 3 6 8
4 2 7 5 1 8 6 3
样例输出
4 7 5 2 8 6 3 1
数据规模和约定
0<n<100000,。保证先序遍历和中序遍历合法，且均为1～n。 */
/* 此题即为由先、中序排列确定 后序排序; 首先要知道一个结论，前序/后序+中序序列可以唯一确定一棵二叉树，所以自然而然可以用来建树。
看一下前序和中序有什么特点，前序1,2,4,7,3,5,6,8 ，中序4,7,2,1,5,3,8,6；
有如下特征：
前序中左起第一位1肯定是根结点，我们可以据此找到中序中根结点的位置rootin；（后序中最后一位肯定是根节点。）
中序中根结点左边就是左子树结点，右边就是右子树结点，即[左子树结点，根结点，右子树结点]，我们就可以得出左子树结点个数为int left = rootin - leftin;；
前序中结点分布应该是：[根结点，左子树结点，右子树结点]；（后序中分布：[左子树节点, 右子树节点, 根节点]）
根据前一步确定的左子树个数，可以确定前序中左子树结点和右子树结点的范围；
如果我们要前序遍历生成二叉树的话，下一层递归应该是：
左子树：root->left = pre_order; (前序左子树范围，中序左子树范围，前序序列，中序序列)
右子树：root->right = pre_order; (前序右子树范围，中序右子树范围，前序序列，中序序列)
每一层递归都要返回当前根结点root；
*/
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(NULL), right(NULL) {}
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode *OrderToTree(int L_Pre, int R_Pre, int L_In, int R_In, vector<int> &Pre, vector<int> &In)
{
if (L_Pre > R_Pre || L_In > R_In)
return NULL;
TreeNode *root = new TreeNode(Pre[L_Pre]); //前序排列中 最左位为根节点
int in_root = L_In;
while (In[in_root] != Pre[L_Pre]) {
in_root++; }
int left = in_root - L_In;
root->left = OrderToTree(L_Pre + 1, L_Pre + left, L_In, L_In + left, Pre, In);
root->right = OrderToTree(L_Pre + left +1, R_Pre, L_In + left +1, R_In, Pre, In);
return root;
}
//打印逆序排序
void PosOrder (TreeNode* root)
{
if(root == NULL)
return;
PosOrder(root->left);
PosOrder(root->right);
cout << root->val << ' ';
}
int main ()
{
int n; // 0<n<=1000000
// int PreNumber[100000] = {0}, InNumber[100000] = {0}, PosNumber[100000] = {0};
vector<int> PreNumber, InNumber, PosNumber;
cin >> n;
for (int i = 0; i < n; i++) {
int j;
cin >> j;
PreNumber.push_back(j);
}
for (int i = 0; i < n; i++) {
int j;
cin >> j;
InNumber.push_back(j);
}
TreeNode *root = OrderToTree(0, n-1, 0, n-1, PreNumber, InNumber);
PosOrder (root);
return 0;
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
// 注意题中说明 二叉树中的各个值不相同,不需要考虑不成立的情况
// 前序/后序+中序序列可以唯一确定一棵二叉树，只知道前序和后序不唯一确定
// 前序是 root + 左树节点 + 右树节点
// 后序是 左树节点 + 右树节点 + root
// 所以后序的倒数第二个是前序中右树的根节点 前序的第二个是后续的前树的根节点最后一位 如此递推就有规律
class Solution {
public:
// l1 r1限定pre的子树区域，l2 r2限定post的子树区域。
// 此法默认优先生成左子树（即只有一边子树时默认是左子树）
TreeNode* build_tree(vector<int>& pre, vector<int>& post, int l1, int r1, int l2, int r2) {
if(l1 > r1)
return nullptr;
TreeNode *root = new TreeNode(pre[l1]); //或post[r2]
for (int i = r2-1; i >= l2; i--) {
if(pre[l1+1] == post[i]) {
int len = i - l2;
root->left = build_tree(pre, post, l1+1, l1+len+1, l2, i);
root->right = build_tree(pre, post, l1+len+2, r1, i+1, r2-1);
break;
}
}
return root;
}
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
TreeNode* ans = build_tree(preorder, postorder, 0, postorder.size()-1, 0, preorder.size()-1);
return ans;
}
};
class BSTIterator {
private:
TreeNode* cur;
stack<TreeNode*> stk;
public:
BSTIterator(TreeNode* root): cur(root) {}
int next() {
while (cur != nullptr) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
int ret = cur->val;
cur = cur->right;
return ret;
}
bool hasNext() {
return cur != nullptr || !stk.empty();
}
};
红黑树
红黑树是一种自平衡的二叉搜索树，并且其附加定义如下：
- 节点有且只有两种颜色，红色和黑色
- 根节点和叶子节点必须是黑色，其中，叶子节点是虚拟存在的空节点NULL
- 红色节点的两个子节点必须是黑色
- 任意节点到叶子节点的路径上，必须包含相同数目的黑色节点
map multimap 的底层是红黑树 中序遍历会是有序的，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，
所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。
unordered_map 的底层是用哈希表来实现的 无序，通过key的哈希路由到每一个桶（即数组）用来存放内容。通过key来获取value的时间复杂度就是O（1）。
因为key的哈希容易碰撞，所以需要对碰撞做处理。map里的每一个数组（桶）里面存的其实是一个链表，key的哈希冲突以后会加到链表的尾部，
这是再通过key获取value的时间复杂度就变成O(n），当碰撞很多的时候查询就会变慢。为了优化这个时间复杂度，map的底层就把这个链表转换成了 平衡树，
这样虽然插入增加了复杂度，但提高了频繁哈希碰撞时的查询效率，使哈希碰撞时查询效率变成O(log n)。
前缀树 trie tree
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
又称为字典树 trie tree，是一种是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
下面给出一个小写字符串映射的 tire tree 简易实现:
208. 实现 Trie (前缀树) - 力扣（LeetCode）
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
struct TrieNode {
bool flag; // 为true 表示存在以该节点为尾部的值
unordered_map<char, TrieNode*> son;
TrieNode(): flag(false) {}
};
class Trie {
private:
TrieNode* root = nullptr;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* now = root;
for (const char& w : word) {
if(now->son.find(w) == now->son.end())
now->son[w] = new TrieNode();
now = now->son[w];
}
now->flag = true;
}
bool search(string word) {
TrieNode* now = root;
for (const char& w : word) {
if(now->son.find(w) == now->son.end())
return false;
now = now->son[w];
}
return now->flag;
}
bool startsWith(string prefix) {
TrieNode* now = root;
for (const char& w : prefix) {
if(now->son.find(w) == now->son.end())
return false;
now = now->son[w];
}
return now;
}
};
基数树 radix tree
radix树 简单来说就是 tire 树的压缩路径版本，Trie树一般用于字符串到对象的映射（Trie树看成是一个基为26的Radix树），而radix树一般用于长整数到对象的映射。
对于长整型数据的映射，怎样解决Hash冲突和Hash表大小的设计是一个非常头疼的问题。radix树就是针对这对这样的稀疏长整型数据查找，能高速且节省空间地完成映射。借助于Radix树，我们能够实现对于长整型数据类型的路由。利用radix树能够依据一个长整型（比如一个长ID）高速的找到其相应的对象指针。这比用hash映射来的简单，也更节省空间，使用Hash映射hash函数难以设计，不恰当的hash函数可能增大冲突，或浪费空间。
radix tree是一种多叉搜索树，树的叶子节点是实际的数据条目。每一个节点有一个固定的、2^n指针指向子节点（每一个指针称为slot，n为划分的基的大小）。
redis之radix tree_happytree001的博客 介绍了c编写的 redis 如何实现 radix 树
其主要区别实现在于 iscompr 字段记录该key是否为压缩字符串
平衡二叉树
B树
MySQL索引底层：B+树详解 包含内容:
- B-树、B+树简介
- B+树插入
- B+树查找
- B+树删除
- B+树经典面试题