二叉树基本操作演示程序 设计一个与二叉树基本操作相关的演示程序。 要求: (1)创建二叉树。 (2)分别以先序、中序、后序三种遍历访问二叉树。 (3)输出二叉树的叶子结点及叶子结点的个数。 (4)输出二叉树的高度。 (5)C语言编写 (6)按照用户手动输入的二叉树,构建二叉树。
时间: 2023-12-10 07:11:51 浏览: 51
好的,我来帮您解答这个问题。
以下是一个简单的C语言实现的二叉树基本操作演示程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建二叉树
struct TreeNode *createTree() {
struct TreeNode *node;
int value;
printf("请输入一个整数(0表示空结点):");
scanf("%d", &value);
if (value == 0) {
node = NULL;
} else {
node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = createTree();
node->right = createTree();
}
return node;
}
// 先序遍历
void preOrder(struct TreeNode *root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
// 中序遍历
void inOrder(struct TreeNode *root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
// 后序遍历
void postOrder(struct TreeNode *root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
// 计算叶子结点数目
int getLeafNodeCount(struct TreeNode *root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return getLeafNodeCount(root->left) + getLeafNodeCount(root->right);
}
}
// 计算二叉树的高度
int getHeight(struct TreeNode *root) {
if (root == NULL) {
return 0;
} else {
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
}
int main() {
struct TreeNode *root = createTree();
printf("先序遍历:");
preOrder(root);
printf("\n");
printf("中序遍历:");
inOrder(root);
printf("\n");
printf("后序遍历:");
postOrder(root);
printf("\n");
printf("叶子结点数目:%d\n", getLeafNodeCount(root));
printf("二叉树的高度:%d\n", getHeight(root));
return 0;
}
```
在程序中,通过 `createTree()` 函数手动输入二叉树,通过先序、中序、后序遍历输出二叉树结点,通过 `getLeafNodeCount()` 函数输出叶子结点数目,通过 `getHeight()` 函数输出二叉树的高度。