假设二叉树T用二叉链表作存储结构,设计一个c++算法求二叉树(结点值各不相同)中值为x的结点所在的层次。
时间: 2024-06-16 22:05:00 浏览: 127
要设计一个C++算法来求二叉树中值为x的结点所在的层次,可以使用递归的方式进行深度优先搜索(DFS)。
首先,定义一个递归函数来实现搜索操作。该函数需要传入当前节点、目标值x、当前层次level和一个整数变量result用于保存结果。
在递归函数中,首先判断当前节点是否为空,如果为空则返回。然后判断当前节点的值是否等于x,如果相等则将当前层次level赋值给result,并返回。
如果当前节点不为空且值不等于x,则递归调用该函数来搜索当前节点的左子树和右子树。在递归调用时,层次level需要加1。
最后,在主函数中调用该递归函数,并输出结果。
下面是具体的C++代码实现:
```cpp
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void findNodeLevel(TreeNode* root, int x, int level, int& result) {
if (root == nullptr) {
return;
}
if (root->val == x) {
result = level;
return;
}
findNodeLevel(root->left, x, level + 1, result);
findNodeLevel(root->right, x, level + 1, result);
}
int main() {
// 构建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int x = 5; // 目标值
int result = -1; // 结果变量
findNodeLevel(root, x, 1, result);
if (result != -1) {
std::cout << "节点值为" << x << "的结点所在的层次为:" << result << std::endl;
} else {
std::cout << "未找到节点值为" << x << "的结点" << std::endl;
}
return 0;
}
```
阅读全文