问题：

队列陷入无限循环的二叉树层次顺序遍历

秦弘亮

2023-03-14

我一直在尝试用C语言实现带有队列的二叉树，我对这种语言相当陌生。我一直在尝试调试我用C编写的代码，从头开始编写代码，但没有结果。我看不出我做错了什么。

我检查了用整数数据编写的队列代码，它运行得很好。

enqueue 函数推送队列中的元素
取消排队函数从队列中弹出元素
函数检查队列是否为空

然后我实现了二叉搜索树，并在节点中打印了元素

root -> left -> left -> left -> data; //worked fine, was able to reach the extreme left leaf node

和

根-

再进行一些类似这样的遍历，树看起来很好。我在level_order（）函数中打印了队列，我能理解的是队列没有正确构建。不知怎的，整个事情进入了无限循环。我没什么主意了。这是密码，谢谢。

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

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

struct Queue{
    struct BstNode *address;
    struct Queue *next;
};

struct Queue *front = NULL;
struct Queue *back = NULL;

struct Queue* create_queue(BstNode **address){
    struct Queue *temp = (Queue*)malloc(sizeof(struct Queue));
    temp -> next = NULL;
    temp -> address = *address;
    return temp;
}

void enqueue(BstNode **address){
    struct Queue *temp = create_queue(address);
    if(front == NULL && back == NULL){
        front = back = temp;
    }
    else{
        temp -> next = back;
        back = temp;
    }
}

void dequeue(){
    if(front == NULL){
        return;
    }
    struct Queue* temp;
    temp = back;
    if(front == back){
        front = back = NULL;
    }
    else{
        back = back -> next;
    }
    free(temp);
}

bool empty(){
    if(front == NULL){
        return true;
    }
    return false;
}

void print_queue(){
    struct Queue *temp = back;
    while(temp != NULL){
        printf("%d", temp->address->data);
        temp = temp -> next;
    }
    printf("\n");
}

struct BstNode *root;

struct BstNode *create_node(int data){
    struct BstNode *temp = (BstNode *)malloc(sizeof(struct BstNode));
    temp -> data = data;
    temp -> left = NULL;
    temp -> right = NULL;
    return temp;
}

void insert_bst_cell(BstNode **node, int data){
    if((*node) == NULL){
        struct BstNode* temp = create_node(data);
        *node = temp;
    }
    else if(data > (*node)->data){
        insert_bst_cell(&(*node)->right, data);
    }
    else if(data < (*node)->data){
        insert_bst_cell(&(*node)->left, data);
    }
}

BstNode *first_element(){
    return front->address;
}

void level_order(){
    if(root == NULL) return;
    enqueue(&root);
    while(!(empty())){
        struct BstNode *current = first_element();
        dequeue();
        printf("%d\n", current->data);
        if(current->right != NULL){
            enqueue(&(current->left));
        }
        if(current->left != NULL){
            enqueue(&(current->right));
        }
    }
}

int main(int argc, char **argv)
{
    front = NULL;
    back = NULL;
    root = NULL;
    insert_bst_cell(&root, 15);
    insert_bst_cell(&root, 10);
    insert_bst_cell(&root, 20);
    insert_bst_cell(&root, 5);
    insert_bst_cell(&root, 11);
    insert_bst_cell(&root, 17);
    insert_bst_cell(&root, 25);
    insert_bst_cell(&root, 4);
    insert_bst_cell(&root, 6);
    insert_bst_cell(&root, 9);
    insert_bst_cell(&root, 12);
    insert_bst_cell(&root, 16);
    insert_bst_cell(&root, 19);
    insert_bst_cell(&root, 21);
    insert_bst_cell(&root, 35);
    level_order();
    return 0;
}

共有1个答案

李文轩

2023-03-14

感谢Paul Georg Podlech指出我实现了堆栈而不是队列。另一个错误是

if(current->right != NULL){
    enqueue(&(current->left));
}
if(current->left != NULL){
    enqueue(&(current->right));
}

在这个特定的代码中。应该是

if(current->left != NULL){    //current -> right in previous snippet
    enqueue(&(current->left));  
}
if(current->right != NULL){    //current -> left in previous snippet
    enqueue(&(current->right));
}

为了以防万一，我将发布工作代码

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

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

struct Queue{
    struct BstNode *address;
    struct Queue *next;
};

struct Queue *front = NULL;
struct Queue *back = NULL;

struct Queue* create_queue(BstNode **address){
    struct Queue *temp = (Queue*)malloc(sizeof(struct Queue));
    temp -> next = NULL;
    temp -> address = *address;
    return temp;
}

void enqueue(BstNode **address){
    struct Queue *temp = create_queue(address);
    if(front == NULL && back == NULL){
        front = back = temp;
    }
    else{
//        temp -> next = back;
        back -> next = temp;
        back = temp;
    }
}

