求以孩子兄弟表示法存储的二叉树的高度C语言

在C语言中，如果我们要使用孩子兄弟表示法（Child-Sibling Representation，也称为左孩子的链表表示法）来存储二叉树，每个节点包含三个指针：一个指向其左子节点，一个指向其右子节点，以及一个指向其右侧相邻节点的指针（即哥哥节点）。这种表示方法使得层次遍历（如先序、中序或后序遍历）相对容易，因为可以按照线索顺序直接访问下一个节点。

计算这样的二叉树高度（最大层数）的基本思路是采用递归或迭代的方式。以下是迭代版本的一个简单算法：

int heightInCSR(struct Node* root) {
    if (root == NULL) return 0; // 空树的高度是0

    int level = 1;
    queue<Node*> q;
    q.push(root); // 将根节点入队
    while (!q.empty()) {
        int size = q.size(); // 当前层的节点数
        for (int i = 0; i < size; i++) {
            struct Node* node = q.front();
            q.pop();

            // 如果有右子节点，将其加入下一层
            if (node->right)
                q.push(node->right);

            // 如果还有左侧未访问的兄弟节点，将兄弟节点加入下一层
            if (node->brother) {
                q.push(node->brother);
            }
            level++; // 移动到下一层次
        }
    }
    return level - 1; // 减一是因为层数从1开始计数
}