一个程序 exp7-6.cpp 实现以下功能,并对图7.1所示的二叉树进行验证。 (1)输出二叉树6的结点个数。 (2) 输出二叉树b的叶子结点个数。 (3)求二叉树6中指定结点值(假设所有结点值不同)的结点的层次。 (4)利用层次遍历求二叉树6的宽度。
时间: 2024-10-28 09:06:19 浏览: 12
二叉树7-1-1.cpp
在C++中,为了实现对给定二叉树的功能,我们可以创建一个二叉树结构,并提供相应的方法来执行所需的操作。这里是一个简化的`exp7-6.cpp`示例,使用了`TreeNode`结构和一些辅助函数:
```cpp
#include <iostream>
using namespace std;
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
// 添加节点
void addNode(int value) {
if (root == nullptr) {
root = new TreeNode(value);
} else {
insert(root, value);
}
}
private:
TreeNode* root = nullptr;
// 插入函数,用于递归添加节点
void insert(TreeNode*& node, int value) {
if (value < node->val) {
if (node->left == nullptr) {
node->left = new TreeNode(value);
} else {
insert(node->left, value);
}
} else {
if (node->right == nullptr) {
node->right = new TreeNode(value);
} else {
insert(node->right, value);
}
}
}
// 结点数量
int countNodes(TreeNode* node) {
if (node == nullptr) {
return 0;
}
return 1 + countNodes(node->left) + countNodes(node->right);
}
// 叶子节点数量
int leafCount(TreeNode* node) {
if (node == nullptr || (node->left == nullptr && node->right == nullptr)) {
return (node == nullptr ? 0 : 1);
}
return leafCount(node->left) + leafCount(node->right);
}
// 指定值的结点层次
int depthOfValue(TreeNode* node, int target) {
if (node == nullptr) {
return -1; // 结点不存在
}
if (node->val == target) {
return 0;
}
return 1 + max(depthOfValue(node->left, target), depthOfValue(node->right, target));
}
// 层次遍历求宽度
int widthByLevel(TreeNode* node) {
if (node == nullptr) {
return 0;
}
queue<TreeNode*> q;
q.push(node);
int maxWidth = 0, levelWidth[100] = {};
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
TreeNode* current = q.front(); q.pop();
levelWidth[current->val % 100]++;
if (current->left != nullptr) {
q.push(current->left);
}
if (current->right != nullptr) {
q.push(current->right);
}
}
maxWidth = max(maxWidth, *max_element(levelWidth, levelWidth + 100));
}
return maxWidth;
}
// 验证图7.1所示的二叉树
bool validateTree(TreeNode* node, const vector<int>& expectedValues) {
if (node == nullptr) {
return true;
}
if (expectedValues[node->val] != node->val) {
return false;
}
return validateTree(node->left, expectedValues) && validateTree(node->right, expectedValues);
}
};
int main() {
BinaryTree bt;
// 初始化二叉树6的数据,比如手动添加节点
// ...
// 调用上述方法
int nodeCount = bt.countNodes(bt.root);
int leafCount = bt.leafCount(bt.root);
int depth = bt.depthOfValue(bt.root, someTargetValue);
int treeWidth = bt.widthByLevel(bt.root);
// 验证二叉树
vector<int> expectedValues = { /* 图7.1的实际值列表 */ };
bool isValid = bt.validateTree(bt.root, expectedValues);
cout << "Node Count of Binary Tree 6: " << nodeCount << endl;
cout << "Leaf Nodes in Binary Tree b: " << leafCount << endl;
cout << "Depth of specified node with value X: " << depth << endl;
cout << "Width of the binary tree: " << treeWidth << endl;
cout << "Is tree valid based on Figure 7.1? " << (isValid ? "Yes" : "No") << endl;
return 0;
}
```
在这个代码中,我们实现了节点添加、计数、叶子节点数量获取、特定值层次计算、宽度测量以及验证二叉树的功能。你需要根据实际需求调整初始化部分以适应图7.1所示的二叉树。
阅读全文