用C语言写一个程序,需有输入二叉树能以先序、中序、后序遍历,还能输出每一个叶子节点和计算出深度并且判断是否为满树
时间: 2024-05-25 13:17:35 浏览: 2
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序遍历
void preOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 中序遍历
void inOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
printf("%c ", root->data);
inOrderTraversal(root->right);
}
// 后序遍历
void postOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%c ", root->data);
}
// 输出叶子节点
void printLeaves(TreeNode *root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%c ", root->data);
}
printLeaves(root->left);
printLeaves(root->right);
}
// 计算深度
int depth(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
// 判断是否为满树
int isFullTree(TreeNode *root) {
if (root == NULL) {
return 1;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
if (root->left != NULL && root->right != NULL) {
return isFullTree(root->left) && isFullTree(root->right);
}
return 0;
}
// 创建二叉树
TreeNode *createTree(char arr[], int size, int index) {
if (index >= size || arr[index] == '#') {
return NULL;
}
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = arr[index];
node->left = createTree(arr, size, index * 2 + 1);
node->right = createTree(arr, size, index * 2 + 2);
return node;
}
int main() {
char arr[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', '#', 'H', '#', '#', 'I', '#', '#', '#', '#', '#', '#'};
int size = sizeof(arr) / sizeof(char);
TreeNode *root = createTree(arr, size, 0);
printf("先序遍历:");
preOrderTraversal(root);
printf("\n");
printf("中序遍历:");
inOrderTraversal(root);
printf("\n");
printf("后序遍历:");
postOrderTraversal(root);
printf("\n");
printf("叶子节点:");
printLeaves(root);
printf("\n");
printf("深度:%d\n", depth(root));
if (isFullTree(root)) {
printf("是满树\n");
} else {
printf("不是满树\n");
}
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)