9并查集和线序二叉树

并查集和线序二叉树

并查集（树形数据结构）

对（不相交）集合进行合并和查找

树（数组）存储集合，树根存储元素的代表(指向自己)，其余结点存储集合元素（指向上方）

步骤

建立单元素集合
合并元素集合

代码

#include<stdio.h>
#include<stdlib.h>

int uset[100];		//下标代表数据元素，值代表父节点

//size:大小
void makeSet(int size)		//初始化
{
    for(int i=0;i<size;i++)
    {
        uset[i]=i;	//父节点为自己
    }
}

//查找代表的函数
int find(int i)
{
    if(i==uset[i])			//如果找到代表
    {
        return i;			//返回代表的值
	}
    return find(uset[i]);	//根据值找父节点
}

//合并函数
void unite(int x,int y)
{
    int m=find(x);
    int n=find(y);
    if(m==n)	//集合相交
    {
        return;	//就不合并了
    }
    uset[m]=n;	//否则就合并
}

路径压缩代码

从末尾开始，将遍历的结点都变成代表的子节点

#include<stdio.h>
#include<stdlib.h>

int node[100];		//每个结点
int rank[100];		//树的高度

void makeSet(int size)		//初始化
{
    for(int i=0;i<size;i++)
    {
        node[i]=i;	//父节点为自己
        rank[i]=0;	//高度为0
    }
}

int find(int x)
{
    if(x==node[x])
    {
        return x;
    }
    return node[x]=find(node[x]);		//找到后传回代表结点给当前结点
}

void Unite(int x,int y)
{
    x=find(x);		
    y=find(y);
    if(x==y)		
    {
        return;
    }
    
    //比较高度，决定谁是谁的子树（集合与集合之间的合并）
    if(rank[x]<rank[y])		//如果x的高度小于y的高度
    {
        node[x]=y;			//把x变成y的子树
    }
    else
    {
        node[y]=x;			//把y变成x的子树
        if(rank[x]==rank[y])
        {
            rank[x]++;
        }
	}
}

线索二叉树

利用叶子结点的空链域存储中序遍历的结果，左边指向前驱，右边指向后继

特性：线索化过程

新问题：如何区分叶子结点

解决：结点增加左右标志域

孩子：0

线索：1

#include<stdio.h>
#include<stdlib.h>

typedef struct ThreadTree{
    int data;
    struct ThreadTree *left;
    struct ThreadTree *right;
    int left_type,right_type;
}Node;
Node* pre;		//跟随指针
//中序线索化
void inOrderThreadTree(Node* node)
{
    if(node==NULL)
        return;
    inOrderThreadTree(node->left);
    //线索化，先处理前驱结点
    //结点左子树为NULL，设置前驱
    if(node->left==NULL)
    {
        node->left_type=1;
        node->left=pre;
	}
    //结点右子树为NULL，设置前驱的后继
    if(pre!=NULL && pre->right==NULL)
    {
        pre->right_type=1;
        pre->right=node;
    }
    
    pre=node;  	//更新pre
    inOrderThreadTree(node->right);
    
}

void inOrderTraverse(Node* node)
{
    if(node==NULL)
    {
        return;
	}
    
    while(node!=NULL && node->left_type==0)
        node=node->left;
    
    while(node!=NULL)
    {
        node=node->right;
	}
}

发布于 2024-11-10