用c语言创建一个二叉树并用广义表的形式打印
时间: 2023-12-26 18:54:54 浏览: 117
好的,我会回答您的问题。首先,您需要定义一个二叉树的数据结构。这里是一个示例:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
然后,您可以使用递归的方式来创建一个二叉树。下面是一个示例函数,它可以将一个广义表的字符串表示形式转换为一个二叉树:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* parseTree(char* s) {
struct TreeNode* root = NULL;
struct TreeNode** stack = malloc(sizeof(struct TreeNode*) * strlen(s));
int top = -1;
char* p = s;
while (*p != '\0') {
if (*p == '(') {
if (*(p+1) == ')') {
stack[top]->left = NULL;
} else {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = 0;
node->left = NULL;
node->right = NULL;
stack[top]->left = node;
stack[++top] = node;
}
p++;
} else if (*p == ',') {
if (*(p+1) == ')') {
stack[top]->right = NULL;
} else {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = 0;
node->left = NULL;
node->right = NULL;
stack[top]->right = node;
stack[++top] = node;
}
p++;
} else if (*p == ')') {
top--;
p++;
} else {
int num = 0;
while (*p >= '0' && *p <= '9') {
num = num * 10 + (*p - '0');
p++;
}
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = num;
node->left = NULL;
node->right = NULL;
if (root == NULL) {
root = node;
stack[++top] = root;
} else {
if (stack[top]->left == NULL) {
stack[top]->left = node;
stack[++top] = node;
} else {
stack[top]->right = node;
stack[++top] = node;
}
}
}
}
free(stack);
return root;
}
```
您可以使用以下方式调用上述函数:
```
struct TreeNode* root = parseTree("(1,2,3(4,5))");
```
最后,您可以使用递归的方式来打印一个二叉树的广义表形式。下面是一个示例函数:
```
void printTree(struct TreeNode* root) {
if (root == NULL) {
printf("()");
} else {
printf("(%d", root->val);
printTree(root->left);
printTree(root->right);
printf(")");
}
}
```
您可以使用以下方式调用上述函数:
```
printTree(root);
```
希望这可以帮助您!
阅读全文