用c++ 按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 15:19:10 浏览: 94
求二叉树叶子结点的个数(c++类建立)
5星 · 资源好评率100%
好的,我可以帮你解答这个问题。
首先,我们需要定义二叉树的节点结构体:
```c++
struct BinaryTreeNode {
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
```
然后,我们需要一个函数来按照先序遍历序列建立二叉树:
```c++
BinaryTreeNode* buildTree(vector<int>& preorder, int& index) {
if (index >= preorder.size() || preorder[index] == -1) {
// 如果当前节点为nullptr,返回nullptr
return nullptr;
}
// 创建当前节点
BinaryTreeNode* node = new BinaryTreeNode(preorder[index]);
// 递归创建左子树
index++;
node->left = buildTree(preorder, index);
// 递归创建右子树
index++;
node->right = buildTree(preorder, index);
return node;
}
```
其中,preorder是先序遍历序列,index是当前节点在序列中的下标。-1表示当前节点为nullptr。
接下来,我们可以计算叶子结点个数和二叉树的深度:
```c++
void getLeafCountAndDepth(BinaryTreeNode* root, int& leafCount, int& depth) {
if (!root) {
return;
}
if (!root->left && !root->right) {
// 叶子结点
leafCount++;
}
getLeafCountAndDepth(root->left, leafCount, depth);
getLeafCountAndDepth(root->right, leafCount, depth);
// 计算深度
depth = max(depth, max(getDepth(root->left), getDepth(root->right)) + 1);
}
int getDepth(BinaryTreeNode* root) {
if (!root) {
return 0;
}
return max(getDepth(root->left), getDepth(root->right)) + 1;
}
```
其中,getDepth函数计算以root为根节点的二叉树的深度,getLeafCountAndDepth函数同时计算叶子结点个数和二叉树的深度。
最后,我们可以将以上函数组合起来:
```c++
int main() {
vector<int> preorder = {1, 2, -1, -1, 3, 4, -1, -1, 5, -1, -1};
int index = 0;
BinaryTreeNode* root = buildTree(preorder, index);
int leafCount = 0, depth = 0;
getLeafCountAndDepth(root, leafCount, depth);
cout << "Leaf count: " << leafCount << endl;
cout << "Depth: " << depth << endl;
return 0;
}
```
输出结果为:
```
Leaf count: 3
Depth: 3
```
这说明我们的函数计算结果是正确的。
阅读全文