关于树和二叉树的部分,还有如下三个知识点,待以后时间更充裕的时候再回头完善。
1 树与等价问题
文字描述
关于等价关系和等价类的定义,在离散数学上的描述有点拗口, 其实在数据结构中,这部分相关的主要是如下三个函数:
示意图
算法分析:
代码实现
//
// Created by lady on 18-12-15.
// #include <stdio.h>
#include <stdlib.h>
#include <string.h> #define MAX_TREE_SIZE 20 typedef char TElemType; /*
* 树的双亲表示法
*
* 以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。
*/
//结点结构
typedef struct PTNode{
//结点的数据域
TElemType data;
//结点的双亲位置域
int parent;
}PTNode;
//树的结构
typedef struct{
//树的结点
PTNode node[MAX_TREE_SIZE];
//树的根的位置
int r;
//树的结点数
int n;
}PTree; static void printMFSet(PTree *S)
{
printf("打印以树的双亲表示法表示的树:\n");
printf("树的结点数: %d\n", S->n);
printf("树的根的位置: %d\n", S->r);
int i = ;
for(i=; i<=S->n; i++)
{
printf("index %d: (data %c, parent %d)\n", i, S->node[i].data, S->node[i].parent);
}
printf("\n");
} //初始化操作, 构造一个由n个子集(每个子集只含单个成员xi)构成的集合S。
static int initialMFSet(PTree *S)
{
printf("构造一个由n个子集(每个子集只含单个成员xi)构成的集合S:\n");
printf("输入n的值:");
char tmp[] = {};
scanf("%d", &S->n);
int i = ;
for(i=; i<S->n; i++)
{
printf("输入第%d个子集的值:", i+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
S->node[i+].data = tmp[];
S->node[i+].parent = -;
}
S->r = ;
printf("\n");
return ;
} /* param1 S: S是已存在的集合
* param2 data: x是S中某个子集的成员
* result: 查找函数,确定S中x所属子集Si
*/
static int findMFSet(PTree *S, TElemType data)
{
int i = ;
int j = ;
int loc = -;
for(i=; i<=S->n; i++){
if(S->node[i].data == data){
loc = i;
break;
}
}
if(loc < ){
printf("数据data:%c在S集合中不存在!\n", data);
return -;
}
for(j=i; S->node[j].parent>; j=S->node[j].parent);
return j;
} //data_i和data_j所在的子集互不相交,
static int mergeMFSet(PTree *S, TElemType data_i, TElemType data_j)
{
int loc_i = -, loc_j = -;
if((loc_i=findMFSet(S, data_i)) < ){
return -;
}
if((loc_j=findMFSet(S, data_j)) < ){
return -;
} if(S->node[loc_i].parent > S->node[loc_j].parent){
//data_i所在子集的数目比data_j所在子集的数目少
S->node[loc_j].parent += S->node[loc_i].parent;
S->node[loc_i].parent = loc_j;
}else{
S->node[loc_i].parent += S->node[loc_j].parent;
S->node[loc_j].parent = loc_i;
}
return ;
} //确定data所在子集,并交data所在index到根路径上所有结点都变成根的孩子结点。
static int fixMFSet(PTree *S, TElemType data)
{
int index = -;
int parent = -;
int t = ;
int k = ;
for(t=; t<=S->n; t++){
if(S->node[t].data == data){
index = t;
break;
}
}
if(index < )
return ;
for(parent=index; S->node[parent].parent>; parent=S->node[parent].parent);
for(k=index; k!=parent; k=t){
t = S->node[k].parent;
S->node[k].parent = parent;
}
} int main(int argc, char *argv[])
{
PTree S;
initialMFSet(&S);
printMFSet(&S); printf("创建等价类:\n");
char tmp[] = {};
TElemType dataI, dataJ;
while(){
memset(tmp, , sizeof(tmp));
printf("输入一对数据,(0,0)表示结束:");
scanf("%s", tmp);
sscanf(tmp, "%c,%c", &dataI, &dataJ);
if(mergeMFSet(&S, dataI, dataJ) < ){
break;
}else{
printMFSet(&S);
}
}
printf("\n"); printf("现开始压缩路径, 输入要压缩的结点值: ");
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
fixMFSet(&S, tmp[]);
printMFSet(&S);
return ;
}
树与等价类
代码运行
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
构造一个由n个子集(每个子集只含单个成员xi)构成的集合S:
输入n的值:9
输入第1个子集的值:1
输入第2个子集的值:2
输入第3个子集的值:3
输入第4个子集的值:4
输入第5个子集的值:5
输入第6个子集的值:6
输入第7个子集的值:7
输入第8个子集的值:8
输入第9个子集的值:9 打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -1)
index 2: (data 2, parent -1)
index 3: (data 3, parent -1)
index 4: (data 4, parent -1)
index 5: (data 5, parent -1)
index 6: (data 6, parent -1)
index 7: (data 7, parent -1)
index 8: (data 8, parent -1)
index 9: (data 9, parent -1) 创建等价类:
输入一对数据,(0,0)表示结束:1,2
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -2)
index 2: (data 2, parent 1)
index 3: (data 3, parent -1)
index 4: (data 4, parent -1)
index 5: (data 5, parent -1)
index 6: (data 6, parent -1)
index 7: (data 7, parent -1)
index 8: (data 8, parent -1)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:3,4
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -2)
index 2: (data 2, parent 1)
index 3: (data 3, parent -2)
index 4: (data 4, parent 3)
index 5: (data 5, parent -1)
index 6: (data 6, parent -1)
index 7: (data 7, parent -1)
index 8: (data 8, parent -1)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:5,6
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -2)
index 2: (data 2, parent 1)
index 3: (data 3, parent -2)
index 4: (data 4, parent 3)
index 5: (data 5, parent -2)
index 6: (data 6, parent 5)
index 7: (data 7, parent -1)
index 8: (data 8, parent -1)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:7,8
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -2)
index 2: (data 2, parent 1)
index 3: (data 3, parent -2)
index 4: (data 4, parent 3)
index 5: (data 5, parent -2)
index 6: (data 6, parent 5)
index 7: (data 7, parent -2)
index 8: (data 8, parent 7)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:1,3
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -4)
index 2: (data 2, parent 1)
index 3: (data 3, parent 1)
index 4: (data 4, parent 3)
index 5: (data 5, parent -2)
index 6: (data 6, parent 5)
index 7: (data 7, parent -2)
index 8: (data 8, parent 7)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:5,7
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -4)
index 2: (data 2, parent 1)
index 3: (data 3, parent 1)
index 4: (data 4, parent 3)
index 5: (data 5, parent -4)
index 6: (data 6, parent 5)
index 7: (data 7, parent 5)
index 8: (data 8, parent 7)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:1,5
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -8)
index 2: (data 2, parent 1)
index 3: (data 3, parent 1)
index 4: (data 4, parent 3)
index 5: (data 5, parent 1)
index 6: (data 6, parent 5)
index 7: (data 7, parent 5)
index 8: (data 8, parent 7)
index 9: (data 9, parent -1) 输入一对数据,(0,0)表示结束:0,0
数据data:0在S集合中不存在! 现开始压缩路径, 输入要压缩的结点值: 8
打印以树的双亲表示法表示的树:
树的结点数: 9
树的根的位置: 0
index 0: (data , parent -1208980472)
index 1: (data 1, parent -8)
index 2: (data 2, parent 1)
index 3: (data 3, parent 1)
index 4: (data 4, parent 3)
index 5: (data 5, parent 1)
index 6: (data 6, parent 5)
index 7: (data 7, parent 1)
index 8: (data 8, parent 1)
index 9: (data 9, parent -1) Process finished with exit code 0
示意图中的例子的代码实现
2 回溯法与树的遍历
3 树的计数