C++实现二叉树（#为补全的空结点）的基本操作，包括树的创建和输出，求叶子结点数目和深度。

Question

实现二叉树（#为补全的空结点）的基本操作，包括树的创建和输出，求叶子结点数目和深度。

Answer 1

答案引用自chatgpt生成，望对题主有所帮助/启发；若有帮助，还望采纳！

在C++中，我们可以使用结构体来定义二叉树的节点，然后通过指针来连接这些节点，形成一棵二叉树。以下是一个简单的实现：

#include<iostream>
using namespace std;

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

// 创建二叉树
TreeNode* createTree(int arr[], int n, int i) {
    if(i >= n || arr[i] == -1) {
        return NULL;
    }
    TreeNode* node = new TreeNode(arr[i]);
    node->left = createTree(arr, n, 2*i+1);
    node->right = createTree(arr, n, 2*i+2);
    return node;
}

// 输出二叉树
void printTree(TreeNode* root) {
    if(root == NULL) {
        return;
    }
    cout << root->val << " ";
    printTree(root->left);
    printTree(root->right);
}

// 求二叉树的叶子节点数目
int countLeaves(TreeNode* root) {
    if(root == NULL) {
        return 0;
    }
    if(root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

// 求二叉树的深度
int depth(TreeNode* root) {
    if(root == NULL) {
        return 0;
    }
    int leftDepth = depth(root->left);
    int rightDepth = depth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

int main() {
    int arr[] = {1, 2, 3, -1, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    TreeNode* root = createTree(arr, n, 0);
    printTree(root);
    cout << endl;
    cout << "Number of leaves: " << countLeaves(root) << endl;
    cout << "Depth of tree: " << depth(root) << endl;
    return 0;
}

在这个代码中，我们首先定义了一个结构体TreeNode来表示二叉树的节点，每个节点包含一个值和两个指向左右子节点的指针。然后我们定义了四个函数来实现二叉树的基本操作：创建二叉树、输出二叉树、求二叉树的叶子节点数目和求二叉树的深度。在主函数中，我们创建了一个二叉树，并调用这四个函数来进行操作。