1）设计树的孩子链表法存储结构；2）基于该结构设计算法：求下标为i的结点的双亲。

1）树的孩子链表法存储结构是指，将每个结点的孩子结点用一个单链表链接起来，同时在每个结点中记录该结点的第一个孩子结点的指针和该结点的双亲结点的指针。

2）求下标为i的结点的双亲的算法如下：

（1）如果i为根结点，则返回空指针；

（2）从根结点开始遍历树，直到找到下标为i的结点；

（3）返回该结点的双亲结点的指针。

相关问题

设计树的孩子链表法存储结构；2）基于该结构设计算法：求下标为i的结点的双亲。

1）树的孩子链表法存储结构是指，对于每个结点，用一个指针指向它的第一个孩子结点，再用一个指针指向它的下一个兄弟结点。如果一个结点没有孩子结点，则它的孩子指针为空。如果一个结点没有兄弟结点，则它的兄弟指针为空。

2）求下标为i的结点的双亲的算法如下：

（1）从根结点开始遍历树，直到找到下标为i的结点。

（2）在遍历的过程中，记录每个结点的父结点，直到找到下标为i的结点。

（3）返回下标为i的结点的父结点即可。

任务1：1）设计二叉树的二叉链表结构；2）基于该结构设计算法：求二叉树的叶子结点数。 任务2：1）设计树的孩子链表法存储结构；2）基于该结构设计算法：求下标为i的结点的双亲。 任务3：(不需要写代码)对于给定的一组权值 W＝{1, 5, 7, 8, 14, 20, 28} ，画出哈夫曼树并求其WPL。

任务1：
1）二叉树的二叉链表结构定义如下：

typedef struct BiTNode{
char data; // 数据域
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

2）求二叉树的叶子结点数的算法如下：

int countLeaf(BiTree root){
if(root == NULL){
return 0; // 空树没有叶子结点
}else if(root->lchild == NULL && root->rchild == NULL){
return 1; // 叶子结点
}else{
return countLeaf(root->lchild) + countLeaf(root->rchild); // 递归求左右子树的叶子结点数之和
}
}

任务2：
1）树的孩子链表法存储结构定义如下：

typedef struct CTNode{
int child; // 孩子结点在数组中的下标
struct CTNode *next; // 下一个孩子结点指针
}*ChildPtr;

typedef struct{
char data; // 数据域
ChildPtr firstchild; // 第一个孩子结点指针
}CTBox;

typedef struct{
CTBox nodes[MAXSIZE]; // 结点数组
int n, r; // 结点数和根结点在数组中的下标
}CTree;

2）求下标为i的结点的双亲的算法如下：

int getParent(CTree tree, int i){
for(int j = 0; j < tree.n; j++){
ChildPtr p = tree.nodes[j].firstchild;
while(p != NULL){
if(p->child == i){
return j; // 找到双亲结点
}
p = p->next;
}
}
return -1; // 没有找到双亲结点
}

任务3：
哈夫曼树的构建过程如下：
1）将权值从小到大排序，得到序列{1, 5, 7, 8, 14, 20, 28}。
2）将权值最小的两个结点合并，得到新的结点15，其权值为1+5=6，将其插入到序列中，得到{6, 7, 8, 14, 15, 20, 28}。
3）重复步骤2，得到{13, 14, 15, 20, 28}。
4）重复步骤2，得到{27, 28}。
5）最后剩下的两个结点合并，得到新的根结点55，其权值为27+28=55。

哈夫曼树如下所示：

55
/ \
27 28
/ \
13 14
/ \
1 5

WPL = 1*2 + 5*2 + 7*2 + 8*2 + 14*2 + 20*2 + 28*2 = 196。