java二叉排序树上找结点x的算法
时间: 2023-08-14 19:07:28 浏览: 48
在Java中,可以通过以下代码实现在二叉排序树上找结点x的算法:
```java
public Node search(Node root, int x) {
if (root == null || root.val == x) {
return root;
}
if (root.val > x) {
return search(root.left, x);
}
return search(root.right, x);
}
```
其中,Node表示二叉排序树的节点,val表示节点的值,left表示左子树,right表示右子树。该算法使用递归实现,在每个节点上比较节点的值与x的大小关系,继续查找左子树或右子树,直到找到节点值等于x的节点或遍历到叶子节点仍未找到。如果根节点为null或根节点的值等于x,则直接返回根节点。
相关问题
二叉排序树上找结点x,用java写
假设二叉排序树的结点定义如下:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
```
可以使用递归或迭代的方法在二叉排序树上查找结点x。
递归实现:
```java
public TreeNode searchBST(TreeNode root, int x) {
if (root == null || root.val == x) {
return root;
}
if (x < root.val) {
return searchBST(root.left, x);
} else {
return searchBST(root.right, x);
}
}
```
迭代实现:
```java
public TreeNode searchBST(TreeNode root, int x) {
while (root != null && root.val != x) {
if (x < root.val) {
root = root.left;
} else {
root = root.right;
}
}
return root;
}
```
其中,递归实现通过比较当前结点的值和目标值来判断向左还是向右子树递归;迭代实现则通过一个循环,不断向左或向右子树移动,直到找到目标结点或者到达叶子结点为止。
c++在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。
在二叉排序树中插入结点的算法如下:
```c++
// 定义二叉排序树的结点
struct BSTNode {
int val; // 结点的值
BSTNode* left; // 左子树指针
BSTNode* right; // 右子树指针
BSTNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
// 插入结点的函数
void insert(BSTNode* &root, int val) {
if (!root) {
root = new BSTNode(val);
return;
}
if (root->val > val) {
insert(root->left, val);
}
else {
insert(root->right, val);
}
}
```
在此基础上,我们可以实现构建二叉排序树的算法。具体思路是,读入一组数据,依次将每个数据插入到二叉排序树中。代码如下:
```c++
// 构建二叉排序树的函数
BSTNode* build_tree() {
BSTNode* root = nullptr;
int val;
while (cin >> val) {
insert(root, val);
}
return root;
}
```
调用上述函数,即可构建出一颗二叉排序树。