void dequeue(){
    if(front == NULL){
        return;
    }
    struct Queue* temp;
    temp = front;
    if(front == back){
        front = back = NULL;
    }
    else{
        front = front -> next;
    }
    free(temp);
}

bool empty(){
    if(front == NULL){
        return true;
    }
    return false;
}

void print_queue(){
    struct Queue *temp = back;
    while(temp != NULL){
        printf("%d", temp->address->data);
        temp = temp -> next;
    }
    printf("\n");
}

struct BstNode *root;

struct BstNode *create_node(int data){
    struct BstNode *temp = (BstNode *)malloc(sizeof(struct BstNode));
    temp -> data = data;
    temp -> left = NULL;
    temp -> right = NULL;
    return temp;
}

void insert_bst_cell(BstNode **node, int data){
    if((*node) == NULL){
        struct BstNode* temp = create_node(data);
        *node = temp;
    }
    else if(data > (*node)->data){
        insert_bst_cell(&(*node)->right, data);
    }
    else if(data < (*node)->data){
        insert_bst_cell(&(*node)->left, data);
    }
}

BstNode *first_element(){
    return front->address;
}

void level_order(){
    if(root == NULL) return;
    enqueue(&root);
    while(!(empty())){
        struct BstNode *current = first_element();
        dequeue();
        printf("%d\n", current->data);
        if(current->left != NULL){
            enqueue(&(current->left));
        }
        if(current->right != NULL){
            enqueue(&(current->right));
        }
    }
}

int main(int argc, char **argv)
{
    front = NULL;
    back = NULL;
    root = NULL;
    insert_bst_cell(&root, 15);
    insert_bst_cell(&root, 10);
    insert_bst_cell(&root, 20);
    insert_bst_cell(&root, 5);
    insert_bst_cell(&root, 11);
    insert_bst_cell(&root, 17);
    insert_bst_cell(&root, 25);
    insert_bst_cell(&root, 4);
    insert_bst_cell(&root, 6);
    insert_bst_cell(&root, 9);
    insert_bst_cell(&root, 12);
    insert_bst_cell(&root, 16);
    insert_bst_cell(&root, 19);
    insert_bst_cell(&root, 21);
    insert_bst_cell(&root, 35);
    level_order();
    return 0;
}

感谢大家宝贵的时间和投入。

类似资料：

二叉树的层次顺序遍历

我想对二叉树执行级别顺序遍历。因此，对于给定的树，说：产出将是：我知道我可以使用某种队列，但在C中递归地实现这一点的算法是什么？感谢您的帮助。
二叉树到堆树的转换-陷入无限循环

给定一棵树，其中左和右子树是min堆，但根节点不维护min堆属性。您的代码应该修改根植于node*n的树，使其成为一个最小堆。（这意味着您需要满足min heap属性：节点的值等于它的一个子节点或两个子节点都是可以的，但节点的值不能大于它的任何一个子节点。您不必试图平衡树或使其成为完整的树。）请建议我缺少什么。我觉得我把它弄得太复杂了。此外，我没有任何其他函数，如swap将二叉树转换为堆MIN。
二叉树层次遍历

主要内容：层次遍历的实现过程,实现代码前边介绍了二叉树的先序、中序和后序的遍历算法，运用了栈的数据结构，主要思想就是按照先左子树后右子树的顺序依次遍历树中各个结点。本节介绍另外一种遍历方式：按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层
java中二叉搜索树的层次顺序遍历

我已经为我的二叉搜索树做了4次不同的遍历。我被困在最后一个，这是水平顺序遍历，我不能得到，似乎找到如何做它正确。主要的问题是我不知道如何一次只搜索一个层次，我只知道如何搜索整个左或整个右子树。
使用队列的非二叉树中的BFS/级顺序遍历

我必须创建两个类:NonBinaryTree和SingleNode类，包含一些处理节点和整个树的方法(在NonBinaryTree类中)。我在使用队列(先进先出类型)实现非二叉树的BFS(层次顺序)遍历时遇到过问题。由于二叉树有很多资源，每个节点最多有两个子节点，我还没有找到任何可以帮助我解决非二叉树问题的资源。到目前为止，我做了这个代码：我的树：在此处输入图像描述我需要按以下顺序处理节点
无序二叉树遍历

为了上课，我必须创建一个状态对象的二叉树，每个状态对象包括一个居民对象的二叉树，这些居民对象组织住在每个州的人。我试图在一个给定的州中搜索最老的居民；然而，居民是按字母顺序组织在树中的，这对我的搜索毫无帮助。因此，我必须遍历整个居民树，更新保存最老的人的节点，并在树被完全遍历后返回它。我已经有了代码的第一部分，但是还停留在如何写递归的剩余部分。状态树的方法：然后是公共“包装器”状态树方法：

队列陷入无限循环的二叉树层次顺序遍历

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档