二叉树基本操作C语言 c语言定义二叉树的结点结构\n实现先序序列构造二叉树的算法\n实现先序遍历这棵二叉树，输出每个结点的值的算法\n利用先序遍历，统计叶子结点的个数\n利用后序遍历，求二叉树的深度

蔚落 2024-02-19 11:07 36阅读 0赞

二叉树基本操作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;