обход уровня двоичного дерева по очереди - PullRequest
Новая
       17

обход уровня двоичного дерева по очереди

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

Я пытаюсь выполнить обход уровня порядка, используя очередь.но печатается только первое значение, т. е. 10. После этого вызывается функция dequeue (), но все равно значения не печатаются.Очевидно, есть некоторая проблема с функцией dequeue ().пожалуйста, помогите.

все функции работают. 

            #include<stdio.h>
            #include<stdlib.h>
            #define max 100
            int a[max];
            int front=-1;
            int rear=-1;
            struct node
            {
                int data;
                struct node *left, *right;
            };
            struct node *newNode(int data)
            {
                struct node *nn;
                nn=(struct node *)malloc(sizeof(struct node));
                if(!nn)
                    return;
                nn->data=data;
                nn->left=nn->right=NULL;
                return nn;
            };
            void enqueue(struct node *root)
            {
                a[++rear]=root;
                front++;
            }
            struct node *dequeue()
            {
                printf("inside dequeue\n");
                struct node *temp;
                temp=a[front];
                front++;
                return temp;
            }
            int isempty(){
                return(front==-1);
            }
            void levelorder(struct node *root)
            {
                struct node *temp=NULL;
                if(!root)
                    return;
                enqueue(root);
                while(!isempty())
                {
                    temp=dequeue();
                    printf("%d\t",temp->data);
                    if(temp->left)
                        enqueue(temp->left);
                    if(temp->right)
                        enqueue(temp->right);
                }
            }
            int main()
            {
                int data;
                struct node *root=newNode(10);
                root->left = newNode(11);
                root->left->left = newNode(7);
                root->right = newNode(9);
                root->right->left = newNode(15);
                root->right->right = newNode(8);
                levelorder(root);
                return 0;
            }

1 Ответ

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

Я думаю, в вашей логике есть какая-то ошибка в реализации очереди. Я могу дать вам несколько советов. 

        int front=0,rear=0;

        void enqueue(struct node *root)
        {
            a[rear]=root;
            rear++;
        }

        struct node *dequeue()
        {
            //handle case where queue is empty
            printf("inside dequeue\n");
            struct node *temp;
            temp=a[front];
            front++;
            return temp;
        }

        int isEmpty(){
            return(front==rear);
        }

Чтобы сделать его более надежным с размером массива, вы должны использовать функцию модуля с такими индексами. 

        int front=0,rear=0;

        void enqueue(struct node *root)
        {
            a[rear%max]=root;
            rear++;
        }

        struct node *dequeue()
        {
            //handle case where queue is empty
            printf("inside dequeue\n");
            struct node *temp;
            temp=a[front%max];
            front++;
            return temp;
        }

        int isEmpty(){
            return(front==rear);
        }
...