树形结构的3中搜索方式示例分享

在树形结构中，常见的搜索方式主要包括以下几种。以下是这些搜索方式的示例分享，旨在以简洁、高效的方式展示它们的实现逻辑。

### 1. 二叉树搜索

二叉树搜索是最基础也是最常用的树形搜索方式之一。在二叉树中，每个节点最多有两个子节点，通常称为左子节点和右子节点。搜索时，从根节点开始，根据目标值与节点值的比较结果决定向左子树还是右子树搜索，直至找到目标值或搜索到叶子节点为止。

**示例代码**（假设为二叉搜索树，即左子树所有节点值小于根节点值，右子树所有节点值大于根节点值）：

#include <iostream>
using namespace std;

// 假设二叉树节点的定义如下
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉树搜索函数
TreeNode* searchBST(TreeNode* root, int target) {
    if (root == nullptr || root->val == target) {
        return root;
    }
    if (target < root->val) {
        return searchBST(root->left, target);
    } else {
        return searchBST(root->right, target);
    }
}

int main() {
    // 示例用法
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(8);

    int target = 3;
    TreeNode* result = searchBST(root, target);
    if (result != nullptr) {
        cout << "Found: " << result->val << endl;
    } else {
        cout << "Not found." << endl;
    }

    // 释放内存（略）
    return 0;
}

### 2. 满m叉树搜索

满m叉树是每一层节点都达到最大节点数的m叉树。搜索时，从根节点开始，依次遍历每一层的节点，直到找到目标值或遍历完所有节点。

**示例逻辑**（由于满m叉树的结构较为特殊，且具体实现可能依赖于具体的应用场景，此处仅描述逻辑）：

- 从根节点开始，记录当前深度`depth`。

- 在当前深度下，遍历该层的所有节点（数量为m的`depth`次方）。

- 如果找到目标值，则返回该节点；否则，如果已遍历完当前层的所有节点且未达到树的最大深度，则`depth`加1，继续搜索下一层。

### 3. 子集树（全排列树）搜索

子集树（也称为全排列树）用于生成一个集合的所有子集或全排列。搜索时，通常使用深度优先搜索（DFS）来遍历所有可能的子集或排列。

**示例代码**（以生成集合的所有子集为例）：

#include <iostream>
#include <vector>
using namespace std;

void generateSubsets(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
    result.push_back(current); // 将当前子集加入结果集
    for (int i = start; i < nums.size(); ++i) {
        current.push_back(nums[i]); // 选择当前元素
        generateSubsets(nums, i + 1, current, result); // 递归生成后续子集
        current.pop_back(); // 回溯，撤销选择
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    generateSubsets(nums, 0, current, result);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> subsets = subsets(nums);
    for (const auto& subset : subsets) {
        for (int num : subset) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

以上示例展示了树形结构中三种