二叉查找树的级序遍历

Question

我试图使用队列的链表实现实现二叉搜索树的级别顺序遍历。

我已经检查了二叉查找树的实现，它是好的。队列的链表实现也是正确的。在这里，我试图访问节点并将其子节点排队。然后使用弹出函数实际访问节点。

这最终是通过递归调用完成的。当我运行以下代码时，我以不同的顺序获得输出。

// 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();
}
}

Answer 1

现在，你从头部插入，然后从头部取出。这意味着你有一个堆栈(后进先出)，而不是队列(先进先出)。

添加尾部指针，然后从添加的另一端删除。如果在头部添加，请从尾部删除，反之亦然。