Уровень порядка обхода бинарного дерева поиска - PullRequest
Новая
       7

Уровень порядка обхода бинарного дерева поиска

0 голосов
/ 16 октября 2019

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

Я проверил реализацию дерева двоичного поиска, и это нормально. Реализация очереди в связанном списке также корректна. Здесь я пытаюсь посетить узел и поставить его детей в очередь. а затем используйте функцию pop для фактического посещения узла.

Это делается с помощью рекурсивного вызова в конце. Когда я запускаю следующий код, я получаю вывод в другом порядке. 

// Trees
#include <stdio.h>
#include <stdlib.h>

//Node declaration for binary search tree

struct node 
{
int data;
struct node *left;
struct node *right;
};


// LINKED LIST BASED IMPLEMENTATION OF QUEUE

struct qnode 
{
struct node *data;
struct qnode *next;
};



struct qnode *head = NULL;


void insertq (struct node *);   //This function enqueue node in the queue.

struct node *pop ();        // dequeue  function

//The function declaration for level order traversal.

void leorder ();



struct node *make (int);
struct node *insert (struct node *, int);



void 
main () 
{



struct node *root = NULL;


root = insert (root, 10);


root = insert (root, 9);


root = insert (root, 8);


root = insert (root, 5);


root = insert (root, 2);


root = insert (root, 4);


root = insert (root, 3);


root = insert (root, 6);


root = insert (root, 7);


root = insert (root, 1);


insertq (root);     //Insertion of first root.


leorder ();


} 

//The program that makes nodes for the bst.

struct node* make(int x){
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;

return temp;
};




//The node insertion function.(BINARY SEARCH TREE)

struct node* insert(struct node* root,int x){
if(root == NULL){
    root = make(x);
}
else{
if(x <= root->data){
    root->left = insert(root->left,x);
}

else{
    root->right = insert(root->right,x);
}}
return root;
}




// This function will insert node in the queue.

void insertq(struct node* x){

if(head == NULL){
struct qnode* temp = (struct qnode*)malloc(sizeof(struct qnode));
temp->data = x;
temp->next = NULL;
head = temp;
}
else{
struct qnode* temp = (struct qnode*)malloc(sizeof(struct qnode));
temp->data = x;
temp->next = head;
head = temp;
}
}

struct node* pop(){
struct node* r;
if(head == NULL){
    return NULL;
}
else{
 struct qnode* pt;
 pt = head;
 head = head->next;
 r = pt->data;
 free(pt);
 return r;
}
}


// dequeue function.

struct node* pop(){
struct node* r;
if(head == NULL){
    return NULL;
}
else{
 struct qnode* pt;
 pt = head;
 head = head->next;
 r = pt->data;
 free(pt);
 return r;
}
}



// Function to print tree in level order.

void leorder(){
struct node* popped;
popped = pop();
printf("%d ",popped->data);
if(popped != NULL){
    if(popped->left != NULL){
        insertq(popped->left);
    }

    if(popped->right != NULL){
        insertq(popped->right);
    }
    leorder();
}
}

1 Ответ

0 голосов
/ 16 октября 2019

Прямо сейчас вы вставляете в голову, и вы удаляете в голове. Это означает, что у вас есть стек (последний пришел, первый вышел), а не очередь (первый пришел, первый вышел).

Добавьте указатель tail и удалите его с противоположного конца, который вы добавляете. Если вы добавляете в голову, снимите с хвоста или наоборот.

...