C++ 中序遍历二叉树并输出节点深度

下面是一个 C++ 的例子，使用递归方式实现中序遍历二叉树，并输出每个节点所处的深度：

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}  
};

void inorderTraversal(Node* root, int depth) {
    if (root == nullptr) {
        return;
    }
    
    // 递归遍历左子树
    inorderTraversal(root->left, depth + 1);
    
    // 输出当前节点的值和深度
    std::cout << 'Node value: ' << root->data << ', depth: ' << depth << std::endl;
    
    // 递归遍历右子树
    inorderTraversal(root->right, depth + 1);
}

int main() {
    // 创建一个二叉树
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    // 中序遍历二叉树并输出节点深度
    inorderTraversal(root, 0);
    
    // 释放内存
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;
    
    return 0;
}

运行以上代码，输出结果为：

Node value: 4, depth: 2
Node value: 2, depth: 1
Node value: 5, depth: 2
Node value: 1, depth: 0
Node value: 3, depth: 1

以上代码中，inorderTraversal 函数实现了中序遍历二叉树的逻辑，通过 depth 参数记录当前节点的深度。在函数内部，先递归遍历左子树，然后输出当前节点的值和深度，最后递归遍历右子树。在 main 函数中，创建了一个简单的二叉树，并调用 inorderTraversal 函数进行遍历和输出。最后，需要手动释放创建的节点内存，以避免内存泄漏。