数据结构-树和森林

树

树的存储

树的顺序存储-双亲表示法

//双亲表示法是使用一组连续的空间来存储每个结点，同时每个结点增设一个伪指针为数组下标，表示其父亲的位置
#define MaxSize 100  //树中最多结点数

typedef struct{    //树的结点定义
    ElemType data;  //数据元素
    int parent; //双亲位置，数组下标，父亲唯一，所有该值唯一
}PTNode;

typedef struct{
    PTNode nodes[MaxSize];  //存储所有的结点，相当于树的顺序存储
    int n;  //结点数
}PTree;

树的链式存储-孩子表示法

//孩子表示法，将所有结点存入数组内。这种方法寻找双亲需要遍历所有结点。每个结点含有的1个指向
typedef struct CNode{
    int index;  //该孩子在结点表中的数组下标
    CNode *nextchild;  //指向下一个孩子
}CNode;
typedef struct{
    ElemType data;  //数据域
    CNode *child;   //指向其第一个孩子
}CMNode;
typedef struct{
    CMNode nodes[MaxSize];  //结点表数组
    int count;  //结点数量
}CTree;

树的链式存储-孩子兄弟表示法

//孩子兄弟表示法，只包括3个数据：1.数据域；2.指向该结点的第一个结点；3.指向与该结点同层兄弟结点
typedef struct CSNode{
    ElemType data;  //数据域
    CSNode *firstchild,*nextsibling;    //第一个孩子和下一个兄弟（可以便于层次搜索）
}CSNode,*CSTree;

树的应用

树的应用-并查集

并查集的存储-数据结构

//并查集只是一个数组，正数则表示其为子结点，正数为其父亲数组下标，负数则表示其为父结点，负数绝对值表示其结点总数(包括父节点本身)
#define MaxSize 100
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
}UFSets;

并查集的初始化

//初始化
UFSets *InitialUFSets(){
    UFSets *s = (UFSets*)malloc(sizeof(UFSets));
    for(int i=0;i<MaxSize;i++){
        s->data[i]=-1;
    }
    return s;
}

并查集的查找

//查找并查集S中返回数组下标index的树根的数组下标
int Find(UFSets s,int index){
    while(s.data[index]>=0){
        index = s.data[index];
    }
    return index;
}

并查集的合并

//求两个不想交子集合的并集(即合并root1与root2，让root2成为root1的子树),要求root1与root2不同
void Union(UFSets s,int root1,int root2){
    s.data[root2] = root1;  //将root2链接在root1下
}

赏

谢谢你请我吃糖果

支付宝

微信