用C语言实现二叉树的链式存储和基本操作

二叉树是一种非常重要的数据结构，它可以用链式存储和顺序存储两种方式实现。链式存储是指用指针来表示二叉树的结构，而顺序存储则是用数组来表示二叉树的结构。在C语言中，我们通常使用链式存储来实现二叉树。

二叉树的基本操作包括建立、遍历、计算深度、结点数、叶子数等。其中，建立二叉树可以使用前序遍历或中序遍历或后序遍历的方式来实现。下面是用前序遍历的方式来创建二叉树的代码：

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *pTreeNode;

pTreeNode createTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }
    pTreeNode root = (pTreeNode)malloc(sizeof(TreeNode));
    root->data = ch;
    root->left = createTree();
    root->right = createTree();
    return root;
}

遍历二叉树有三种方式：前序遍历、中序遍历和后序遍历。下面是三种遍历方式的代码：

void preOrder(pTreeNode root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(pTreeNode root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->data);
    inOrder(root->right);
}

void postOrder(pTreeNode root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ", root->data);
}

计算二叉树的深度可以使用递归的方式来实现。下面是计算二叉树深度的代码：

int depth(pTreeNode root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = depth(root->left);
    int rightDepth = depth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

计算二叉树的结点数和叶子数也可以使用递归的方式来实现。下面是计算二叉树结点数和叶子数的代码：

int countNodes(pTreeNode root) {
    if (root == NULL) {
        return 0;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int countLeaves(pTreeNode root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}