二叉树基本操作C语言 c语言 定义二叉树的结点结构\n实现先序序列构造二叉树的算法\n实
二叉树基本操作C语言
c语言
定义二叉树的结点结构\n实现先序序列构造二叉树的算法\n实现先序遍历这棵二叉树，输出每个结点的值的算法\n利用先序遍历，统计叶子结点的个数\n利用后序遍历，求二叉树的深度
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新的二叉树节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 先序序列构造二叉树
TreeNode* constructBinaryTree(int* preOrder, int start, int end) {
static int preIndex = 0;
if (start > end) {
return NULL;
}
TreeNode* root = createNode(preOrder[preIndex++]);
if (start == end) {
return root;
}
int i;
for (i = start; i <= end; i++) {
if (preOrder[i] > root->val) {
break;
}
}
root->left = constructBinaryTree(preOrder, preIndex, i - 1);
root->right = constructBinaryTree(preOrder, i, end);
return root;
}
// 先序遍历二叉树
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 统计叶子节点个数
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 maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
int main() {
int preOrder[] = { 4, 2, 1, 3, 6, 5, 7 };
int size = sizeof(preOrder) / sizeof(preOrder[0]);
TreeNode* root = constructBinaryTree(preOrder, 0, size - 1);
printf("先序遍历结果：");
preOrderTraversal(root);
printf("\n");
int leafCount = countLeaves(root);
printf("叶子节点个数：%d\n", leafCount);
int depth = maxDepth(root);
printf("二叉树深度：%d\n", depth);
return 0;
}
