Я не могу выяснить причину аварийного завершения при выполнении функции levelOrder? - PullRequest
Новая
       18

Я не могу выяснить причину аварийного завершения при выполнении функции levelOrder?

0 голосов
/ 05 июня 2019

Этот код предназначен для реализации двоичного дерева.Она состоит из insertNode (функция, которая вставляет узел в дерево) и levelOrder (функция, которая пересекает двоичное дерево в порядке уровней).

Функция insertNode работает нормально, но при выполнении levelOrder она успешно отображает данные, но после этого онаперестает работать и показывает, что программа перестала работать.

Я не могу найти, где я иду не так?Заранее спасибо {:) 

#include<iostream>
using namespace std;

struct Node
{
    Node *left;
    Node *right;
    int data;
}*root;

struct Queue
{

    Node *p[1000];
    int index=-1;

    Node *add(Node *ptr)
    {
        p[++index]=ptr;
        return ptr;
    }
    Node *peek()
    {
        if(index==-1)
            return NULL;

        return p[0];    
    }
    Node *pop()
    {
        if(index==-1)
            return NULL;

        Node *temp=p[0];

        for(int i=0;i<index;i++)
            p[i]=p[i+1];

        index--;

        return temp;

    }
};

Node * createNode(int data)
{
    Node *p=new Node();
    p->data=data;
    p->left=p->right=NULL;

    return p;
}

///////Insertion Of Node////////

int insertNode(int val)
{
    if(root==NULL)
    {
        root=createNode(val);
        return val;
    }

    bool found=false;
    Node *p;

    Queue q;
    q.add(root);
    while(found==false)
    {
        Node *l=(q.peek())->left;
        Node *r=(q.peek())->right;

        if(l==NULL)
        {
            (q.peek())->left=createNode(val);
            found=true;
            return val;
        }
        else
            q.add(l);

        if(r==NULL)
        {
            q.peek()->right=createNode(val);
            found=true;
            return val;
        }
        else
            q.add(r);


        q.pop();

    }
        return val;

}
/////////Traversal's///////////
void levelOrder(Node *p)
{
    if(p==NULL)
        return;

    Queue q;
    q.add(p);

    while(true)
    {
        cout<<q.peek()->data<<" ";

        if(q.peek()->left!=NULL)
            q.add(q.peek()->left);

        if(q.peek()->right!=NULL)
            q.add(q.peek()->right);

        if(q.pop()==NULL)
            return;
    }

}


int main()
{
    root=NULL;

    insertNode(1);
    insertNode(2);
    insertNode(3);
    insertNode(4);

    levelOrder(root);


    return 0;
}

1 Ответ

1 голос
/ 05 июня 2019

После того, как вы вытолкнули последний элемент из очереди, вы q.peek()->data на следующей итерации, когда q.peek() не является действительным указателем.

Измените условие расторжения: 

while (q.peek())
{
    cout<<q.peek()->data<<" "<< endl;;

    if(q.peek()->left!=NULL)
        q.add(q.peek()->left);

    if(q.peek()->right!=NULL)
        q.add(q.peek()->right);

    q.pop();
}

Кстати, это одна ситуация, когда переменная "loop-local" может улучшить читаемость - все эти peek s добавляют беспорядок: 

while(Node *next = q.pop())
{
    cout<<next->data<<" "<< endl;;

    if(next->left != nullptr)
        q.add(next->left);

    if(next->right != nullptr)
        q.add(next->right);
}
...