c++实现利用二叉树的链式存储结构计算二叉树的深度

在C++中，利用二叉树的链式存储结构（也称为二叉链表）来计算二叉树的深度可以采用递归的方式来实现。二叉链表每个节点通常包含两个指针，分别指向左孩子和右孩子。以下是简单的步骤：

1. 定义一个节点结构体（Node），包含整数值（val）、左孩子指针（left）和右孩子指针（right）。

struct Node {
    int val;
    Node* left;
    Node* right;
};

2. 创建一个函数`int maxDepth(Node* root)`，这个函数用于计算从根节点到最远叶子节点的最长路径。如果根节点为空，则返回0表示空树的深度为0。

int maxDepth(Node* root) {
    if (root == nullptr) {
        return 0; // 空节点，深度为0
    } else {
        // 计算左子树和右子树的最大深度，然后取较大值加一
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return std::max(leftDepth, rightDepth) + 1; // 返回当前节点最大深度
    }
}

相关问题

c++实现利用二叉树的链式存储结构计算二叉树的深度完整代码

在C++中，我们可以使用递归的方式来实现二叉树的链式存储结构（即每个节点包含左指针、右指针以及指向下一个节点的指针）的深度计算。这里是一个简单的示例：

#include <iostream>

// 定义二叉树节点的结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* next; // 链接其他节点的指针
};

// 用于计算树的深度
int maxDepth(TreeNode* root) {
    if (root == nullptr) { // 如果根节点为空，则树的深度为0
        return 0;
    }

    // 递归计算左子树和右子树的深度，并取较大值
    int left_depth = maxDepth(root->left);
    int right_depth = maxDepth(root->right);

    // 树的深度等于左右子树深度的最大值加1（当前节点）
    return std::max(left_depth, right_depth) + 1;
}

int main() {
    // 创建一个示例二叉树
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->left = new TreeNode();
    root->left->val = 2;
    root->left->next = new TreeNode();
    root->left->next->val = 3;
    root->left->next->next = nullptr;

    // 初始化右子树
    root->right = new TreeNode();
    root->right->val = 4;
    root->right->next = new TreeNode();
    root->right->next->val = 5;
    root->right->next->next = nullptr;

    // 计算并输出树的深度
    int depth = maxDepth(root);
    std::cout << "The maximum depth of the binary tree is: " << depth << std::endl;

    // 清理内存
    delete root;
    return 0;
}

在这个例子中，`maxDepth` 函数会遍历整棵树并返回最大深度。

C＋＋ 2.假设二叉树采用链式存储结构进行存储，编写程序实现求出二叉树的深度

在C++中，如果二叉树采用了链式存储结构，即每个节点都有指向左右子节点的指针，那么我们可以使用递归的方式来计算二叉树的深度（也称高度）。以下是实现这一功能的代码片段：

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 求二叉树深度的辅助函数
int maxDepth(TreeNode* root) {
    if (root == nullptr) {  // 如果根节点为空，返回0
        return 0;
    } else {
        // 计算左子树和右子树的最大深度，然后取较大值加1
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        
        return std::max(leftDepth, rightDepth) + 1;  // 返回当前节点的深度
    }
}

// 主函数测试
int main() {
    // 假设你已经有一个二叉树的头节点root
    TreeNode* root = ...;

    int treeDepth = maxDepth(root);
    std::cout << "The depth of the binary tree is: " << treeDepth << std::endl;

    return 0;
}

在这个代码里，`maxDepth` 函数会递归地检查当前节点及其子节点，直到找到空节点为止。每次递归调用都会增加一层深度，当到达最底层的叶子节点时，返回的深度就是整棵树的深度。