用c语言用递归算法计算二叉树分支数

二叉树的分支数等于其左子树的分支数加上右子树的分支数再加一，即：

int branches(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return branches(root->left) + branches(root->right) + 1;
}

其中，`struct TreeNode` 是二叉树节点的结构体，如下所示：

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

相关问题

c语言实现用递归算法输出二叉树中从每个叶子结点到根结点的路径

假设二叉树的结构体定义如下：

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

可以使用递归算法来输出每个叶子结点到根结点的路径，具体实现如下：

void printPaths(struct TreeNode* root, int path[], int pathLen) {
    if (root == NULL) {
        return;
    }
    
    // 将当前结点的值加入路径中
    path[pathLen] = root->val;
    pathLen++;
    
    // 如果当前结点是叶子结点，则输出路径
    if (root->left == NULL && root->right == NULL) {
        for (int i = pathLen - 1; i >= 0; i--) {
            printf("%d ", path[i]);
        }
        printf("\n");
    }
    else {
        // 否则继续遍历左右子树
        printPaths(root->left, path, pathLen);
        printPaths(root->right, path, pathLen);
    }
}

在主函数中调用该函数即可输出每个叶子结点到根结点的路径：

int main() {
    struct TreeNode* root = createBinaryTree();  // 创建二叉树
    
    int path[100];  // 存储路径
    int pathLen = 0;  // 路径长度
    
    printPaths(root, path, pathLen);  // 输出路径
    
    return 0;
}

其中 `createBinaryTree()` 是创建二叉树的函数，需要根据实际情况进行实现。

（二） c语言采用递归先序算法建立二叉树。要求通过键盘输入二叉树的先序遍历顺序从而建立一棵二叉树，哉采用递归算法实现显示出二叉树先序、中序和后序遍历顺序，最后采用非递归算法实现二叉树的先序或中序遍历

在C语言中，使用递归先序算法构建二叉树通常需要以下几个步骤：

1. **输入序列处理**：
首先，你需要从用户处获取二叉树的先序遍历序列，这个序列包含了根节点、左子树的先序遍历和右子树的先序遍历。

2. **递归函数**：
编写一个递归函数`buildTree()`，它接受当前遍历到的元素、剩余序列以及前序遍历序列作为参数。函数首先检查是否已遍历完序列，如果是，则返回`NULL`表示结束。否则，它会找到第一个未访问的元素，将其设置为当前节点，然后递归地为左右子树创建子节点，并将它们添加到当前节点。

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

TreeNode* buildTree(int pre[], int n) {
    if (n <= 0) return NULL; // 序列结束标志
    TreeNode* root = new TreeNode(pre[0]); // 当前节点
    int i = 1;
    while (pre[i] != -1) { // 遍历剩余序列
        root->left = buildTree(pre + i, n - i); // 递归左子树
        root->right = buildTree(pre + i + 1, n - i - 1);
        i += 2; // 跳过已处理的左右子节点
    }
    return root;
}

其中，`pre[]`是一个包含先序遍历整数的数组，`-1`用于标记序列结束。

3. **遍历函数**：
创建辅助函数分别用于先序（Preorder）、中序（Inorder）和后序（Postorder）遍历，通常都是递归的。例如，先序遍历就是根节点 -> 左子树 -> 右子树。

4. **非递归遍历**：
若要非递归实现，可以考虑使用栈数据结构来保存待访问的节点，但这需要更为复杂的逻辑来控制访问顺序。