6-5 求树（或森林）的高度 分数 13 作者 曾艳 单位 西安邮电大学 编写算法，在以孩子兄弟二叉链表存储的树（或森林）中，求树（或森林）的高度。 函数接口定义： int GetHeight (CSTree rt);

在C++中，给定一个孩子兄弟二叉链表表示的树（forest），我们可以使用递归的方式来计算树的高度。这里的`CSTree`结构体或类通常包含两个成员：指向左孩子的指针和指向右孩子的指针，以及一个表示根节点的标识。高度是指从根节点到最远叶子节点的最大路径长度。下面是一个简单的算法实现：

// 假设CSTree类有一个整型height字段用于记录当前节点的高度
class CSTree {
public:
    // 其他方法...
    int getHeight() { return height; }
    CSTree* leftChild() { return left; } // 左孩子指针
    CSTree* rightChild() { return right; } // 右孩子指针
    bool isRoot() { return rootFlag; } // 根节点标志
};

int GetHeight(CSTree* rt) {
    if (!rt || !rt->isRoot()) return 0; // 空树或非根节点高度为0

    // 递归获取左右子树的高度，并返回较大者加1作为当前节点的高度
    int leftHeight = GetHeight(rt->leftChild());
    int rightHeight = GetHeight(rt->rightChild());

    return std::max(leftHeight, rightHeight) + 1;
}

相关问题

6-1 二叉树中求度为2的结点的个数 分数 10  全屏浏览 作者 曾艳 单位 西安邮电大学 编写算法，在以二叉链表存储的二叉树中，求度为2的结点的个数。 函数接口定义： int Degree2(

在二叉链表表示的二叉树中，求度为2的节点个数可以通过深度优先搜索（DFS）或者广度优先搜索（BFS）来实现。这里我将提供一个基于递归的解决方案：

// 假设二叉链表节点结构体定义如下：
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int Degree2(TreeNode* root) {
    if (root == nullptr) return 0; // 如果根节点为空，返回0

    int degree2 = 0; // 初始化度为2的节点计数器
    bool hasRightChild = false;

    // 使用递归遍历左子树和右子树
    if (root->right != nullptr) {
        degree2 += 1; // 非空右子树的当前节点度为2
        hasRightChild = true;
    }

    degree2 += Degree2(root->left); // 计算左子树的度2节点，并累加到总和

    // 如果左子树存在且有右孩子，说明有一个新的度为2节点
    if (hasRightChild && root->left->right != nullptr) {
        degree2++;
    }

    return degree2;
}

这个算法通过检查每个节点是否有右子节点以及它的左子节点是否也有右子节点来计算度为2的节点。递归会一直深入直到叶子节点，然后返回上来更新计数。