第六章++树与森林.ppt

第六章树与森林
一、树的定义与术语
定义:一棵树(tree)是由一个或一个以上结点组成的有限集,其中有一个特定的结点R称为T的根结点。集合(T-{R})的其余结点被划分为n个不相交的子集T1、T2、...、Tn,其中每个子集都是树。子集Ti称为树T的子树。
二、树结点的ADT
template<class Elem> class GTNOde{
public:
GTNode(const Elem&);
~GTNode();
Elem value();
bool isLeaf();
GTNode* parent();
GTNode* leftmost_child();
GTNode* right_sibling();
void setValue(Elem&);
void insert_first(GTNode<Elem>* n);
void insert_next(GTNode<Elem>*n);
void remove_first();
void remove_next();
};
template <class ELem> class GenTree{
private:
void printhelp(GTNode*);
public:
GenTree();
~GenTree();
void clear();
GTNode* root();
void newroot(Elem&, GTNode<Elem>*,GTNode<Elem>*);
void print();
};
父指针表示法(并查集(Union Find Sets))
1、UFSets是集合的一种简单而广为应用的表示方法。
2、UFSets表示方法
0
6
7
8
1
4
9
2
3
5
– 4
– 3
– 3
2
1
2
0
0
0
1
0 1 2 3 4 5 6 7 8 9
下标
parent
一个集合表示成树,所有集合表示成森林。
树中每个结点代表集合的一个单元素,下标代表元素名双亲指针指向该集合的另一个元素,树的根结点下标代表集合名。
举例:设集合S1 = {0,6,7,8} S2 = {1,4,9} S3 = {2,3,5} 其并查集树型结构及存贮结构
. . .
. .
.
3、UFSets的并查运算举例
S2合并到S1中
0
6
7
8
1
4
9
下标
parent
0 1 2 3 4 5 6 7 8 9
– 7
– 3
2
1
2
0
0
0
1
0
只修改1号和0号分量的值
搜索(查找)元素4所在的集合
沿 parent 指针去找双亲结点,直到 parent 值为负为止。元素4是在0集合中,返回集合名0。
并查集(Union Find Sets)
class Gentree{
private:
int * array;
int size;
int FIND(int ) const;
public:
Gentree(int);
~Gentree(){delete [] array;}
void UNION(int ,int);
bool differ(int ,int);
};
Gentree::Gentree(int sz){
size=sz;;
array=new int [sz];
for(int i=0; i<sz; i++) array[i]=-1;
}
树的Union Find 算法实现
bool Gentree::differ(int a, int b){
int root1=FIND(a); int root2=FIND(b);
return (root1!=root2);
}
void Gentree::UNION(int a, int b){
int root1=FIND(a); int root2=FIND(b);
if(root1!=root2){
array[root1]+=array[root2]
array[root2]=root1;}
}
int Gentree::FIND(int curr) const{
while(array[curr]>=0) curr=array[curr];
return curr;
}
树的Union Find 算法实现
6、并集的改进算法——以加权规则压缩高度
 n 个单元素集合的 n – 1 次合可能产生一棵退化树
– 1
0 1 2 3 4 5 6 7 8 9
– 1
– 1
– 1
– 1
– 1
– 1
– 1
– 1
– 1