二叉搜索树 / set入门

2016年6月12日4,5790

仅列出纲要

二叉树

结点，叶结点，分支结点，结点的度

左右孩子

树的深度，大小

二叉树类型

满二叉树

完全二叉树

平衡二叉树

二叉搜索树

性质

1.前驱后继

2.如何查找？

构建

1.对已经排序的数快速构建二叉搜索树

2.如何顺序插入？

效率讨论

STL-set

顾名思义的操作

什么是Iterator？

如何遍历set？

用法示例

#include<set>
#include<cmath>
#include<iostream>
using namespace std;
set<int>st;//定义
int main()
{
    cout<<st.count(1)<<endl;//输出0
    st.insert(1);
    cout<<st.count(1)<<endl;//输出1

    cout<<st.empty()<<endl;//输出false
    st.clear();//清空
    cout<<st.empty()<<endl;//输出true

    //begin() end() bound()返回的是迭代器
    
    st.insert(1);
    st.insert(2);
    cout<<*st.begin()<<endl;//输出1
    cout<<*--st.end()<<endl;//输出2
    cout<<st.size()<<endl;//输出2

    cout<<*st.lower_bound(1)<<endl;//输出1
    cout<<*st.upper_bound(1)<<endl;//输出2

    for(set<int>::iterator i=st.begin();i!=st.end();i++)
        cout<<*i;//输出12
    cout<<endl;
    return 0;
}

#include<set>

#include<cmath>

#include<iostream>

using namespace std;

set<int>st;//定义

int main()

{

cout<<st.count(1)<<endl;//输出0

st.insert(1);

cout<<st.count(1)<<endl;//输出1

cout<<st.empty()<<endl;//输出false

st.clear();//清空

cout<<st.empty()<<endl;//输出true

//begin() end() bound()返回的是迭代器

st.insert(1);

st.insert(2);

cout<<*st.begin()<<endl;//输出1

cout<<*--st.end()<<endl;//输出2

cout<<st.size()<<endl;//输出2

cout<<*st.lower_bound(1)<<endl;//输出1

cout<<*st.upper_bound(1)<<endl;//输出2

for(set<int>::iterator i=st.begin();i!=st.end();i++)

cout<<*i;//输出12

cout<<endl;

return 0;

}

替罪羊树

阅读http://pan.baidu.com/share/link?shareid=318543&uk=235772034

我一直在想，明显应该拿替罪羊树做平衡树入门？

实现参见http://hzwer.com/8016.html

« 「CODEVS1230」元素查找「BZOJ1208」[HNOI2004] 宠物收养所 »

hzwer.com _ Home | http://hzwer.com

二叉搜索树 / set入门

分类目录

热门文章

Myfriends

近期评论