算叶子结点及右子树高度

Question

typedef struct btnode{
Elem Type element; struct btnode*lchild,rchild; BTNode;//二叉链表结点类型
typedef struct binarytreef BTNode root;
BinaryTree; 二叉树类型

Answer 1

引自免费微信小程序：皆我百晓生

在C++中，为了计算一个给定二叉树的叶子节点数量以及每个叶子节点对应的右子树的高度，我们可以定义一个递归函数来遍历整个二叉树。这里是一个详细的实现方法：

首先，我们需要为二叉树结构添加一些辅助成员函数，例如获取左孩子、右孩子以及当前节点的高度。

#include <iostream>
using namespace std;

// 定义元素类型
typedef int ElemType;

// 定义二叉链表结点类型
struct TreeNode {
    ElemType data;
    TreeNode* left;
    TreeNode* right;
};

// 获取节点的高度
int getHeight(TreeNode* node) {
    if (node == nullptr) return 0;
    else {
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        return max(leftHeight, rightHeight) + 1;
    }
}

// 计算叶子节点的数量以及对应右子树的高度
void countLeavesAndRightSubtreeHeight(TreeNode* node, int& leafCount, vector<int>& rightSubtreeHeights) {
    if (node == nullptr) return;

    // 如果是叶子节点，增加计数，并将右子树高度存储到向量中（对于叶子节点，其右子树高度为0）
    if (node->right == nullptr && node->left == nullptr) {
        ++leafCount;
        rightSubtreeHeights.push_back(0);
    } else {
        // 非叶子节点，递归处理左右子树
        countLeavesAndRightSubtreeHeight(node->left, leafCount, rightSubtreeHeights);
        countLeavesAndRightSubtreeHeight(node->right, leafCount, rightSubtreeHeights);
    }
}

接下来，你可以创建一个二叉树并调用这些函数来得到结果。注意，这个例子中的二叉树不是通过btnode和binarytreef结构体表示的，而是使用了简单的TreeNode结构体。如果你需要按照你的原始结构来实现，只需要稍作修改即可。

int main() {
    // 创建示例二叉树
    TreeNode* root = new TreeNode{1};
    root->left = new TreeNode{2};
    root->right = new TreeNode{3};
    root->left->left = new TreeNode{4};
    root->left->right = new TreeNode{5};
    root->right->left = new TreeNode{6};

    // 初始化变量
    int leafCount = 0;
    vector<int> rightSubtreeHeights;

    // 计算叶子节点数量和右子树高度
    countLeavesAndRightSubtreeHeight(root, leafCount, rightSubtreeHeights);

    // 输出结果
    cout << "叶节点数量: " << leafCount << endl;
    cout << "右子树高度: ";
    for (int height : rightSubtreeHeights) {
        cout << height << " ";
    }
    cout << endl;

    // 释放内存
    // ... (手动管理内存，删除所有节点)

    return 0;
}

这段代码首先创建了一个简单的二叉树，然后计算了叶子节点的数量以及每个叶子节点对应的右子树的高度。最后，输出了结果。注意，这个示例没有包含内存管理部分，你需要自己处理节点的创建和删除以防止内存泄漏。

如果你的二叉树结构与提供的不同，请根据你的结构进行相应的调整。如果有任何疑问或需要进一步的帮助，请随时告诉我。