正文

二叉搜索树 - 实现“搜索”功能

 2023-02-19  87

关键词：

【中文标题】二叉搜索树 - 实现“搜索”功能【英文标题】：Binary Search Tree - implementing a "search" function 【发布时间】：2019-02-20 21:49:38 【问题描述】：

我正在尝试实现二叉搜索树，但“搜索”函数为除根以外的每个条目返回错误值。

该函数应返回其值与键参数匹配的节点的地址，如果该节点不存在，则返回 NULL。

#include <iostream>
#include <string>
#include <vector>

using namespace std;
struct TreeNode 
    string data;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
;

int main()

    TreeNode* search(TreeNode* root, string key);
    TreeNode* insert(TreeNode* root, TreeNode* parent, string key);
    void delAll(TreeNode* root);

    vector<string> vals"yo", "check", "boy", "hope", "this", "doesn't", "break";
    TreeNode* root = NULL;

    // Build tree
    for (auto key : vals)
    
        root = insert(root, NULL, key);
    

    cout << endl;

    // Search for all keys
    for (auto key: vals)
    
        cout << key << " found at " << search(root, key) <<  endl;
    

    delAll(root);

    return 0;

void delAll(TreeNode* root)

    if (root == NULL)
        return;

    delAll(root->left);
    TreeNode* next = root->right;

    delete root;

    delAll(next);
 
TreeNode* search(TreeNode* root, string key)

    if (root == NULL)
        return NULL;
    if (root->data == key)
        return root;

    if (key < root->data)
        search(root->left, key);
    else
        search(root->right, key);

TreeNode* insert(TreeNode* root, TreeNode* parent, string key)


    if (!root)
    
        root = new TreeNode;
        root->data = key;
        root->left = NULL;
        root->right = NULL;
        root->parent = parent;
        cout << "Added \"" << key << "\" at " << root << endl;
    
    else if (key > root->data)
        root->right = insert(root->right, root, key);
    else
        root->left = insert(root->left, root, key);    

    return root;

当我运行代码时，我得到以下信息：

Added "yo" at 0x5574f9b94f60
Added "check" at 0x5574f9b953b0
Added "boy" at 0x5574f9b953f0
Added "hope" at 0x5574f9b95430
Added "this" at 0x5574f9b95470
Added "doesn't" at 0x5574f9b954b0
Added "break" at 0x5574f9b954f0

yo found at 0x5574f9b94f60
check found at 0x7ffe97caf730
boy found at 0x7ffe97caf730
hope found at 0x7ffe97caf730
this found at 0x7ffe97caf730
doesn't found at 0x7ffe97caf730
break found at 0x7ffe97caf730

我知道每个节点的“左”和“右”指针链接正确，因为“delAll”函数成功删除了所有节点。

将“cout”语句添加到“search”函数表明该函数似乎返回了正确的地址。为什么从 main 调用时会打印错误的地址？

【问题讨论】：

【参考方案1】：

你几乎拥有它。由于搜索函数是递归的，它必须返回它的结果。

TreeNode* search(TreeNode* root, string key)

    if (root == NULL)
        return NULL;
    if (root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);  // return this value
    else
        return search(root->right, key); // return this value
    return NULL; // never hit

【讨论】：

好答案。而且，如果正在使用一个体面的编译器，它应该警告函数中没有返回结果的代码路径。我拒绝评论编译器是否有缺陷或 OP 是否不明智地选择忽略此类警告 :-)

[c/c++]详解stl容器5--二叉搜索树的介绍及模拟实现(代码片段)

本文对二叉搜索树进行介绍，并对其核心功能进行了模拟实现。目录一、二叉搜索树的概念二、二叉搜索树操作1.二叉搜索树的查找2.二叉搜索树的插入3. 二叉搜索树的删除三、二叉搜索树的性能分析四、二叉搜索树的实现1.... 查看详情

二叉搜索树介绍与实现(代码片段)

二叉搜索树🎓概念🎓性质🎓二叉搜索树实现🎃二叉搜索树key模型🎃二叉搜索树插入🚀二叉搜索树查找⚽二叉搜索树遍历🥇二叉搜索树的判断🚀二叉搜索树删除🍤二叉搜索树的拷贝构造ǳ... 查看详情

二叉搜索树介绍与实现(代码片段)

二叉搜索树🎓概念🎓性质🎓二叉搜索树实现🎃二叉搜索树key模型🎃二叉搜索树插入🚀二叉搜索树查找⚽二叉搜索树遍历🚀二叉搜索树删除🎠二叉搜索树性能分析🎿二叉搜索树应用🎯注... 查看详情

二叉搜索树 - Java 实现

