二叉树的表达及链式二叉树

二叉树是一种树形结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的链式存储是指使用指针来表示二叉树的存储方式。每个节点包含三个部分：数据域、左子节点指针和右子节点指针。如果一个节点没有左子节点或右子节点，则对应指针为空。

在C语言中，可以使用结构体来表示二叉树的节点，如下所示：

struct TreeNode {
    int val; // 数据域
    struct TreeNode *left; // 左子节点指针
    struct TreeNode *right; // 右子节点指针
};

二叉树的链式存储可以通过递归的方式来实现建立、遍历、计算深度、结点数、叶子数等基本操作。下面是一个示例代码，用于先序创建二叉树，并计算二叉树的高度和叶子个数：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 先序创建二叉树
struct TreeNode* createTree() {
    char c;
    scanf("%c", &c);
    if (c == '#') {
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = c;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 计算二叉树的高度
int getHeight(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 计算二叉树的叶子个数
int getLeafCount(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return getLeafCount(root->left) + getLeafCount(root->right);
}

int main() {
    struct TreeNode *root = createTree();
    printf("Height of the binary tree is: %d\n", getHeight(root));
    printf("Number of leaves in the binary tree is: %d\n", getLeafCount(root));
    return 0;
}