用C语言 建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法

在编程中，树是一种非线性的数据结构，它的节点分为根节点、子节点，每个子节点可以有左右两个分支。为了有效地处理这类数据，我们会创建相关的函数和类来进行操作。下面是一些基本的操作： 1. **二叉树的二叉链表头文件.h**: ```c++ // 定义二叉树节点的结构体 typedef struct TreeNode { int data; // 节点值 TreeNode* left; // 左孩子指针 TreeNode* right; // 右孩子指针 } TreeNode; // 函数声明 TreeNode* createEmptyTree(); // 创建空树 void destroyTree(TreeNode* root); // 销毁树并释放内存 void clearTree(TreeNode* &root); // 清空树 TreeNode* buildLevelOrderInput(int arr[], int n); // 按层序输入数据建树 TreeNode* buildPreorderInput(int arr[], int n); // 按先序输入数据建树 bool isEmpty(TreeNode* root); // 判空 int treeDepth(TreeNode* root); // 计算树的深度 TreeNode* getRoot(TreeNode* root); // 获取根节点 TreeNode* getParent(TreeNode* node); // 获取父节点 TreeNode* getLeftChild(TreeNode* node); // 获取左孩子 TreeNode* getRightChild(TreeNode* node); // 获取右孩子 TreeNode* getLeftBrother(TreeNode* node); // 获取左兄弟 TreeNode* getRightBrother(TreeNode* node); // 获取右兄弟 TreeNode* insertSubtree(TreeNode* parent, TreeNode* subtree); // 插入子树 TreeNode* deleteSubtree(TreeNode* root, TreeNode* target); // 删除子树 void displayGeneralList(TreeNode* root); // 显示广义表形式的树 ```

首先，以下是使用C语言实现上述功能的部分代码： 1. **按先序序列构造二叉链表**（假设先序遍历数组pre[]存储了节点值，数组长度为n，pre[0]为根节点，前缀sum[]存储了前i个元素的累加和用于查找子节点索引）: ```c typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; TreeNode* buildTree(int pre[], int n) { if (n == 0) return NULL; TreeNode* root = new TreeNode(pre[0]); int i = 1, sum = 0; for (; i < n && pre[i]; ++i) { while (sum <= pre[i]) { sum += pre[++root->left->val]; } root->right = new TreeNode(pre[i]); ++sum; } return root; } ``` 2. **中序遍历（递归）**: ```c void inorderTraversal(TreeNode* node) { if (node != NULL) { inorderTraversal(node->left); printf("%d ", node->val); // 输出节点值 inorderTraversal(node->right); } } ``` 3. **求二叉树高度**: ```c int height(TreeNode* root) { if (root == NULL) return 0; int leftHeight = height(root->left); int rightHeight = height(root->right); return MAX(leftHeight, rightHeight) + 1; } int main() { // 先构建树... int heightResult = height(root); printf("树的高度: %d\n", heightResult); return 0; } ``` 4. **求二叉树的叶节点数**: ```c int countLeaves(TreeNode* node, int count) { if (node == NULL) return count; if (node->left == NULL && node->right == NULL) count++; return countLeaves(node->left, count) + countLeaves(node->right, count); } int main() { int leafCount = countLeaves(root, 0); printf("叶节点数: %d\n", leafCount); return 0; } ``` 5. **交换每个节点的左右子树**: ```c void swapChildren(TreeNode* node) { if (node != NULL) { TreeNode* temp = node->left; node->left = node->right; node->right = temp; swapChildren(node->left); swapChildren(node->right); } } int main() { // 在这里调用swapChildren(root)函数 printf("交换后的树结构...\n"); return 0; } ``` 请注意，为了完整实现所有功能，上述代码需要在main函数中整合并处理用户输入。此外，`MAX()`和`new`在C语言中可能需要自定义，因为标准库中一般没有提供。你可以选择使用宏或者头文件如`stdlib.h`或`malloc.h`。