已知一棵树的层次遍历序列及相应的每个结点的次数序列,请用C语言写出构造此树的左儿子—右兄弟链接表示的算法。
时间: 2024-03-24 13:36:43 浏览: 68
以下是构造左儿子-右兄弟表示法的C语言算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
typedef struct Node {
int val;
struct Node *lchild;
struct Node *rchild;
} Node;
Node *createTree(int layer[], int count[], int index, int n) {
if (index >= n) {
return NULL;
}
Node *node = (Node *) malloc(sizeof(Node));
node->val = layer[index];
node->lchild = NULL;
node->rchild = NULL;
int i;
for (i = index + 1; i < n; i++) {
if (count[i] > count[index]) {
node->lchild = createTree(layer, count, i, n);
break;
} else if (count[i] == count[index]) {
node->rchild = createTree(layer, count, i, n);
}
}
return node;
}
void printTree(Node *root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
printTree(root->lchild);
printTree(root->rchild);
}
int main() {
int n;
int layer[MAX_N];
int count[MAX_N];
printf("请输入结点个数:");
scanf("%d", &n);
printf("请输入每层结点的值和出现次数:\n");
for (int i = 0; i < n; i++) {
scanf("%d%d", &layer[i], &count[i]);
}
Node *root = createTree(layer, count, 0, n);
printf("左儿子-右兄弟表示法:");
printTree(root);
return 0;
}
```
该算法的主要思想是根据层次遍历序列和结点次数序列递归地构造树。具体步骤如下:
1. 从根节点开始,依次读入每个结点的值和出现次数。
2. 对于当前结点,按照层次遍历的顺序,逐个遍历其后继结点,找到第一个出现次数大于当前结点的结点,将其作为当前结点的左儿子。
3. 对于后继结点出现次数与当前结点相同的结点,将其依次作为当前结点的右兄弟。
4. 递归地重复以上步骤,构造出整棵树。
最后,输出左儿子-右兄弟表示法即可。
阅读全文