若用二叉链表作为二叉树的存储表示，请设计算法求二叉树中度为 1 的结点个数。

可以按照以下算法实现求二叉树中度为1的节点个数：

1. 初始化变量 count 为0，根节点 root 入队。
2. 循环执行以下操作直到队列为空：
1) 出队一个节点p。
2) 如果p的左右孩子均为NULL，跳过当前循环，继续下一次循环。
3) 如果p只有左孩子或只有右孩子，则令 count 加1。
4) 如果p有左右孩子，将其左右孩子入队。
3. 返回 count 值即为二叉树中度为1的节点个数。

示例代码如下：

def count_degree_1(root):
    if not root:
        return 0
    count = 0
    queue = [root]
    while queue:
        p = queue.pop(0)
        if not p.left and not p.right:
            continue
        if not p.left or not p.right:
            count += 1
        if p.left:
            queue.append(p.left)
        if p.right:
            queue.append(p.right)
    return count

相关问题

以二叉链表作为二叉树的存储结构，求二叉树的叶子结点个数。

### 回答1：
使用二叉链表作为二叉树的存储结构，可以通过遍历二叉树来求出二叉树的叶子结点个数。具体方法如下：

1. 如果二叉树为空，则叶子结点个数为。

2. 如果二叉树非空，则分别递归计算左子树和右子树的叶子结点个数。

3. 如果当前结点的左右子树都为空，则当前结点为叶子结点，叶子结点个数加1。

4. 最后返回左右子树叶子结点个数之和。

代码实现如下：

def count_leaves(root):
    if root is None:
        return 
    if root.left is None and root.right is None:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

其中，root表示二叉树的根节点，left和right分别表示左子树和右子树。函数返回二叉树的叶子结点个数。

### 回答2：
二叉链表是一种常见的二叉树的存储结构，它是由一个结构体构成，其中包含了该结点的信息（如值、父结点、左右儿子等），以及指向左右儿子结点的指针。对于二叉树的叶子结点，其左右儿子指针均为空。

要求二叉树的叶子结点个数，可以从根结点开始遍历整棵树，对于每个结点，判断其左右儿子是否为空，如果均为空，则该结点为叶子结点，计数器加1。如果左儿子不为空，则递归遍历左子树；如果右儿子不为空，则递归遍历右子树。最终，计数器的值即为二叉树的叶子结点个数。

具体的代码实现如下：

# 定义二叉树的结点类
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 计算二叉树的叶子结点个数
def count_leaves(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(count_leaves(root))  # 输出：4

在上面的代码中，我们首先定义了一个二叉树的结点类，包含了结点的值和左右儿子指针。然后，我们定义了一个递归函数 `count_leaves`，用来计算二叉树的叶子结点个数。具体实现中，我们先判断当前结点是否为叶子结点，如果是，则返回1；如果不是，则分别递归计算其左右子树的叶子结点个数，并将结果相加。最后，我们对整棵树调用 `count_leaves`，并输出结果。在上面的例子中，二叉树共有4个叶子结点，输出结果为4。

### 回答3：
二叉链表是一种二叉树的存储结构，它是通过链表的方式来表示二叉树的结构。在二叉链表中，每个结点除了存放数据之外，还需要存放左右孩子的地址，这样才能表示二叉树的结构。

求二叉树的叶子结点个数，可以通过遍历二叉树来实现。遍历二叉树的方法有前序遍历、中序遍历和后序遍历，这里以中序遍历为例进行说明。

中序遍历是指按照左子树->根->右子树的顺序遍历二叉树。对于一个结点，如果其左右孩子为空，则该结点为叶子结点，否则继续递归遍历其左右子树。

下面给出求二叉树叶子结点个数的代码实现：

int countLeaves(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        // 当前结点为叶子结点
        return 1;
    }
    // 递归遍历左右子树
    return countLeaves(root->left) + countLeaves(root->right);
}

在这个代码中，root表示当前结点，如果其左右孩子均为空，则该结点为叶子结点，返回1，否则递归遍历其左右子树，并将它们的叶子结点个数相加作为当前结点的叶子结点个数。最后，通过递归汇总，就能得到整个二叉树的叶子结点个数了。

总之，二叉链表作为二叉树的存储结构，可以用递归的方式来遍历二叉树并求解叶子结点个数，这种方法简单易懂、代码实现方便，具有较高的实用性。

使用C语言以二叉链表作为二叉树的存储结构，编写用层次顺序遍历二叉树的方法，统计树中度为1 的结点个数

以下是使用C语言以二叉链表作为二叉树的存储结构，编写用层次顺序遍历二叉树的方法，统计树中度为1 的结点个数的代码。

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

// 定义二叉树结点的结构体
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义队列结点的结构体
typedef struct QueueNode {
    TreeNode* data;
    struct QueueNode* next;
} QueueNode;

// 定义队列的结构体
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
int isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 入队
void enqueue(Queue* queue, TreeNode* data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    if (isQueueEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队
TreeNode* dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Queue is empty!\n");
        return NULL;
    } else {
        TreeNode* data = queue->front->data;
        QueueNode* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
        return data;
    }
}

// 层次顺序遍历二叉树
void levelOrderTraversal(TreeNode* root, int* count) {
    if (root == NULL) {
        return;
    }
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root);
    while (!isQueueEmpty(&queue)) {
        TreeNode* node = dequeue(&queue);
        if (node->left != NULL) {
            enqueue(&queue, node->left);
        }
        if (node->right != NULL) {
            enqueue(&queue, node->right);
        }
        if ((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL)) {
            (*count)++;
        }
        printf("%d ", node->data);
    }
}

int main() {
    // 构造二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = 1;
    TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
    node1->data = 2;
    TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
    node2->data = 3;
    TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
    node3->data = 4;
    TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
    node4->data = 5;
    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node1->right = NULL;
    node2->left = NULL;
    node2->right = node4;
    node3->left = NULL;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;

    int count = 0;
    levelOrderTraversal(root, &count);
    printf("\nNumber of nodes with degree 1: %d\n", count);

    return 0;
}

运行结果：

1 2 3 4 5 
Number of nodes with degree 1: 2

在该代码中，我们使用了一个队列来存储二叉树中的结点，实现了层次顺序遍历。在遍历过程中，我们判断每个结点的左右子树是否为空，如果有一个为空，就说明该结点的度为1，将计数器加1。最后输出计数器的值即为树中度为1的结点个数。