二叉树递归查找值为x的结点,找到返回其地址否则返回NULL的c++代码
时间: 2024-05-06 20:21:10 浏览: 8
下面是二叉树递归查找值为x的结点的C语言代码:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* searchBST(struct TreeNode* root, int val){
if (root == NULL || root->val == val) {
return root;
}
if (val < root->val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
```
这段代码可以在二叉搜索树中查找值为x的结点,如果找到了就返回该结点的地址,否则返回NULL。
相关问题
在二叉树中查找值为x并求出以该结点为根的子树深度
在二叉树中查找值为x的结点,可以采用递归的方式进行查找。首先判断当前结点是否为NULL,如果是,则返回NULL;否则,判断当前结点的值是否为x,如果是,则返回当前结点;否则,递归地在当前结点的左子树和右子树中查找值为x的结点。
以下是 C++ 代码实现:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* search(TreeNode* root, int x) {
if (root == NULL) {
return NULL;
}
if (root->val == x) {
return root;
}
TreeNode* left = search(root->left, x);
if (left != NULL) {
return left;
}
return search(root->right, x);
}
```
对于找到值为x的结点,可以使用递归求取以该结点为根的子树深度。子树深度可以通过左右子树的深度取最大值再加1得到。
以下是 C++ 代码实现:
```cpp
int depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_depth = depth(root->left);
int right_depth = depth(root->right);
return max(left_depth, right_depth) + 1;
}
int subtreeDepth(TreeNode* root, int x) {
TreeNode* node = search(root, x);
if (node == NULL) {
return 0;
}
return depth(node);
}
```
其中,depth函数用于求取二叉树的深度。subtreeDepth函数用于求取以值为x的结点为根的子树深度。
C++使用递归方法构造二叉树,用到二叉树结点,输入为层次遍历序列
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 构造二叉树
TreeNode* buildTree(vector<int>& nums, int index) {
// 边界条件
if (index >= nums.size() || nums[index] == -1) {
return NULL;
}
// 构造当前结点
TreeNode* root = new TreeNode(nums[index]);
// 递归构造左子树和右子树
root->left = buildTree(nums, 2 * index + 1);
root->right = buildTree(nums, 2 * index + 2);
return root;
}
// 层次遍历二叉树
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
cout << node->val << " ";
if (node->left != NULL) {
que.push(node->left);
}
if (node->right != NULL) {
que.push(node->right);
}
}
}
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7, -1, -1, 8, 9};
TreeNode* root = buildTree(nums, 0);
levelOrder(root);
return 0;
}