通常用树（森林）的双亲表示作为并査集的存储结构，每个子集合以一棵树表示。
所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。
通常用数组元素的下标代表元素名，根结点的下标代表子集合名，根结点的双亲结点为负数。

例如，若设有一个全集合为 S={0,1,3,4,5,6,7,8,9}，初始化时每个元素自成一个单元素 |
子集合，每个子集合的数组值为 -1，如图 4-17 所示。

经过一段时间的计算，这些子集合合并成 3 个更大的子集合：(S_1={0,8})、(S_2={1,9})、(S_3={2,5})，此时并査集的树形表示和存储结构如图 4-18 所示。

为了得到两个子集合的并，只要将其中一个子集合根结点的双亲指针指向另一个集合的根结点即可。
因此，(S_1 cup S_2) 可以具有如图 4-19 所示的表示。
在采用树的双亲指针数组表示作为并査集的存储表示时，集合元素的编号从 0 到 size-1。
其中 size 是最大元素的个数。下面是并査集主要运算的实现。

并査集的结构定义如下：

#define SIZE 100
int UFSets[SIZE]; //集合元素数组（双亲指针数组）

并查集的初始化操作（S 即为并査集）。

void Initial(int S[]) {
    for(int i=0; i<size; i++) //每个自成单元素集合
        S[i] = -1;
}

Find 操作（函数在并査集 S 中査找并返回包含元素 x 的树的根）。

int Find(int S[],int x){
    while(S[x]>=0) //循环寻找 x 的根
        x=S[x];
    return x; //根的 s[]小于 0
}

Union 操作（函数求两个不相交子集合的并集）。

void Union(int S[],int Root1,int Root2) {
//要求 Rootl 与 Root2 是不同的， 且表示子集合的名字
    S[Root2] = Root1; //将根 Root2 连接到另一根 Rootl 下面
}

4.5 树与二叉树的应用

4.5.1 二叉排序树

（1）二叉排序树的定义

二叉排序树（简称 BST），也称为二叉査找树。
二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树：

1. 若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。
2. 若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值。
3. 左、右子树本身也分别是一棵二叉排序树。

由此定义可知，二叉排序树是一个递归的数据结构，可以方便地使用递归算法对二叉排序树进行各种运算。
图 4-20 所示为一棵二叉排序树。
根据二叉排序树的定义，有 左子树结点值 < 根结点值 < 右子树结点值，所以，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。
例如，图 4-20 的二叉排序树的中序遍历序列为 123468。

（2）二叉排序树的查找

二叉排序树的査找是从根结点开始，沿某一个分支逐层向下进行比较的过程。
若二叉排序树非空，将给定值与根结点的关键字比较，若相等，则査找成功；若不等,则当根结点的关键字大于给定关键字值时，在根结点的左子树中査找，否则在根结点的右子树中査找。
这显然是一个递归的过程。

二叉排序树的非递归査找算法：

BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p) {
//査找函数返回&向关键字值为 key 的结点指针，若不存在，返回 NULL
    p = NULL; //p 指向被査找结点的双亲，用于插入和删除操作中
    while(T!=NULL && key!=T->data) {
        p = T;
        if(key<T->data)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

例如，在图 4-20 中査找值为 4 的结点。
首先 4 与根结点 6 比较。
因为 4 小于 6,所以在根结点 6 的左子树中继续査找。
因为 4 大于 2,所以在结点 2 的右子树中査找，査找成功。

同样，二叉排序树的査找也可以用递归算法实现，递归算法比较简单，但执行效率较低。
具体的实现，留给读者思考。

（3）二叉排序树的插入

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!