高级数据结构_二叉树

发表于2022-05-20更新于2025-09-28阅读次数

内容

  1. 树相关概念

考点

  1. CreateBinaryTree
  2. NicePreOrder - 前序遍历、NiceInOrder - 中序遍历、NicePostOrder - 后序遍历
  3. 二叉树是否是完全二叉树、满二叉树、二叉搜索树、平衡二叉树

相关术语及翻译

术语 英译
先序遍历 PreOrder Traversal
中序遍历 InOrder Traversal
后序遍历 PostOrder Traversal

树相关概念

三个字来总结：一对多。

树是由n(n>=0)个结点组成的有限集合。
如果n=0，称为空树；
如果n>0，则有一个特定的称之为根(root)的结点， 它只有直接后继， 但没有直接前驱；
除根以外的其它结点划分为m(m>=0)个互不相交的有限集合T0,T1,Tm−1T_0, T_1, T_{m-1}，每个集合又是一棵树，并且称之为根的子树(subTree) 。每棵子树的根结点有且仅有一个直接前驱， 但可以有0个或多个直接后继。

  1. 节点的度：一个节点含有的子树的个数（直接后继节点）。
  2. 树的度：一棵树中，所有节点的度中的最大值。
  3. 叶节点（终端节点）：度为0的节点。
  4. 非叶节点（分支节点）：度不为0的节点。
  5. 父节点（双亲）：若一个节点含有子节点，则是其子节点的父节点；某节点的直接前驱节点。
  6. 子节点（孩子）：一个节点的字树的根节点（或直接后继节点）。
  7. 兄弟节点：有相同父节点的节点互称为兄弟节点。
  8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
  9. 深度：即从根（第1层）到第n层的路径长，根的深度为0。即层次数-1。——偏向于层
  10. 高度：从根节点到叶节点的最长路径。当只有根节点时，路径为0即高度为0。——偏向于一条路径
  11. 堂兄弟节点：它们的父节点不同，但它们的父节点在同一层的节点，互为堂兄弟。
  12. 祖先节点：从根到该节点路径上所经过的所有节点；有的解释为爷爷节点。

二叉树概念

二叉树的定义：一棵二叉树是节点的一个有限集合，该集合或为空，或为由一个根节点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。

从定义可以看出，“二叉树是由二叉树组成的”，属于递归式定义。如果某件事物的本质是递归的，那么我们解决此类事物的方法往往也是递归式的。

二叉树的性质

  1. 若二叉树的层次从00开始，则第ii层最多有2i2^i个节点(i≥0)(i\ge0)。可用数学归纳法证明。
  2. 高度为kk的二叉树最多有2k+1−12^{k+1}-1个节点(k≥0)(k\ge0)。可用等比数列求和公式得出。
  3. 对于任何一棵二叉树，如果叶节点个数为n0n_0（nn的下标表示度数），度为2的非叶节点个数为n2n_2，则有n0=n2+1n_0=n_2+1。

特殊的二叉树

满二叉树 - Full Binary Tree

二叉树的每一层的节点数都达到最大值。

image-20220520153714340

完全二叉树 - Complete Binary Tree

若二叉树的高度为hh，则共有h+1h+1层。除第hh层外，其他各层(0 ~ h-1)的节点数都达到最大个数，第hh层从右向左连续缺0个或若干个节点。满二叉树是一种特殊的完全二叉树。

具有nn个节点的完全二叉树的高度为⌈log⁡2(n+1)⌉−1\lceil\log_2(n+1)\rceil-1。注意，只适于完全二叉树，不适于一般的二叉树。

证明：设完全二叉树的高度为hh，则有

\begin{flalign} &~~~~~~2^h-1<n\le2^{h+1}-1\\ &\Leftrightarrow 2^h<n+1\le2^{h+1}\\ 取对数&\Leftrightarrow h<\log_2(n+1)\le h+1& \end{flalign}

image-20220520154516885

中序+前序/后序序列建立二叉树

遍历方式 步骤
先序遍历 先操作根节点，再遍历左子树，再遍历右子树
中序遍历 先遍历左子树，返回后再操作根节点，再遍历右子树
后序遍历 先遍历左子树，再遍历右子树，再操作根节点。

image-20220520163512650

如此一棵二叉树。手写出三种方式遍历的序列：

1
2
3
先序遍历：ABCDEFGH
中序遍历：CBEDFAGH
后序遍历：CEFDBHGA

