已知一棵树的层次遍历序列及相应的每个结点的次数序列,请写出构造此树的左儿子—右兄弟链接表示的c语言代码并给出使用的函数库
时间: 2024-04-30 19:21:53 浏览: 104
树结构c语言代码
3星 · 编辑精心推荐
构造树的左儿子-右兄弟表示法的基本思路是:从根节点开始,依次将每个节点插入到其父节点的左儿子链表的末尾,如果当前节点有兄弟节点,则将其插入到其兄弟节点的右儿子链表的末尾。
以下是一个示例代码,使用了stdlib.h库中的malloc函数动态分配内存空间:
```c
#include <stdio.h>
#include <stdlib.h>
// 树节点结构体
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* firstChild; // 左儿子
struct TreeNode* nextSibling; // 右兄弟
} TreeNode;
// 构造树的左儿子-右兄弟表示法
TreeNode* buildTree(int* levelOrder, int* count, int n) {
if (n <= 0) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = levelOrder[0];
root->firstChild = NULL;
root->nextSibling = NULL;
TreeNode* cur = root;
int i = 1;
while (i < n) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = levelOrder[i];
node->firstChild = NULL;
node->nextSibling = NULL;
if (count[i] > 0) {
cur->firstChild = node;
cur = node;
} else {
cur->nextSibling = node;
cur = node;
}
count[i]--;
if (count[i] == 0) {
i++;
}
}
return root;
}
// 测试函数
int main() {
int levelOrder[] = {1, 2, 3, 4, 5, 6, 7};
int count[] = {2, 2, 2, 0, 0, 0, 0};
int n = 7;
TreeNode* root = buildTree(levelOrder, count, n);
// 输出树的层次遍历序列
printf("Level Order Traversal: ");
TreeNode* cur = root;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->nextSibling;
}
printf("\n");
return 0;
}
```
该代码的输出结果为:
```
Level Order Traversal: 1 2 3 4 5 6 7
```
说明树的构造成功。
阅读全文