用c语言写一个程序,假设二叉树采用二叉链存储结构,二叉树中结点值为单个字符且所有结点值不相同。设计二叉树的基本运算程序,包括创建二叉链,输出二叉树,求二叉树的高度,求结点数和叶子结点数;并用相关数据进行测试
时间: 2023-05-14 15:05:22 浏览: 109
以下是用C语言实现二叉树的基本运算程序的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
char data; // 结点值
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') { // 如果输入的是#,表示该结点为空
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode)); // 创建新结点
node->data = ch;
node->left = createTree(); // 递归创建左子树
node->right = createTree(); // 递归创建右子树
return node;
}
// 输出二叉树(中序遍历)
void printTree(TreeNode *root) {
if (root == NULL) {
return;
}
printTree(root->left);
printf("%c ", root->data);
printTree(root->right);
}
// 求二叉树的高度
int getHeight(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 求二叉树的结点数
int getNodeCount(TreeNode *root) {
if (root == NULL) {
return 0;
}
return getNodeCount(root->left) + getNodeCount(root->right) + 1;
}
// 求二叉树的叶子结点数
int getLeafCount(TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return getLeafCount(root->left) + getLeafCount(root->right);
}
int main() {
printf("请输入二叉树(用#表示空结点):\n");
TreeNode *root = createTree();
printf("中序遍历二叉树:");
printTree(root);
printf("\n二叉树的高度:%d\n", getHeight(root));
printf("二叉树的结点数:%d\n", getNodeCount(root));
printf("二叉树的叶子结点数:%d\n", getLeafCount(root));
return 0;
}
```
你可以将上述代码保存为一个名为`binary_tree.c`的文件,然后在命令行中使用以下命令编译并运行:
```
gcc binary_tree.c -o binary_tree
./binary_tree
```
接下来,你可以输入一个二叉树的结构,例如:
```
AB#C##DE#G##F###
```
程序将会输出中序遍历二叉树,以及二叉树的高度、结点数和叶子结点数。
阅读全文