jjzjj

c++ - 在二叉树中，找出有多少祖父只有两个或三个孙子

coder 2024-02-04 原文 

                                   8
                                /      \
                              4         12
                             / \         / \
                           3    6       2   1
                          / \   / \    /   / \
                         7  10 13 15  5   9  11
                                             /
                                            14

我需要找到一棵树的祖父，在这个例子中我只有一个祖父，12 号(我需要他只有两个或三个孙子)。

这是我到目前为止尝试过的:

int T(struct node * tree){
    int t = 0;
    if (tree == NULL)
        return 0;
    if (tree->left && tree->right)
    {    //In this case i check if we NOT have all the four grandchildrens.
        if (!((tree->left->left) && (tree->left->right) && (tree->right->left) && (tree->right->right)))
        {
            t =  1 + T(tree->left) + T(tree->right);
            T(tree->left);
            T(tree->right);

        }
        else
       {
            T(tree->left);
            T(tree->right);
        }

    }

    return t;

}

不幸的是，它不起作用...有人可以帮我解决这个问题吗？

最佳答案

一种有效的方法是递归地返回一对结果。在 C++ 中有更优雅的方法来返回一对，但我将使用旧的笨拙的 C 方法通过指针输入返回一个输出:

int T2(struct node * tree, int* child_count)
{
    int t = 0;  // Count the things we are supposed to count
    int g = 0;  // Count grandchildren of the current node
    if (tree == NULL)
        return 0;
    if ( tree->left )
    {
       ++ *child_count;
       t += T2( tree->left, &g );
    }
    if ( tree->right )
    {
       ++ *child_count;
       t += T2( tree->right, &g );
    }
    if ( g==2 || g==3 )
       ++t;
    return t; 
}

int T(struct node * tree) {int dummy; return T2(tree, &dummy); }

这个函数同时做了两件事。简单的工作是它通过递增 *child_count 来帮助计算其 parent 的孙子，它还通过在 t 中累加来递归地完成主要工作。

下面的方式可能更容易理解，但不够优雅:

int T(struct node * tree)
{
    struct node *c;
    int t = 0;  // Count the things we are supposed to count
    int g = 0;  // Count grandchildren of the current node
    if (tree == NULL)
        return 0;
    if ( (c=tree->left) != NULL )
    {
       g += (c->left != NULL) + (c->right != NULL);
       t += T( c );
    }
    if ( (c=tree->right) != NULL )
    {
       g += (c->left != NULL) + (c->right != NULL);
       t += T( c );
    }
    if ( g==2 || g==3 )
       ++t;
    return t; 
}

关于c++ - 在二叉树中，找出有多少祖父只有两个或三个孙子，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34483586/

孙子amptreerightgtc++cbinary-tree

有关c++ - 在二叉树中，找出有多少祖父只有两个或三个孙子的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

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

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

  3. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  4. ruby - 可以通过多少种方法将方法添加到 ruby​​ 对象？ - 2

    当谈到运行时自省(introspection)和动态代码生成时，我认为ruby​​没有任何竞争对手，可能除了一些lisp方言。前几天，我正在做一些代码练习来探索ruby​​的动态功能，我开始想知道如何向现有对象添加方法。以下是我能想到的3种方法:obj=Object.new#addamethoddirectlydefobj.new_method...end#addamethodindirectlywiththesingletonclassclass这只是冰山一角，因为我还没有探索instance_eval、module_eval和define_method的各种组合。是否有在线/离线资

  5. 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.你能做的最好的事情是:

  6. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  7. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  8. ruby - 使用 Ruby，计算 n x m 数组的每一列中有多少个 true 的简单方法是什么？ - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true？”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组，其中每个子数组代表一列，然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本，应该在1.8.6上运行，没有任何依赖:arr.transpose.map{|subarr|subarr.in

  9. ruby-on-rails - 只有当不是 nil 时才执行映射？ - 2

    如果names为nil，则以下中断。我怎样才能让这个map只有在它不是nil时才执行？self.topics=names.split(",").mapdo|n|Topic.where(name:n.strip).first_or_create!end 最佳答案 其他几个选项:选项1(在其上执行map时检查split的结果):names_list=names.try(:split,",")self.topics=names_list.mapdo|n|Topic.where(name:n.strip).first_or_create!e

  10. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

随机推荐