二叉查找树的操作的时间复杂度为。

1.预备知识

树：一些结点的集合，这个集合要么是空集，要么由根结点r和0个或多个非空子树组成，它们的根结点都被来自r的一条有向边连接。
每一棵子树的根叫做跟r的儿子，r是它们的父亲。
没有儿子的结点叫做叶结点（不再向下延伸了）。
路径：从父亲到儿子的序列。
层数：根结点的层数为0，其他结点的层数是父结点的层数+1.
对于任意节点，根节点到它的路径长叫做它的深度，它到它的所有叶节点的路径长的最大值叫做它的高度。一棵树的高度等于它根的高度，一棵树的深度等于它所有叶节点深度的最大值，这两个数是相等的。
如果存在到的一条路径，则是的祖先，如果，则叫真祖先。
树的实现：用一个指针连接第一个儿子，再用一个指针连接自己的兄弟。

struct tree {
    int data;
    tree *firstchild;
    tree *nextsibling;
};

二叉树：每个结点最多有两个儿子。

struct tree {
    int data;
    tree *pright;
    tree *pleft;
};

2.树的遍历

以二叉树为例：
前序遍历：先访问父结点，再访问左子结点，再访问右子结点。
中序遍历：先访问左子结点，再访问父结点，再访问右子结点。
后序遍历：先访问左子结点，再访问右子结点，再访问父结点。
代码：（栈实现不是很容易理解）

#include<iostream>
#include<string>
#include<stack>
using namespace std;
struct Tree {
    int data;
    struct Tree *pleft;
    struct Tree *pright;
}tree[11];

void midtravelR(Tree *proot) {//中序遍历的递归实现
    if (proot == nullptr) return;
    else {
        if (proot->pleft != nullptr) midtravelR(proot->pleft);
        cout << proot->data << endl;
        if (proot->pright != nullptr) midtravelR(proot->pright);
    }
}
void pretravel(Tree *proot) { //前序遍历
    if(proot == nullptr) return;
    else {
        cout << proot->data << endl;
        if (proot->pleft != nullptr) pretravel(proot->pleft);
        if (proot->pright != nullptr) pretravel(proot->pright);
    }
}
void posttravel(Tree *proot) { //后序遍历
    if (proot == nullptr) return;
    else {
        if (proot->pleft != nullptr) posttravel(proot->pleft);
        if (proot->pright != nullptr) posttravel(proot->pright);
        cout << proot->data << endl;
    }
}

void midtravelS(Tree *proot) {//中序遍历的栈实现
    if (proot == nullptr) return;
    else {
        Tree *p = proot;
        stack<Tree *> treestack;
        while (!treestack.empty() || p != nullptr) { //直到栈空而且p==nullptr
            while (p != nullptr) {//遍历左结点，并将其全部进栈
                treestack.push(p);
                p = p->pleft;
            }
            if (!treestack.empty()) {
                p = treestack.top();
                cout << p->data << endl;
                treestack.pop();//输出栈顶元素
                p = p->pright;//切换到右结点，如果没有右结点，下一循环的栈顶元素为父结点
            }
        }
    }
}

int main() {
    Tree *proot;
    for (int i = 0; i <= 10; i++) cin >> tree[i].data;
    proot = &tree[0];
    tree[0].pleft = &tree[1];
    tree[0].pright = &tree[2];
    tree[1].pleft = &tree[3];
    tree[1].pright = &tree[4];
    tree[2].pleft = &tree[5];
    tree[2].pright = &tree[6];
    tree[3].pleft = &tree[7];
    tree[3].pright = &tree[8];
    tree[4].pleft = &tree[9];
    tree[4].pright = &tree[10];
    midtravelR(proot);
    cout << endl;
    midtravelS(proot);
    cout << endl;
    pretravel(proot);
    cout << endl;
    posttravel(proot);
    return 0;
}

3.二叉树

表达式树：叶子结点是数，其他结点是运算符的树。
对表达式树进行前序、中序、后序遍历并输出对应的正好是前缀、中缀、后缀表达式。
把后缀表达式转化为表达式树：建一个树指针栈，将表达式读入，遇到数字就建立一个单节点树并让它进栈；遇到运算符就从栈里弹出两棵树，并将它们以读到的运算符为根形成一棵新树，把这棵新树的指针压进栈里。
代码：

#include<iostream>
#include<stack>
#include<string>
#include<cctype>
using namespace std;
string input;
struct Tree {
    int data;
    Tree *pleft;
    Tree *pright;
};
stack<Tree *> treestack;
Tree roots[100];
int num;

void midtravel(Tree* proot) {
    if (proot == nullptr) return;
    if (proot->pleft != nullptr) {
        cout << '(';
        midtravel(proot->pleft);
        cout << ')';
    }
    cout << char(proot->data);
    if (proot->pright != nullptr) {
        cout << '(';
        midtravel(proot->pright);
        cout << ')';
    }
}