我们观察手写出来的先序遍历序列和中序遍历序列，发现规律。

在先序遍历中可以看出，A为根节点，以A为基准，再把目光转向中序遍历，则可以看出以A划分出了CBEDF和GH，而这也分别对应A节点的左子树和右子树。
按照这个规律，再看先序遍历，A后面一个是B，以B为基准，再把目光转向中序遍历，则可以看出以B划分出了C和EDF，而这也分别对应B节点的左子树和右子树。
…
因此可以根据中序遍历序列和先序/后序遍历序列的其中一种来复画二叉树逻辑结构。

由此，相应地，我们的代码逻辑也浮于水面。先来看根据前序、中序序列来创建二叉树代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BtNode* CreatePreIn(const char * pre_str, const char * in_str, int len)
{
    BtNode * s = NULL;
    if(len >= 1)
    {
        s = Buynode();
        s->data = pre_str[0];
        int pos = FindInStr(in_str, len, pre_str[0]);
        if(pos == -1)
        {
            exit(1);
        }
        s->left  = CreatePreIn(pre_str+1, in_str, pos);	//左子树
        s->right = CreatePreIn(pre_str+pos+1, in_str+pos+1, len-pos-1);//右子树
    }
    return s;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cassert>
#include<cstring>
using namespace std;
typedef char ElemType;
typedef struct BtNode
{
    BtNode * left;
    BtNode * right;
    ElemType data;
}BtNode, *BinaryTree;
BtNode* Buynode()
{
    BtNode * s = (BtNode*)malloc(sizeof(BtNode));
    if(s == NULL)
    {
        exit(1);
    }
    return s;
}
int FindInStr(const char * in_str, int len, char ch)
{
    assert(in_str != NULL);
    int pos = -1;
    int i = 0;
    while(i < len)
    {
        if(in_str[i]==ch)
        {
            pos = i;
            break;
        }
        ++i;
    }
    return pos;
}
BtNode* CreatePreIn(const char * pre_str, const char * in_str, int len)
{
    BtNode * s = NULL;
    if(len >= 1)
    {
        s = Buynode();
        s->data = pre_str[0];
        int pos = FindInStr(in_str, len, pre_str[0]);
        if(pos == -1)
        {
            exit(1);
        }
        s->left  = CreatePreIn(pre_str+1, in_str, pos);	//左子树
        s->right = CreatePreIn(pre_str+pos+1, in_str+pos+1, len-pos-1);//右子树
    }
    return s;
}
BtNode* CreateTreePreIn(const char * pre_str, const char * in_str)
{
    if(pre_str == NULL || in_str == NULL)return NULL;
    int pre_len = strlen(pre_str);
    int in_len = strlen(in_str);
    if(pre_len != in_len)return NULL;
    return CreatePreIn(pre_str, in_str, pre_len);
}
void PrintPre(BinaryTree bt)
{
    if(bt == NULL)return;
    cout << bt->data << " ";
    PrintPre(bt->left);
    PrintPre(bt->right);
}
void PrintIn(BinaryTree bt)
{
    if(bt == NULL)return;
    PrintIn(bt->left);
    cout << bt->data << " ";
    PrintIn(bt->right);
}
void PrintPost(BinaryTree bt)
{
    if(bt == NULL)return;
    PrintPost(bt->left);
    PrintPost(bt->right);
    cout << bt->data << " ";
}
int main()
{
    BinaryTree root = NULL;
    char pre_str[] = {"ABCDEFGH"};
    char in_str[] = {"CBEDFAGH"};
    root = CreateTreePreIn(pre_str, in_str);
    PrintPre(root); cout << endl;
    PrintIn(root); cout << endl;
    PrintPost(root); cout << endl;
    return 0;
}

运行结果

image-20220520180445645

相应地，可以得出后序、中序序列建立二叉树代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cassert>
#include<cstring>
using namespace std;
typedef char ElemType;
typedef struct BtNode
{
    BtNode * left;
    BtNode * right;
    ElemType data;
}BtNode, *BinaryTree;
BtNode* Buynode()
{
    BtNode * s = (BtNode*)malloc(sizeof(BtNode));
    if(s == NULL)
    {
        exit(1);
    }
    return s;
}
int FindInStr(const char * in_str, int len, char ch)
{
    assert(in_str != NULL);
    int pos = -1;
    int i = 0;
    while(i < len)
    {
        if(in_str[i]==ch)
        {
            pos = i;
            break;
        }
        ++i;
    }
    return pos;
}
BtNode* CreatePostIn(const char * post_str, const char * in_str, int len)
{
    BtNode * s = NULL;
    if(len >= 1)
    {
        s = Buynode();
        s->data = post_str[len-1];
        int pos = FindInStr(in_str, len, post_str[len-1]);
        if(pos == -1)
        {
            exit(1);
        }
        s->left  = CreatePostIn(post_str, in_str, pos);	               //左子树
        s->right = CreatePostIn(post_str+pos, in_str+pos+1, len-pos-1);//右子树
    }
    return s;
}
BtNode* CreateTreePostIn(const char * post_str, const char * in_str)
{
    if(post_str == NULL || in_str == NULL)return NULL;
    int pre_len = strlen(post_str);
    int in_len = strlen(in_str);
    if(pre_len != in_len)return NULL;
    return CreatePostIn(post_str, in_str, pre_len);
}
void PrintPre(BinaryTree bt)
{
    if(bt == NULL)return;
    cout << bt->data << " ";
    PrintPre(bt->left);
    PrintPre(bt->right);
}
void PrintIn(BinaryTree bt)
{
    if(bt == NULL)return;
    PrintIn(bt->left);
    cout << bt->data << " ";
    PrintIn(bt->right);
}
void PrintPost(BinaryTree bt)
{
    if(bt == NULL)return;
    PrintPost(bt->left);
    PrintPost(bt->right);
    cout << bt->data << " ";
}
int main()
{
    BinaryTree root = NULL;
    char pre_str[] = {"ABCDEFGH"};
    char in_str[] = {"CBEDFAGH"};
    char post_str[] = {"CEFDBHGA"};
    root = CreateTreePostIn(post_str, in_str);
    PrintPre(root); cout << endl;
    PrintIn(root); cout << endl;
    PrintPost(root); cout << endl;
    return 0;
}

image-20220520183237682

非递归遍历链式存储二叉树

前序遍历

一个栈，先入右，后入左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<stack>
using namespace std;
typedef struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int val;
}TreeNode;
void preorderTraversal(TreeNode* root)
{
    TreeNode* cur = root;
    stack<TreeNode*> st;
    st.push(cur);
    while (!st.empty())
    {
        cur = st.top();
        st.pop();
        cout << cur->val;
        if (cur->right != nullptr)
        {
            st.push(cur->right);
        }
        if (cur->left != nullptr)
        {
            st.push(cur->left);
        }
    }
}

