二叉树中查找指定结点 C++

在C++中，二叉搜索树（Binary Search Tree，BST）用于查找特定节点通常涉及以下步骤：

1. **遍历**：首先需要有一个指向根节点的指针。如果树为空，则表示没有找到目标节点。如果节点值小于目标值，我们递归地在右子树中查找；如果节点值大于目标值，我们在左子树中查找。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* searchBST(TreeNode* root, int target) {
    if (root == nullptr || root->val == target) {
        return root;
    }
    if (root->val < target) {
        return searchBST(root->right, target);
    } else {
        return searchBST(root->left, target);
    }
}

2. **终止条件**：当遍历到空节点或者当前节点的值等于目标值时，查找结束并返回该节点。

相关问题

二叉树查找双亲结点c++

二叉树查找双亲结点可以通过递归实现。如果当前节点是根节点，则其没有双亲节点，返回空指针。否则，递归查找其父节点。

以下是C++代码实现：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

TreeNode* findParent(TreeNode* root, TreeNode* node) {
    if (root == nullptr || root == node) return nullptr;
    if (root->left == node || root->right == node) return root;
    TreeNode* leftParent = findParent(root->left, node);
    if (leftParent != nullptr) return leftParent;
    return findParent(root->right, node);
}

其中，`root` 表示当前节点所在的子树的根节点，`node` 表示要查找双亲节点的节点。如果 `root` 为空或者等于 `node`，说明当前节点没有双亲节点，返回空指针。如果 `root` 的左子节点或右子节点等于 `node`，说明 `node` 是 `root` 的子节点，返回 `root`。否则，递归查找 `node` 在 `root` 的左子树中的双亲节点，如果找到了，则返回该节点；否则，递归查找 `node` 在 `root` 的右子树中的双亲节点。

c++ 创建二叉树函数 二叉树查找指定结点的双亲和兄弟的函数 并用主函数测试

好的，我来为您介绍如何实现这个功能。

首先，我们需要定义二叉树的结构体，包括数据域和左右子树指针：

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;
}

其中，-1 表示空节点。

接下来，我们可以编写一个查找指定结点的双亲和兄弟的函数：

void findParentAndSibling(TreeNode* root, int target, TreeNode* parent, TreeNode* &sibling) {
    if (root == NULL || root->val == target) {
        return;
    }
    if (root->left != NULL && root->left->val == target) {
        parent = root;
        sibling = root->right;
        return;
    }
    if (root->right != NULL && root->right->val == target) {
        parent = root;
        sibling = root->left;
        return;
    }
    findParentAndSibling(root->left, target, root, sibling);
    findParentAndSibling(root->right, target, root, sibling);
}

其中，parent 和 sibling 都是引用类型，用于记录找到的双亲和兄弟结点。

最后，我们可以在主函数中测试这两个函数：

int main() {
    vector<int> nums = {1, 2, 3, -1, -1, 4, 5};
    TreeNode* root = buildTree(nums, 0);
    TreeNode* parent = NULL;
    TreeNode* sibling = NULL;
    findParentAndSibling(root, 4, parent, sibling);
    if (parent == NULL) {
        cout << "4 不在树中" << endl;
    } else {
        cout << "4 的双亲为 " << parent->val << endl;
        if (sibling == NULL) {
            cout << "4 没有兄弟" << endl;
        } else {
            cout << "4 的兄弟为 " << sibling->val << endl;
        }
    }
    return 0;
}

输出结果为：

4 的双亲为 2
4 的兄弟为 5

这样，我们就成功实现了创建二叉树的函数和查找指定结点的双亲和兄弟的函数，并用主函数测试了它们的功能。