int main() {
    getline(cin, input);
    int len = input.size();
    for (int i = 0; i < len; i++) {
        if (input[i] == ' ') continue;
        if (isalnum(input[i])) {
            roots[num].data = input[i];
            roots[num].pleft = roots[num].pright = nullptr;
            treestack.push(&roots[num]);
            num++;
        }
        else {
            roots[num].data = input[i];
            roots[num].pright = treestack.top();
            treestack.pop();
            roots[num].pleft = treestack.top();
            treestack.pop();
            treestack.push(&roots[num]);
            num++;
        }
    }
    midtravel(treestack.top());
    return 0;
}

注意在一开始要开一个大数组来装根结点，不能在函数体内声明，不然会把原来的根结点的地址覆盖了。用这种方法可以实现将后缀表达式转化为前缀表达式和中缀表达式，但是会输出多余的括号。
二叉查找树
对于树中的每个结点，它的左子树的所有结点的值小于它的值，右子树的所有结点的值大于它的值，则称此树为二叉查找树，易知中序遍历一棵二叉查找树即为升序输出它的结点值。
这样说默认了树的结点是两两互异且可比较的。
具体实现：插入，查找，中序遍历，返回最大/最小结点

#include <iostream>
using namespace std;
struct Tree {
    int data;
    Tree *pleft;
    Tree *pright;
};
Tree* search(Tree *proot,int x){
    if(!proot||proot->data==x) return proot;
    if(proot->data<x) return search(proot->pright,x);
    return search(proot->pleft,x);
}
void insert(Tree *&proot, int x) { //在树中插入值为x的结点：先查找它，若没有，插入到最后访问的结点处
    if (proot == nullptr) {
        proot = new Tree;
        proot->pleft = proot->pright = nullptr;
        proot->data = x;
        return;
    }
    if (x < proot->data) insert(proot->pleft, x);
    else insert(proot->pright, x);
}
Tree* CreatTree(){
    Tree* proot=nullptr;
    int data;
    while(cin>>data) insert(proot,data);
    return proot;
}
bool find(Tree* proot, int x) {  //查找树中是否有值为x的结点
    if (proot == nullptr) return false;
    if (proot->data == x) return true;
    else if (proot->data > x) return find(proot->pleft, x);
    else return find(proot->pright, x);
}

void midtravel(Tree *proot) {
    if (proot == nullptr) return;
    midtravel(proot->pleft);
    cout << proot->data << ' ';
    midtravel(proot->pright);
}

Tree* mindata(Tree *proot) {//返回最小结点（最左边的子结点）
    if(!proot) return nullptr;
    while(proot->pleft) proot=proot->pleft;
    return proot;
}

Tree* maxdata(Tree *proot) {//返回最大结点（最右边的子结点）
    if(!proot) return nullptr;
    while(proot->pright) proot=proot->pright;
    return proot;
}

int main() {
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    Tree *proot = CreatTree();
    midtravel(proot);
    cout << endl;
    cout << (*maxdata(proot)).data << endl;
    cout << (*mindata(proot)).data;
    return 0;
}

删除操作比较麻烦：
若删除的是叶子结点，直接删就行；如果删除的结点只有左子树或者右子树，直接让该结点的左儿子或者右儿子取代它的位置即可；若删除的结点既有左子树又有右子树，用其右子树的最小结点的值取代它，再递归删除右子树的最小结点（它一定没有左子树）。

void remove(Tree * &proot,int x) { //删除值为x的结点，这里指针一定要加上引用 
    if (proot == nullptr) return;
    if (x < proot->data) remove(proot->pleft, x);
    else if (x > proot->data) remove(proot->pright, x);
    else if (proot->pleft != nullptr && proot->pright != nullptr) {
        proot->data = mindata(proot->pright)->data;
        remove(proot->pright, proot->data);
    }
    else {//如果只有左子树或者只有右子树，就用子结点取代父节点
        Tree *oldnode = proot;
        if (proot->pleft != nullptr) proot = proot->pleft;
        else proot = proot->pright; //如果在函数头不加引用，函数调用结束后proot根本没变
        delete oldnode;
    }
}

二叉查找树的平均运行时间为，最坏运行时间为。

4.AVL树、伸展树、B树（先欠着）

5.set和map

pair
定义在#include<utility>中的类模板，用于将两种数据类型捆绑，使它们可以互相索引，或者当函数需要返回两个值时，也可以用pair。
pair<T1,T2> p;
pair是个结构体，有两个成员first和second，分别代表了T1的具体变量和T2的具体变量。
pair重载了小于运算符，遵循字典序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。（仅当p1的每个分量都>=p2时，称p1>=p2，否则p1<p2）
set和map
要使用set，必须重载小于运算符，而且小于函数后面必须加上const。
insert(s.end(),x)的速度快于insert(x)。
erase(x),erase(it),erase(begin(),end()) 分别返回删掉的元素个数（0或1），删掉的迭代器的下一个迭代器，end()。
map和set的查找方法find()的返回值是对象的迭代器，如果找不到，则返回end()。
map和set操作的时间复杂度：
先进二叉树再中序遍历的排序算法的时间复杂度：