（1）构造一棵二叉树； （2）对此二叉树进行先根、中根、后根遍历; （3）计算二叉树中叶子结点、度为1的结点、度为2的结 点个数； （4）计算二叉树的高度； （5）查找给定结点的位置。用C语言编写

（1）构造一棵二叉树通常涉及节点结构的设计和节点之间的链接。在C语言中，你可以创建一个简单的结构体来表示二叉树节点：

typedef struct TreeNode {
    int val;       // 节点值
    struct TreeNode *left;   // 左孩子指针
    struct TreeNode *right;  // 右孩子指针
} TreeNode;

（2）对二叉树进行遍历有三种基本方式：先序遍历（根-右），中序遍历（左-根-右），和后序遍历（左-右-根）。以下是遍历函数示例：

- 先序遍历：

void preOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->val);  // 输出当前节点
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

- 中序遍历：

void inOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->val);
        inOrderTraversal(root->right);
    }
}

- 后序遍历：

void postOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        printf("%d ", root->val);
    }
}

（3）计算叶子结点、度为1的结点（即只有一个孩子的节点）、度为2的结点个数，可以在遍历时统计：

int countLeafs(TreeNode* root, int leafs, int deg1, int deg2) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) leafs++;
    else if (root->left == NULL || root->right == NULL) {
        deg1++;
        deg2--;
    }
    return countLeafs(root->left, leafs, deg1, deg2) + countLeafs(root->right, leafs, deg1, deg2);
}

int leaves, degree1, degree2;
leaves = degree1 = degree2 = countLeafs(root, leaves, degree1, degree2);

（4）计算二叉树的高度可以递归地进行：

int heightOfTree(TreeNode* root) {
    if (root == NULL) return 0;
    int leftHeight = heightOfTree(root->left);
    int rightHeight = heightOfTree(root->right);
    return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

（5）查找给定结点位置需要提供结点值和二叉搜索树（BST）的特性。如果是普通二叉树，查找无特定顺序，可以使用递归：

TreeNode* findNode(TreeNode* root, int target) {
    if (root == NULL || root->val == target) return root;
    if (target < root->val) return findNode(root->left, target);
    return findNode(root->right, target);
}