请您使用C语言来帮我实现这样的操作:当我使用scanf函数来输入字符序列,建立二叉树;按先序、中序、后序遍历二叉树(三种递归算法和中序遍历的非递归算法),通过这些步骤来求出二叉树的高度和结点的个数,使得我能得知我输入的字符序列所形成的二叉树的高度和结点的个数
时间: 2024-05-14 17:16:58 浏览: 89
好的,以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct Node {
char data;
struct Node *left;
struct Node *right;
} Node;
// 创建二叉树
void createTree(Node **node) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
*node = NULL;
} else {
*node = (Node *)malloc(sizeof(Node));
(*node)->data = ch;
createTree(&(*node)->left);
createTree(&(*node)->right);
}
}
// 递归前序遍历
void preOrder(Node *node) {
if (node != NULL) {
printf("%c ", node->data);
preOrder(node->left);
preOrder(node->right);
}
}
// 递归中序遍历
void inOrder(Node *node) {
if (node != NULL) {
inOrder(node->left);
printf("%c ", node->data);
inOrder(node->right);
}
}
// 递归后序遍历
void postOrder(Node *node) {
if (node != NULL) {
postOrder(node->left);
postOrder(node->right);
printf("%c ", node->data);
}
}
// 非递归中序遍历
void nonRecursiveInOrder(Node *node) {
Node *stack[100];
int top = -1;
while (node != NULL || top != -1) {
if (node != NULL) {
stack[++top] = node;
node = node->left;
} else {
node = stack[top--];
printf("%c ", node->data);
node = node->right;
}
}
}
// 计算二叉树高度(递归算法)
int getHeight(Node *node) {
if (node == NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 计算二叉树结点个数(递归算法)
int getNodeCount(Node *node) {
if (node == NULL) {
return 0;
}
return getNodeCount(node->left) + getNodeCount(node->right) + 1;
}
int main() {
printf("请输入字符序列,以#代表叶子节点:\n");
Node *root = NULL;
createTree(&root);
printf("\n先序遍历结果为:");
preOrder(root);
printf("\n中序遍历结果为:");
inOrder(root);
printf("\n后序遍历结果为:");
postOrder(root);
printf("\n非递归中序遍历结果为:");
nonRecursiveInOrder(root);
printf("\n该二叉树高度为: %d", getHeight(root));
printf("\n该二叉树结点个数为: %d\n", getNodeCount(root));
return 0;
}
```
请注意,在对输入的字符序列进行建树时,我们使用“#”来代表叶子节点。其中,createTree() 函数为递归实现,preOrder()、inOrder()、postOrder() 函数分别为递归实现的前序、中序、后序遍历函数,nonRecursiveInOrder() 函数为非递归中序遍历函数,getHeight() 函数和getNodeCount() 函数均为递归实现的计算二叉树高度和结点个数的函数。最后,注意在程序中要加入头文件 stdlib.h,以使用 malloc 函数。
阅读全文
相关推荐


















