请给出一个可运行的c语言程序，对任意给定的二叉树完成下列操作： (1）根据输入的序列，建立二叉链表存储结构；（2）输出该二叉树的先序、中序、后序遍历结果（递归算法）； （3）先序遍历二叉树(非递归算法）； (4)借助队列实现二叉树的层次遍历； (5）求二叉树的高度； （6）求二叉树叶子结点个数； （7）将二叉链表视为树或森林的孩子兄弟链表，计算其叶子结点个数。
点击复制后，将打开C知道体验页
以下是一个可运行的 C 语言程序，可以完成给定二叉树的各种操作：
复制
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
char c;
scanf("%c", &c);
if (c == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = c;
root->left = createTree();
root->right = createTree();
return root;
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%c ", root->data);
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->data);
}
// 先序遍历（非递归算法）
void preOrderNonRecursive(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[1000];
int top = 0;
stack[top++] = root;
while (top > 0) {
TreeNode* node = stack[--top];
printf("%c ", node->data);
if (node->right != NULL) {
stack[top++] = node->right;
}
if (node->left != NULL) {
stack[top++] = node->left;
}
}
}
// 层次遍历
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
printf("%c ", node->data);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}
// 求树的高度
int getHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 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 getChildSiblingLeafCount(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return getChildSiblingLeafCount(root->left) + getChildSiblingLeafCount(root->right);
}
int main() {
TreeNode* root = createTree();
printf("先序遍历：");
preOrder(root);
printf("\n中序遍历：");
inOrder(root);
printf("\n后序遍历：");
postOrder(root);
printf("\n先序遍历（非递归算法）：");
preOrderNonRecursive(root);
printf("\n层次遍历：");
levelOrder(root);
printf("\n树的高度：%d\n", getHeight(root));
printf("叶子结点个数：%d\n", getLeafCount(root));
printf("孩子兄弟链表的叶子结点个数：%d\n", getChildSiblingLeafCount(root));
return 0;
}
该程序使用递归算法和非递归算法实现了二叉树的先序、中序、后序遍历，以及先序遍历的非递归算法、层次遍历、求树的高度、求叶子结点个数、计算孩子兄弟链表的叶子结点个数等操作。
