己知一棵以二叉链表方式存储的二叉树，求该二叉树的高度

在二叉链表表示的二叉树中，求解高度通常采用递归的方式。树的高度是从根节点到最远叶子节点的最大路径长度，其中每个节点都有0或2个孩子。你可以按照以下步骤计算：

1. **基本情况**：如果当前节点为空，那么空树的高度是0。
2. **递归过程**：对于非空节点，计算左子树和右子树的高度。然后取两者的较大值加1，作为当前节点的高度。
3. **总高度**：最终树的高度就是所有非空节点中最高的那一个。

这个过程可以这样描述算法：

def height(root):
    if root is None:   # 如果节点为空，高度为0
        return 0
    else:
        left_height = height(root.left)  # 计算左子树高度
        right_height = height(root.right)  # 计算右子树高度
        return max(left_height, right_height) + 1  # 返回较大的一边高度加1

# 调用函数并传入二叉树的根节点
height_of_tree = height(root)

相关问题

C语言编程实现，己知一棵以二叉链表方式存储的二叉树，求该二叉树的层次遍历

在C语言中，要实现二叉树的层次遍历（也称广度优先搜索，BFS），通常会使用队列数据结构来辅助操作。这里是一个简单的示例，假设我们已经有一个二叉链表节点结构：

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

// 队列结构体用于存储节点及其层次
typedef struct QueueNode {
    TreeNode* node;
    int level;
} QueueNode, *Queue;

void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return; // 如果根节点为空，直接返回

    Queue queue = (Queue)malloc(sizeof(QueueNode)); // 创建一个空队列
    QueueNode* front = queue; // 初始化队列头指针

    front->node = root;
    front->level = 0;
    queue->next = NULL;

    while (front != NULL) { // 当队列非空时循环
        TreeNode* current = front->node;
        front = front->next;

        printf("%d ", current->val); // 输出当前层所有节点值

        if (current->left != NULL) { // 将左子节点入队
            QueueNode* newFront = (QueueNode*)malloc(sizeof(QueueNode));
            newFront->node = current->left;
            newFront->level = front->level + 1;
            newFront->next = queue;
            queue = newFront;
        }
        if (current->right != NULL) { // 同理，将右子节点入队
            QueueNode* newFront = (QueueNode*)malloc(sizeof(QueueNode));
            newFront->node = current->right;
            newFront->level = front->level + 1;
            newFront->next = queue;
            queue = newFront;
        }
    }

    free(queue); // 释放内存
}

C语言编程实现，己知一棵以二叉链表方式存储的二叉树，求该二叉树的层次遍历序列

在C语言中，实现二叉树的层次遍历通常需要使用队列数据结构。以下是层次遍历的一个基本步骤：

1. 定义一个队列，用于存储当前层的所有节点。
2. 初始化队列，将根节点入队。
3. 当队列非空时，执行循环：
a. 弹出队首元素（当前层的第一个节点），访问它。
b. 如果这个节点有左孩子，将其左孩子入队；如果有右孩子，也将其右孩子入队（因为下一层节点会先从左开始）。
4. 继续弹出并访问队首元素，直到队列为空。

这是一个基础的算法描述，下面是一个简单的伪代码示例：

void levelOrder(struct TreeNode* root) {
    if (root == NULL) return;
    queueenqueue(&queue, root); // 将根节点入队
    while (!queuelenempty(&queue)) { // 当队列非空
        struct TreeNode* node = queuedequeue(&queue); // 出队当前层第一个节点
        visit(node->val); // 访问节点值

        // 将左右子节点入队，如果存在
        if (node->left != NULL) queueenqueue(&queue, node->left);
        if (node->right != NULL) queueenqueue(&queue, node->right);
    }
}

在这个函数里，`struct TreeNode*`是你自定义的表示二叉树节点的数据结构，包含`val`（值）、`left`（左子节点）和`right`（右子节点）指针。`queueenqueue`和`queuedequeue`是模拟队列操作的函数。