设树结点的元素类型为char,用c语言实现以下二叉树的各种基本操作的程序: 建立不少于10个结点的二叉树T; 用后序遍历方式输出树T的结点; 用层次遍历方式输出树T的结点; 输出树T的深度; 输出树T的叶子结点和非叶子结点; 主函数通过函数调用实现以上各项操作。
时间: 2024-02-18 18:05:07 浏览: 18
以下是基于链表实现的二叉树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结点
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
//创建结点
TreeNode* createNode(char c) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = c;
node->left = NULL;
node->right = NULL;
return node;
}
//建立二叉树
TreeNode* createTree() {
TreeNode* root = createNode('A');
root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');
root->right->left = createNode('F');
root->right->right = createNode('G');
root->left->right->left = createNode('H');
root->left->right->right = createNode('I');
return root;
}
//后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->data);
}
//层次遍历
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[100];
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 depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
//输出叶子结点和非叶子结点
void printLeavesAndNonLeaves(TreeNode* root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%c 是叶子结点\n", root->data);
} else {
printf("%c 是非叶子结点\n", root->data);
}
printLeavesAndNonLeaves(root->left);
printLeavesAndNonLeaves(root->right);
}
int main() {
TreeNode* root = createTree();
printf("后序遍历结果为:");
postOrder(root);
printf("\n层次遍历结果为:");
levelOrder(root);
printf("\n树的深度为:%d\n", depth(root));
printLeavesAndNonLeaves(root);
return 0;
}
```
以上代码中,我们先定义了一个二叉树结点的结构体,包含了元素值、左右子结点指针。然后我们使用 `createNode()` 函数创建结点,并通过 `createTree()` 函数构建了一棵二叉树。接着,我们实现了后序遍历、层次遍历、求树深度和输出叶子结点和非叶子结点的函数。在主函数中,我们调用这些函数来实现各种操作。