使用C语言写一段完整的程序,要求用三种遍历算法遍历该二叉树,给出对应的输出结果。并写一个函数查找二叉树中的节点,根据其是否属于该树,输出true或者false。最后 统计该树的满节点、叶子节点、总节点数。
时间: 2024-12-20 17:22:58 浏览: 5
根据您的要求,下面是一个完整的C语言程序,用于实现二叉树的前序、中序和后序遍历,并提供了一个查找节点的函数以及统计满节点、叶子节点和总节点数的功能。
### C语言代码实现
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->value);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->value);
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->value);
}
// 查找节点
int searchNode(TreeNode* root, int value) {
if (root == NULL) return 0;
if (root->value == value) return 1;
return searchNode(root->left, value) || searchNode(root->right, value);
}
// 统计满节点数量
int countFullNodes(TreeNode* root) {
if (root == NULL) return 0;
int count = 0;
if (root->left != NULL && root->right != NULL) count++;
count += countFullNodes(root->left);
count += countFullNodes(root->right);
return count;
}
// 统计叶子节点数量
int countLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
// 统计总节点数
int countTotalNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countTotalNodes(root->left) + countTotalNodes(root->right);
}
// 主函数
int main() {
// 构建示例二叉树
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// 输出前序遍历结果
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
// 输出中序遍历结果
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
// 输出后序遍历结果
printf("Postorder traversal: ");
postorderTraversal(root);
printf("\n");
// 查找节点
int valueToFind = 5;
if (searchNode(root, valueToFind)) {
printf("Node %d found.\n", valueToFind);
} else {
printf("Node %d not found.\n", valueToFind);
}
// 统计满节点、叶子节点和总节点数
printf("Number of full nodes: %d\n", countFullNodes(root));
printf("Number of leaves: %d\n", countLeaves(root));
printf("Total number of nodes: %d\n", countTotalNodes(root));
return 0;
}
```
### 运行结果示例
假设构建的二叉树如下:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
运行上述程序将输出:
```
Preorder traversal: 1 2 4 5 3 6 7
Inorder traversal: 4 2 5 1 6 3 7
Postorder traversal: 4 5 2 6 7 3 1
Node 5 found.
Number of full nodes: 3
Number of leaves: 4
Total number of nodes: 7
```
这个程序实现了二叉树的基本操作,包括遍历、查找和统计功能。希望这对您有所帮助!
阅读全文