3.1 二叉树的顺序存储和基本操作实现

3.1.2 写代码：定义顺序存储的二叉树（数组实现，树的结点从数组下标1开始存储）

#define MaxSize 100
typedef TElemType SqBiTree[MaxSize];

3.1.3 基于上述定义，写一个函数 int findFather ( i ) ，返回结点 i 的父节点编号

int FindFather(SqBiTree T, int i){
	if(i%2==0) return T[i/2];
	else return T[(i-1)/2];
}

3.1.4 基于上述定义，写一个函数 int leftChild ( i ) ，返回结点 i 的左孩子编号

int FindLeftChild(SqBiTree T, int i){
	if(T[i*2]) return T[2*i];
	else return -1;
}

3.1.5 基于上述定义，写一个函数 int rightChild ( i ) ，返回结点 i 的右孩子编号

int FindRightChild(SqBiTree T, int i){
	if(T[i*2+1]) return T[2*i+1];
	else return -1;
}

3.1.6 利用上述三个函数，实现先/中/后序遍历

/*前序遍历*/
void preorder(sqbitree T,int i){
    visit(T[i]);/*先访问根节点，再递归访问左子树和右子树*/ 
    if(T[2*i])
        preorder(T,2*i);
    if(T[2*i+1])
        preorder(T,2*i+1);
}

void pretraverse(sqbitree T){
    if(emptybitree(T))
       return;
    else{
        preorder(T,1); /*根节点从0开始存储->从0开始递归*/
    }
}

/*中序遍历二叉树*/ 
void InTraverse(sqbitree T,int e)
{ 
    if(T[2*e]!=null) /* 左子树不空 */
        InTraverse(T,2*e);
    visit(T[e]);
    if(T[2*e+1]!=null) /* 右子树不空 */
        InTraverse(T,2*e+1);
}

void InOrderTraverse(sqbitree T)
{ 
    if(!emptybitree(T)) /* 树不空 */
        InTraverse(T,1);
    else return;
}

/*后序遍历二叉树*/
void lastorder(sqbitree T,int i){
    if(T[2*i])
        lastorder(T,2*i);
    if(T[2*i+1])
        lastorder(T,2*i+1);
    visit(T[i]);
} 

void lasttraverse(sqbitree T){
    if(emptybitree(T))
       return;
    else{
        lastorder(T,1);
    }
}

3.1.7 写代码：定义顺序存储的二叉树（数组实现，树的结点从数组下标0开始存储）

#define MaxSize 100
typedef TElemType SqBiTree[MaxSize];

3.1.8 基于上述定义，写一个函数 int findFather ( i ) ，返回结点 i 的父节点编号

int FindFather(SqBiTree T, int i){
	if(T[(i+1)/2-1]) return T[(i+1)/2-1];
	else return -1;
}

3.1.9 基于上述定义，写一个函数 int leftChild ( i ) ，返回结点 i 的左孩子编号

int FindLeftChild(SqBiTree T, int i){
	if(T[i*2+1]) return T[i*2+1];
	else return -1;
}

3.1.10 基于上述定义，写一个函数 int rightChild ( i ) ，返回结点 i 的右孩子编号

int FindRightChild(SqBiTree T, int i){
	if(T[i*2+2]) return T[2*i+2];
	else return -1;
}

3.1.11 利用上述三个函数，实现先/中/后序遍历

/*前序遍历*/
void preorder(sqbitree T,int i){
    visit(T[i]);/*先访问根节点，再递归访问左子树和右子树*/ 
    if(T[2*i+1])
        preorder(T,2*i+1);
    if(T[2*i+2])
        preorder(T,2*i+2);
}

void pretraverse(sqbitree T){
    if(emptybitree(T))
       return;
    else{
        preorder(T,0); /*根节点从1开始存储->从1开始递归*/
    }
}

/*中序遍历二叉树*/ 
void InTraverse(sqbitree T,int e)
{ 
    if(T[2*e+1]!=null) /* 左子树不空 */
        InTraverse(T,2*e+1);
    visit(T[e]);
    if(T[2*e+2]!=null) /* 右子树不空 */
        InTraverse(T,2*e+2);
}

void InOrderTraverse(sqbitree T)
{ 
    if(!emptybitree(T)) /* 树不空 */
        InTraverse(T,0);
    else return;
}

/*后序遍历二叉树*/
void lastorder(sqbitree T,int i){
    if(T[2*i+1])
        lastorder(T,2*i+1);
    if(T[2*i+2])
        lastorder(T,2*i+2);
    visit(T[i]);
} 

void lasttraverse(sqbitree T){
    if(emptybitree(T))
       return;
    else{
        lastorder(T,0);
    }
}

3.3 树（森林）的定义和画图

3.3.1 写代码：使用“双亲表示法”，定义顺序存储的树（以及森林）

#define MAXSIZE 100
 
typedef struct PNode{
    int value;     //该结点的值
    int parent;    //伪指针，用于指向双亲结点（双亲结点的数组下标）
}PNode;
 
typedef struct PTree{
    PNode node[MAXSIZE];    //申明一片PNode类型个数为MAXSIZE的数组用于存储树
    int n;                  //表示该树中的结点个数
}PTree;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BI6hZAGV-1678345881826)(null)]

3.3.2 写代码：使用“孩子表示法”，定义链式存储的树（以及森林）

typedef struct CTNode{    //链式存储，存放该结点的每个孩子结点的信息（非孩子结点的数据）
    int child;            //该结点的孩子结点在数组中的下标
    struct CTNode *next;  //指向该孩子结点的下个孩子结点
}CTNode;
 
typedef struct CTBox{     //定义具体结点，存放结点数据，并且存放该元素的第一个孩子结点
    int data;
    CTNode *firstChild;
}CTBox;
 
typedef struct CTree{     //顺序存储结点
    CTBox nodes[MAXSIZE]; //定义一个CTBox类型长度为MAXSIZE的数组
    int n, r;             //n为结点的总个数，r为根节点的数组下标
}CTree;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uk78SFda-1678345875567)(null)]

3.3.3 写代码：使用“孩子兄弟表示法”，定义链式存储的树（以及森林）（涉及树和森林的相互转换）

typedef struct CSNode {
    int value;    //结点数据
    struct CSNode *firstChild, *nextChild;
}CSNode, *CSTree;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ui1xUK7q-1678345881794)(null)]

3.5 并查集的应用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pUkYZYB8-1678345875542)(null)]

3.5.1 写代码：定义一个并查集（用长度为n的数组实现）

#define SIZE 13
int UFSets[SIZE];

//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++){
		S[i]=-1;
	}
} 

3.5.2 基于上述定义，实现并查集的基本操作—— 并 Union

//Union 并操作，将两个集合合并为一个
void Union(int S[], int Root1, int Root2){
	if(Root1==Root2) return; //要求两个根属于不同的集合（不是同一棵树）
	S[Root2]=Root1; //Root2的父节点是Root1 
}  //时间复杂度为O(1)

3.5.3 基于上述定义，实现并查集的基本操作—— 查 Find

//Find 查操作，找x所属集合（返回x所属根节点的下标）
int Find(int S[], int x){
	while(S[x]>=0) //循环寻找根 
		x=S[x];
	return x; //最坏时间复杂度为O(n) 
}