】二叉搜索树-Java实现【英文标题】：BinarySearchTree-JavaImplementation【发布时间】：2012-11-1406:07:06【问题描述】：我正在编写一个利用二叉搜索树来存储数据的程序。在之前的程序（无关）中，我能够使用JavaSE6提供的implementation实... 查看详情

二叉搜索树(代码片段)

文章目录二叉搜索树的概念二叉搜索树的实现结点类各函数接口总览+小技巧构造函数拷贝构造函数赋值运算符重载函数析构函数插入函数非递归实现递归实现删除函数非递归实现递归实现查找函数非递归实现递归实现二叉搜... 查看详情

python实现二叉搜索树_二叉搜索树(bst)---python实现

github：代码实现本文算法均使用python3实现1.二叉搜索树定义二叉搜索树(BinarySearchTree)，又名二叉排序树(BinarySortTree)。二叉搜索树是具有有以下性质的二叉树：(1)若左子树不为空，则左子树上所有节点的值均小于或... 查看详情

为啥用二叉搜索树实现哈希表？

】为啥用二叉搜索树实现哈希表？【英文标题】：WhyimplementaHashtablewithaBinarySearchTree?为什么用二叉搜索树实现哈希表？【发布时间】：2014-05-2415:47:05【问题描述】：在使用数组实现Hashtable时，我们继承了数组的常量时间索引。使... 查看详情

c++二叉搜索树解析(代码片段)

二叉搜索树概念二叉搜索树的概念（特征）二叉搜索树的性能分析操作查找插入删除模拟实现搜索二叉树类的构建查找操作实现插入操作实现删除操作实现递归版本二叉搜索树的应用K模型KV模型本文将介绍二叉搜索树ÿ... 查看详情

❤️数据结构入门❤️（2-1）-二叉搜索树

文章目录一、树的定义二、二叉树的定义三、二叉搜索树的定义四、二叉搜索树的图解五、二叉搜索树的实现1、二叉搜索树的插入2、二叉搜索树的删除3、二叉搜索树的修改4、二叉搜索树的查找六、二叉搜索树的刷题实战一、... 查看详情

二叉搜索树介绍和模拟实现(代码片段)

文章目录一.二叉搜索树概念二.二叉搜索树的模拟实现二叉搜索树的接口总览(1).构造函数(2).拷贝构造(3).赋值运算符重载(4).插入操作(5).查找操作(6).删除操作(6).析构函数三.二叉搜索树的应用一.二叉搜索树概念二叉搜索树又称二... 查看详情

二叉搜索树介绍和模拟实现(代码片段)

二叉搜索树思想java实现

二叉搜索树：一棵二叉搜索树是以一棵二叉树来组织的，这样一棵树可以使用链表的数据结构来表示（也可以采用数组来实现）。除了key和可能带有的其他数据外，每个节点还包含Left，Right，Parent，它们分别指节点的左孩子，右... 查看详情

[c/c++]详解stl容器4--二叉搜索树的介绍及模拟实现(代码片段)

[c/c++]详解stl容器5--二叉搜索树的介绍及模拟实现(代码片段)

二叉搜索树javascript实现

*什么是二叉搜索树？其形式就是二叉树，对于每个节点x，其左子树的值<=x.value，右子树的值>=x.value。*对于二叉搜索树，我们可以使用中序遍历，得到树上从小到大所有的元素。时间复杂度平均为O(n)。functioninorderTreeWalk(x){if... 查看详情

二叉搜索树的理解以及avl树的模拟实现(代码片段)

AVL树，全称平衡搜索二叉树。要认识AVL树，先认识二叉搜索树。目录二叉搜索树理解、认识二叉搜索树二叉搜索树的结构维护二叉搜索树的节点的类维护二叉搜索树的类二叉搜索树实现查找二叉搜索树的结构优势二叉搜... 查看详情

二叉搜索树的实现源码（源码较长，请慎入）(代码片段)

实现二叉搜索树的一种好方法是利用二叉树抽象数据类型。我们以BisTree这个名称来代表二叉搜索树这种数据结构。通过typedef方式将BisTree(二叉搜索树)实现为BiTree（二叉树）的别名。采用typedef方法使得二叉搜索树具有了某种程度... 查看详情

二叉搜索树rust实现(代码片段)

二叉搜索树二叉搜索树是一颗二叉树每个节点应该包含三个属性left,right,p,根节点p为NIL设x是二叉搜索树的一个节点,y是x左子树的一个节点,那么y.key<=x.key,若y是x右子树的一个节点,那么y.key>=x.key遍历遍历分前中后,以根节点的遍... 查看详情