|
"数据结构并不能直接解决问题，但是数据结构是算法不可缺少的一部分。数据结构能把杂乱无章的数据有序组织起来，易于编程处理。“
一、并查集
并查集是一种用于处理不相交集合合并问题的一类数据结构，主要操作包含：初始化、查找、合并、统计等步骤。典型例题就是”朋友“问题。
合并：确定朋友关系后合并形成新的集
查找：通过递归查找根结点以便合并
根结点：根结点是一个集合的代表，将根结点并入另一个集也就代表将整个集合并入了一个新的集
例：1，2属于朋友、1，3也属于朋友，那么他们都属于同一派系。处理这类问题首先要初始化：
如果第一个朋友关系为（1，2） 则将1并入集2，根结点的值要改变，即s[1]=2
接下来的朋友关系为（1，3），首先要用递归查找第一个集合的根结点，也就是s[2]==2 将其并入新的集合则使得根结点s[2]=3 那么朋友（1，2，3）就形成了以s[3]==3为根结点新的集合
这样 hdu 1213就比较容易理解了
：：将相同派系的人划分为一个桌子，求n个人需要多少张桌子
首先要构建查找和合并函数，查找是为了寻找根结点来进行合并的，用到了递归的知识。
int chazhao(int x)
{ return s[x]==x?x:chaozhao(s[x]);}
合并主要是先查找到前一个集合的根结点，并且改变其的值
void hebing(int x,int y)
{ x=chazhao(x);
y=chazhao(y);
if(x!=y) s[x]=s[y];}
要求多少个桌子只要求得有多少根结点就可以了（根结点是一个集合的代表，根结点满足初始化式子s[i]==i）,在主函数中构造循环即可求解
int num=0;
for(i=1;i<=n;i++)
{ if(s[i]==i) num++;}
cout<<num<<endl;
将代码整合并添加一些细节就可以完成此题了，但是这种代码搜索深度都是树的深度，复杂度较大，性能较差。当出现某种树极深的题时，还有对查找和合并函数的优化方法。
1.查找优化
上述查找程序中查找根结点后返回的是根结点，如果在返回时把i所属的集改为根结点，通过这种路径优化的方法可以减少复杂度。
int chazhao(int x)
{ if(x!=s[x]) s[x]=chazhao(s[x]);
return s[x];}
通过代码可以将集合的每个结点变为根结点，下次再搜在0（1）时间内就可得到结果，产生的以下表格就与普通方法（1，2，3）朋友的集合有些不同
如果担心数据规模过大出现爆栈情况则可以用非递归查找方法
int chazhao(int x)
{ int r=x;
while(s[r]!=r) r=s[r];
int i=x,j;
while(i!=r){
j=s[i];
s[i]=r;
i=j;}
return r;}
2.合并优化
合并优化将一个根结点的集改为另一个根结点，用到了比较树的高度的知识。首先要在初始化的时候初始每个集合树的高度为0。然后在相同高度的树的合并后使树的高度+1，非相同高度的树将矮树并到高树上。
void hebing(int x,int y)
{ x=chazhao(x);
y=chazhao(y);
if(height[x]==height[y]){
height[x]=height[x]+1;
s[y]=x;}
else{ if(height[x]<height[y]) s[x]=y;
else s[y]=x;
} }
这两天看的不太多，二叉树还没有看完，先开个头吧。
二、二叉树
二叉树的每个结点最多有两个子结点（左孩子，右孩子）
… … … 1
… … .2 … 3
… …4 5…6 7
二叉树的第i层最多有2的n-1次方个结点，如果每一层结点都是满的则称为满二叉树，如果二叉树编号只在最后一层有缺失则成为完全二叉树
二叉树通过指针来实现，通过指针指向左右不同结点
struct node{
int value;
node *l, *r;
};
1、二叉树的遍历
运用上面的编号1-7形成的二叉树作例子
（1） 宽度优先遍历
即所说的bfs，比较适合用队列搜索，顺序访问为1234567
（2） 深度优先遍历
即所说的dfs，分为先序遍历、中序遍历、后序遍历三种顺序。
先序遍历：正常的dfs访问顺序 1245367
中序遍历：按左儿子、父结点、右儿子的顺序访问 即 4251637
后序遍历：按左儿子、右儿子、父结点的顺序访问 即 4526731
已知某二叉树的三种遍历，中序遍历+先序遍历或中序遍历+后续遍历都可以确定整棵树。
|