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

Question

我已经使用类和递归在 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 个 1)

Answer 1

看看你的显示函数:

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 这个函数:

If we're on the lowest row of the tree, just return instead of displaying it.

Else, display out two children on the row below us, and then have them display their children.

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

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

最后:为什么要用 6 的深度进行测试？如果我每次运行程序进行测试时都必须数那么多 1，我敢肯定我会在一个小时内把头发拔出来。从深度为 1 的树开始(您当前的代码应该会失败!)。如果可行，请转到深度 2。最多我会测试深度 3。毕竟，深度 6 与深度 3 的情况可能根本没有什么不同!