草庐IT

c++ - 遍历 BST 时出现 Stackoverflow 异常

coder 2024-02-16 原文

我已经在 C++ 中为我的一项作业实现了基于链接的 BST(二叉搜索树)。我已经编写了我的整个类(class)并且一切正常，但我的作业要求我绘制运行时间:

a.  A sorted list of 50000, 75000, and 100000 items
b.  A random list of 50000, 75000, and 100000 items

没关系，我可以插入数字，但它还要求我调用树上的 FindHeight() 和 CountLeaves() 方法。我的问题是我已经使用 recursion 实现了这两个函数。因为我有一个如此大的数字列表，所以我遇到了一个 stackoverflow 异常。

这是我的类定义:

template <class TItem>
class BinarySearchTree
{
public:
    struct BinarySearchTreeNode
    {
    public:
        TItem Data;
        BinarySearchTreeNode* LeftChild;
        BinarySearchTreeNode* RightChild;
    };

    BinarySearchTreeNode* RootNode;

    BinarySearchTree();
    ~BinarySearchTree();

    void InsertItem(TItem);

    void PrintTree();
    void PrintTree(BinarySearchTreeNode*);

    void DeleteTree();
    void DeleteTree(BinarySearchTreeNode*&);

    int CountLeaves();
    int CountLeaves(BinarySearchTreeNode*);

    int FindHeight();
    int FindHeight(BinarySearchTreeNode*);

    int SingleParents();
    int SingleParents(BinarySearchTreeNode*);

    TItem FindMin();
    TItem FindMin(BinarySearchTreeNode*);

    TItem FindMax();
    TItem FindMax(BinarySearchTreeNode*);
};

FindHeight() 实现

template <class TItem>
int BinarySearchTree<TItem>::FindHeight()
{
    return FindHeight(RootNode);
}

template <class TItem>
int BinarySearchTree<TItem>::FindHeight(BinarySearchTreeNode* Node)
{
    if(Node == NULL)
        return 0;

    return 1 + max(FindHeight(Node->LeftChild), FindHeight(Node->RightChild));
}

CountLeaves() 实现

template <class TItem>
int BinarySearchTree<TItem>::CountLeaves()
{
    return CountLeaves(RootNode);
}

template <class TItem>
int BinarySearchTree<TItem>::CountLeaves(BinarySearchTreeNode* Node)
{
    if(Node == NULL)
        return 0;
    else if(Node->LeftChild == NULL && Node->RightChild == NULL)
        return 1;
    else
        return CountLeaves(Node->LeftChild) + CountLeaves(Node->RightChild);
}

我试图思考如何在不递归的情况下实现这两种方法，但我完全被难住了。有人有什么想法吗？

最佳答案

在一个有100,000个节点的树上递归应该不是问题，如果它是平衡的。深度可能只有 17，这在所示的实现中不会使用太多堆栈。 (log2(100,000) = 16.61)。所以看起来可能构建树的代码没有正确平衡它。

关于c++ - 遍历 BST 时出现 Stackoverflow 异常，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8073362/

时出StackoverflowBinarySearchTreeNodecodeTItemc++recursionstack-overflowbinary-search-tree

有关c++ - 遍历 BST 时出现 Stackoverflow 异常的更多相关文章

  1. ruby - ECONNRESET (Whois::ConnectionError) - 尝试在 Ruby 中查询 Whois 时出错 - 2

    我正在用Ruby编写一个简单的程序来检查域列表是否被占用。基本上它循环遍历列表，并使用以下函数进行检查。require'rubygems'require'whois'defcheck_domain(domain)c=Whois::Client.newc.query("google.com").available?end程序不断出错(即使我在google.com中进行硬编码)，并打印以下消息。鉴于该程序非常简单，我已经没有什么想法了-有什么建议吗？/Library/Ruby/Gems/1.8/gems/whois-2.0.2/lib/whois/server/adapters/base.

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  4. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  5. ruby-on-rails - Rails - 乐观锁定总是触发 StaleObjectError 异常 - 2

    我正在学习Rails，并阅读了关于乐观锁的内容。我已将类型为integer的lock_version列添加到我的articles表中。但现在每当我第一次尝试更新记录时，我都会收到StaleObjectError异常。这是我的迁移:classAddLockVersionToArticle当我尝试通过Rails控制台更新文章时:article=Article.first=>#我这样做:article.title="newtitle"article.save我明白了:(0.3ms)begintransaction(0.3ms)UPDATE"articles"SET"title"='dwdwd

  6. 使用 ACL 调用 upload_file 时出现 Ruby S3 "Access Denied"错误 - 2

    我正在尝试编写一个将文件上传到AWS并公开该文件的Ruby脚本。我做了以下事情:s3=Aws::S3::Resource.new(credentials:Aws::Credentials.new(KEY,SECRET),region:'us-west-2')obj=s3.bucket('stg-db').object('key')obj.upload_file(filename)这似乎工作正常，除了该文件不是公开可用的，而且我无法获得它的公共(public)URL。但是当我登录到S3时，我可以正常查看我的文件。为了使其公开可用，我将最后一行更改为obj.upload_file(file

  7. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  8. ruby - 在 Ruby 中重新分配常量时抛出异常？ - 2

    我早就知道Ruby中的“常量”(即大写的变量名)不是真正常量。与其他编程语言一样，对对象的引用是唯一存储在变量/常量中的东西。(侧边栏:Ruby确实具有“卡住”引用对象不被修改的功能，据我所知，许多其他语言都没有提供这种功能。)所以这是我的问题:当您将一个值重新分配给常量时，您会收到如下警告:>>FOO='bar'=>"bar">>FOO='baz'(irb):2:warning:alreadyinitializedconstantFOO=>"baz"有没有办法强制Ruby抛出异常而不是打印警告？很难弄清楚为什么有时会发生重新分配。 最佳答案

  9. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  10. SPI接收数据异常问题总结 - 2

    SPI接收数据左移一位问题目录SPI接收数据左移一位问题一、问题描述二、问题分析三、探究原理四、经验总结最近在工作在学习调试SPI的过程中遇到一个问题——接收数据整体向左移了一位（1bit）。SPI数据收发是数据交换，因此接收数据时从第二个字节开始才是有效数据，也就是数据整体向右移一个字节（1byte）。请教前辈之后也没有得到解决，通过在网上查阅前人经验终于解决问题，所以写一个避坑经验总结。实际背景：MCU与一款芯片使用spi通信，MCU作为主机，芯片作为从机。这款芯片采用的是它规定的六线SPI，多了两根线：RDY和INT，这样从机就可以主动请求主机给主机发送数据了。一、问题描述根据从机芯片手

随机推荐