1 узел, появляющийся меньше в рекурсивной реализации Tree в C ++ - PullRequest
Новая
       21

1 узел, появляющийся меньше в рекурсивной реализации Tree в C ++

0 голосов
/ 10 января 2019

Я создал реализацию полного бинарного дерева в C ++, используя класс и рекурсию. На глубине = 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);
}

Выход: 11111111111111111111111111111111111111111111111111111111111111111111111111 (62 1 с)

1 Ответ

0 голосов
/ 10 января 2019

Посмотрите на функцию отображения: 

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;
        }
    }
};

Давай Резину Даки эту функцию:

Если мы находимся в самом нижнем ряду дерева, просто вернемся вместо его отображения.

Иначе, покажите двух детей в ряду ниже нас, а затем попросите их показать своих детей.

Это ... интересный способ написания отображения для дерева. Я настоятельно рекомендую просто распечатать узел, на котором вы находитесь, и затем позволить его дочерним элементам печатать самим. Этот запутанный способ печати детей сам по себе является причиной вашей проблемы. В конце концов, чей корневой узел является дочерним? Никто! Так, кто печатает корневой узел? Никто !!

В дополнение к этому, вам действительно действительно нужно установить указатели left и right в ваших узлах. На данный момент у вас есть куча диких указателей. Я бы предложил добавить конструктор в ваш класс узлов, чтобы сделать это для вас.

И, наконец: почему вы тестируете с глубиной 6? Если бы мне приходилось считать столько единиц каждый раз, когда я запускал программу для проверки, я почти уверен, что вырву свои волосы в течение часа. Начните с дерева глубины 1 (которое не должно соответствовать вашему текущему коду!). Если это сработает, перейдите на глубину 2. Максимум я бы проверил на глубине 3. В конце концов, случай глубины 6 против 3, вероятно, совсем не отличается!

...