大二博客总结第四周

本周学习内容： 1.了解掌握了二叉树的存储，创建和遍历 2.学会了二叉搜索树（BST），做完了课后习题 3.看懂、学习了简单平衡二叉搜索树——Treap树 4.高精度计算

BST

1.每个元素的键值可以比较大小，将键值存放在BST的结点上 2.键值最大的结点没有右儿子，键值最小的结点没有左儿子 3.最坏的情况下，树的深度为n；最好的情况下，得到的左右子树完全平衡，深度为log2(n). BST的关键在于运用算法努力使它保持平衡

eg：HDU 3999 “The order of a Tree”

#include 

using namespace std;
const int N=100005;
int tree[N],l[N],r[N],a[N];
int root,f,m;               //root(根)的值为0，以tree[0]为根结点
// f的作用是去记录每个值出现的顺序，m是去控制遍历输出的顺序
void buildtree(int root,int x)
{
    if(x>n)
    {
        memset(l,-1,sizeof(l));  //都初始化为-1，方便之后的输出
        memset(r,-1,sizeof(r));
        root=-1;f=0;             //根的值+1后，就没变过
        for(int i=0;i>x;
            if(root==-1)
                tree[++root]=x;  //作为根节点
            else
            {
                tree[++f]=x;
                buildtree(root,x); //tree[0]为中心建树
            }
        }
        m=0;
        order(root);
        for(int i=0;isecond;
            else
            {
                map::iterator it2=it;
                it2--;it++;
                if((g-it2->first)first-g))
                    tmp=it2->second;
                else
                    tmp=it->second;
            }
            cout