时间戳

首页 > 解决方案 > 1 个节点在 C++ 中树的递归实现中出现较少

c++ - 1 个节点在 C++ 中树的递归实现中出现较少

问题描述

我使用类和递归在 C++ 中创建了一个完整二叉树的实现。在 depth = 6 时，它应该有 63 个节点。但在输出中我只能看到 62 个节点。有人可以指出问题吗？

class node{
public:
    node *left, *right, *root, *it;
    int data,m;

void create(){
        root = new node;
        it = root;
        root->data = 1;
        const int n = 6;          // Depth to be passed                     
        addchildren(root,n); }

void addchildren(node *x,int z)   // Recursion (z = No. of levels)
    {

        if (z==1)
            return;
        else
        {
            it->left = new node;
            it->left->data = 1;
            it->right = new node;
            it->right->data = 1;
            addchildren(it->left,z-1);
            addchildren(it->right,z-1);
            return;
        }
    }

void display(node *x,int z) 
    {

        if (z==1)
            return;
        else
        {
            cout<<it->left->data;
            cout<<it->right->data;
            display(it->left,z-1);
            display(it->right,z-1);
            return;
        }
    }
};
int main()
{
    node A;
    A.create();
    A.display(A.root,6);
}

输出：1111111111111111111111111111111111111111111111111111111111111（62 1s）

标签： c++recursiondata-structurestreebinary-tree

解决方案

看看你的显示功能：

void display(node *x,int z) {
        if (z==1)
            return;
        else
        {
            cout<<it->left->data;
            cout<<it->right->data;
            display(it->left,z-1);
            display(it->right,z-1);
            return;
        }
    }
};

让我们使用 Rubber Ducky 这个功能：

如果我们在树的最低行，只需返回而不是显示它。

否则，在我们下面一行展示两个孩子，然后让他们展示他们的孩子。

这是为树编写显示的一种……有趣的方式。我强烈建议只打印您当前所在的节点，然后让其子节点自行打印。这种自己打印孩子的复杂方式导致了您的问题。毕竟，谁是根节点的孩子？没有人！那么谁打印根节点呢？没有人！！

除此之外，你真的真的真的需要在你的节点中设置left和right指针。到目前为止，您有一堆疯狂的指针。我建议向您的节点类添加一个构造函数来为您执行此操作。

最后：为什么要使用深度 6 进行测试？如果我每次运行程序进行测试时都必须数那么多 1，我很确定我会在一个小时内把头发拉出来。从深度为 1 的树开始（您当前的代码应该会失败！）。如果可行，请进入 2 的深度。我最多以 3 的深度进行测试。毕竟，深度 6 与 3 的情况可能完全不同！

推荐阅读