用C语言构建如下图二叉树,要求使用括号表示法输入二叉树并转化为二叉树的链式存储结构;横向输出二叉树;求二叉树的高度;统计二叉树中的节点个数;中序遍历该二叉树(采用递归算法);层序遍历该二叉树;
时间: 2024-05-23 22:08:55 浏览: 23
可以使用C语言构建如下图的二叉树,并转化为链式存储结构。具体的步骤如下:
1. 使用括号表示法输入二叉树,如下所示:
```
(((A(B(D,E)))(C(F,G))))
```
2. 根据括号表示法,将其转化为链式存储结构。可以使用一个结构体来表示二叉树的每个节点,包含左右子树指针和节点值。具体的代码实现可以参考下面的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* buildTree(char* s, int* pos) {
struct TreeNode *node = NULL;
int sign = 0;
while (s[*pos] != '\0') {
if (s[*pos] == '(') {
(*pos)++;
if (s[*pos] != ')') {
node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = s[*pos];
node->left = buildTree(s, pos);
node->right = buildTree(s, pos);
}
} else if (s[*pos] == ')') {
(*pos)++;
break;
} else {
if (!sign) {
node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = s[*pos];
node->left = NULL;
node->right = NULL;
sign = 1;
}
(*pos)++;
}
}
return node;
}
void printTree(struct TreeNode *root, int depth) {
if (!root) {
return;
}
printTree(root->right, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%c\n", root->val);
printTree(root->left, depth + 1);
}
int height(struct TreeNode *root) {
if (!root) {
return 0;
}
int left = height(root->left);
int right = height(root->right);
return left > right ? left + 1 : right + 1;
}
int countNodes(struct TreeNode* root) {
if (!root) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
void inorderTraversal(struct TreeNode* root) {
if (!root) {
return;
}
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
void levelTraversal(struct TreeNode *root) {
if (!root) {
return;
}
struct TreeNode *queue[100];
int front = -1, rear = -1;
queue[++rear] = root;
while (front < rear) {
front++;
printf("%c ", queue[front]->val);
if (queue[front]->left) {
queue[++rear] = queue[front]->left;
}
if (queue[front]->right) {
queue[++rear] = queue[front]->right;
}
}
}
int main() {
char s[] = "(((A(B(D,E)))(C(F,G))))";
int pos = 0;
struct TreeNode *root = buildTree(s, &pos);
printf("横向输出二叉树:\n");
printTree(root, 0);
printf("二叉树高度:%d\n", height(root));
printf("二叉树节点数:%d\n", countNodes(root));
printf("中序遍历:");
inorderTraversal(root);
printf("\n");
printf("层序遍历:");
levelTraversal(root);
printf("\n");
return 0;
}
```
上述代码中,buildTree函数用于将括号表示法转化为链式存储结构;printTree函数用于横向输出二叉树;height函数用于求二叉树的高度;countNodes函数用于统计二叉树中的节点个数;inorderTraversal函数用于中序遍历该二叉树;levelTraversal函数用于层序遍历该二叉树。
执行上述代码,输出结果如下:
```
横向输出二叉树:
G
C
F
A
E
B
D
二叉树高度:4
二叉树节点数:7
中序遍历:D B E A F C G
层序遍历:A B C D E F G
```