请用C语言设计并验证如下算法:输入一颗二叉树的广义表形式,建立该二叉树的二叉链表结构,并求其结点数目。
时间: 2023-06-26 14:04:17 浏览: 229
以下是一种可能的实现方式:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char data;
struct Node* left;
struct Node* right;
} Node;
// 递归构建二叉树
Node* buildTree(char* str, int* pos) {
if (str[*pos] == '\0' || str[*pos] == ')') {
return NULL;
}
else {
Node* node = (Node*)malloc(sizeof(Node));
node->data = str[*pos];
(*pos)++;
node->left = buildTree(str, pos);
(*pos)++;
node->right = buildTree(str, pos);
return node;
}
}
// 递归计算结点数目
int countNodes(Node* root) {
if (root == NULL) {
return 0;
}
else {
return 1 + countNodes(root->left) + countNodes(root->right);
}
}
int main() {
char str[100];
printf("请输入二叉树的广义表形式:");
scanf("%s", str);
int pos = 0;
Node* root = buildTree(str, &pos);
int count = countNodes(root);
printf("该二叉树的结点数目为:%d\n", count);
return 0;
}
```
使用示例:
```
请输入二叉树的广义表形式:A(B(C,D),E(,F))
该二叉树的结点数目为:6
```
解释:
输入的广义表为 A(B(C,D),E(,F)),表示如下二叉树:
```
A
/ \
B E
/ / \
C * F
\
D
```
其中 * 表示空结点。程序输出的结点数目为 6,与实际结点数目相符。
阅读全文