中序遍历

一个栈。

  1. 指针所指节点的左不为空时，入栈左子树
  2. 左空则出栈回退，指针指向出栈的节点（父节点）
  3. 打印
  4. 指针指向右子树
  5. 循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stack>

void inorderTraversal(TreeNode* root)
{
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while(!st.empty() || cur != NULL)
    {
        while(cur != NULL)
        {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        cout << cur->val;
        cur = cur->right;
    }
}

还有一种写法，只是循环的形式稍有不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stack>
void inorderTraversal(TreeNode* root)
{
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while(!st.empty() || cur != NULL)
    {
        if(cur != NULL)
        {
            st.push(cur);
            cur = cur->left;
        }
        else
        {
            cur = st.top();
            st.pop();
            cout << cur->val;
            cur = cur->right;
        }
    }
}

后序遍历

两种方法。

双栈法

模仿前序遍历，但是需要另外一个栈来记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void postorderTraversal(TreeNode* root)
{
    TreeNode* cur = root;
    stack<TreeNode*> st;
    stack<int> ist;
    st.push(cur);
    while (!st.empty())
    {
        cur = st.top();
        st.pop();
        ist.push(cur->val);
        if (cur->left != nullptr)
        {
            st.push(cur->left);
        }
        if (cur->right != nullptr)
        {
            st.push(cur->right);
        }
    }
    while (!ist.empty())
    {
        cout << ist.top();
        ist.pop();
    }
}

迭代法

仍是单栈，但需要一个tag标记指针来记录已经访问过哪个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
typedef struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int val;
}TreeNode;
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* tag = nullptr;
        while (cur != nullptr || !st.empty())
        {
            while (cur != nullptr)
            {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if (cur->right == nullptr || cur->right == tag)
            {
                tag = cur;
                v.push_back(cur->val);
                cout << cur->val;
                cur = nullptr;  //不易写出。
            }
            else
            {
                st.push(cur);
                cur = cur->right;
            }
        }
        return v;
    }
};
int main()
{
    TreeNode n3 = { nullptr, nullptr, 3 };
    TreeNode n2 = { &n3, nullptr, 2 };
    TreeNode n1 = { nullptr, &n2, 1 };
    Solution s;
    s.postorderTraversal(&n1);
}

MySQL_存储引擎

发表于2022-05-19更新于2025-07-30阅读次数

存储引擎

MySQL的一大特点就是支持插件式的存储引擎，即其存储引擎是可更换的，支持不同的存储引擎。

那么，存储引擎代表的是什么呢？

在创建/使用表时，有三大部分需要管理：

  1. 表的结构（有几个字段，字段的类型，约束条件）
  2. 数据
  3. 索引（有利于加速表的查询）

存储引擎直接影响以上三大部分内容的存储方式。即，不同的存储引擎，对应的数据及其结构的存储方式是不一样的。

配置文件

windows下是my.ini

Linux下是my.cnf，在/etc下。

数据库、表对应的文件

都存到了/var/lib/mysql下。

对该目录进行读取时需要进入root用户模式。

  1. ls后发现，每个数据库都会有一个同名的文件夹，里面存放着库中的表。
  2. 进一个文件夹，发现里面每一张表都对应有多种后缀名不同的文件。
    1. .frm表示表的框架信息，即frame。MyISAM和InnoDB存储引擎都要用。
    2. .MYD、.MYI是MyISAM存储引擎下的数据表的文件。
      1. .MYD表示使用MyISAM引擎的表的数据信息，即MyISAM Data。
      2. .MYI表示使用MyISAM引擎的表的索引信息，即MyISAM Index。
    3. .ibd是InnoDB存储引擎下的数据表的文件，同时存储了表的数据信息和索引信息。

可以从表的数据文件的存储方式 - 延伸到索引上

总结

  1. InnoDB的底层文件存储是.frm+.ibd，其中.frm存储的是表的结构，.ibd存储的是数据+索引；
  2. MyISAM的底层文件，表结构、表数据、表索引，各有一个对应的文件。

相关命令

1
SHOW engines;

image-20220519140553878
MyISAM不支持事务。
InnoDB支持事务。
如果仅作查询，则MyISAM比InnoDB轻量级。

各存储引擎区别

存储引擎 锁机制 B树索引 哈希索引 外键 事务 索引缓存 数据缓存
MyISAM 表锁 支持 不支持 不支持 不支持 支持 不支持
InnoDB 行锁 支持 不支持 支持 支持 支持 支持
Memory 表锁 支持 支持 不支持 不支持 支持 支持

锁机制：表示数据库在并发请求访问的时候，多个事务在操作时，并发操作的粒度。

B树索引、哈希索引：加速SQL的查询速度。

外键：子表的字段依赖父表的主键，设置了两张表的依赖关系。

事务：多个SQL语句，保证它们共同执行的原子操作，要么全部成功，要么失败。不能只成功一部分，失败后需要回滚事务。

索引缓存和数据缓存：和MySQL Server的查询缓存相关，在没有对数据和索引做修改之前，重复查询可以不用进行磁盘IO，读取上一次内存中查询的缓存就可以了，提升数据库的性能。

总结

MyISAM不支持事务、也不支持外键。

数据的存储方式

MyISAM

MyISAM索引采用非聚集索引，其优势是访问的速度快，对事务完整性没有要求，以SELECT、INSERT为主的应用基本上都可以使用这个存储引擎来创建表。

MyISAM的表在磁盘上存储成 3 个文件，其文件名都和表名相同，扩展名分别是：
.frm（存储表定义）
.MYD（MYData，存储数据）
.MYI（MYIndex，存储索引）

InnoDB

InnoDB存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全，支持自动增长列，外键等功能，索引采用聚集索引，索引和数据存储在同一个文件，所以InnoDB的表在磁盘上有两个文件，其文件名都和表名相同，扩展名分别是：
.frm（存储表的定义）
.ibd（存储数据和索引）

MEMORY

MEMORY存储引擎使用存在内存中的内容来创建表。
每个MEMORY表实际只对应一个磁盘文件，格式是.frm（表结构定义）。
MEMORY类型的表访问非常快，因为它的数据是放在内存中的，并且默认使用HASH索引（不适合做范围查询），但是一旦服务关闭，表中的数据就会丢失掉。

索引文件和数据文件是否分离造成的结果

见MySQL_索引.md - 一次select where过滤条件查询所经历的事情。